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: | Jzefowska Joanna, Wglarz Jan, Mika Marek, Rycki Rafa, Waligra Gregor |
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%.