Aarhus University Seal / Aarhus Universitets segl

Solving a large-scale precedence constrained scheduling problem with elastic jobs using tabu search

By Christian R. Pedersen, Rasmus V. Rasmussen and Kim A. Andersen
Working Papers
No. 02, October 2004
This paper presents a solution method for minimizing makespan of a practical large-scale scheduling problem with elastic jobs. The jobs are processed on three servers and restricted by precedence constraints, time windows and capacity limitations. We derive a new method for approximating the server exploitation of the elastic jobs and solve the problem using a tabu search procedure. Finding an initial feasible solution is in general $\mathcal{NP}$-complete, but the tabu search procedure includes a specialized heuristic for solving this problem. The solution method has proven to be very efficient and leads to a significant decrease in makespan compared to the strategy currently implemented.
Format available: PDF (231.4 kb), PostScript (898.6 kb)