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
Abstract:
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)