An almost optimal heuristic for preemptive Cmax scheduling of dependent tasks on parallel identical machines

An almost optimal heuristic for preemptive Cmax scheduling of dependent tasks on parallel identical machines

0.00 Avg rating0 Votes
Article ID: iaor20043566
Country: Netherlands
Volume: 129
Issue: 1
Start Page Number: 205
End Page Number: 216
Publication Date: Jul 2004
Journal: Annals of Operations Research
Authors: , , , ,
Abstract:

We consider the problem of scheduling preemptive, dependent tasks on parallel, identical machines to minimize the makespan. The computational complexity of this problem remains open if the number of machines is fixed and larger than 2. The aim of this paper is to compare two heuristic algorithms on a basis of a computational experiment. The solutions generated by the heuristics are compared with optimal solutions obtained by a branch-and-bound algorithm. Computational results show that the heuristic based on node ordering finds optimal schedules for 99.9% of instances with the maximum relative deviation from optimum of 4.8%.

Reviews

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