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

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

0.00 Avg rating0 Votes
Article ID: iaor20082412
Country: United Kingdom
Volume: 34
Issue: 7
Start Page Number: 2025
End Page Number: 2042
Publication Date: Jul 2007
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics: tabu search
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 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.

Reviews

Required fields are marked *. Your email address will not be published.