Schedule packing starts with any schedule satisfying precedence constraints between tasks. It then shifts that schedule, first to the right (forward in time), and then to the left (back to the starting time). For the right shift an arbitrary point in the future is chosen as the endpoint. Tasks are then pulled off the schedule in reverse ending time order and placed in the new, right shifted schedule as close to the endpoint as possible, while still honoring resource and precedence constraints. The left shift is an analogous process where tasks are pulled off the right shifted schedule in starting time order and placed as early as possible, while still honoring precedence and resource constraints.
Repeated iterations of right-left shifts typically results in solutions with short makespans, although on any particular iteration the schedule length may go up or down. This technique also scales well as problem sizes increase, and has been used to produce the best known results on a standard benchmark related to aircraft manufacturing.
CIRL has applied schedule packing to a number of benchmark scheduling problems, most notably a 575 task, 17 resource problem derived from an actual problem from an aircraft manufacturer. Recent work at CIRL has focused on adding limited randomization to the algorithm to help it escape local minima.
It is also worth noting that schedule packing, in some sense, inspired squeaky wheel optimization, a more general purpose search technique that was also developed at CIRL. Schedule packing can in fact be viewed as a domain specific implementation of squeaky wheel.