The solvable cases of a scheduling algorithm

Publisher:
Springer
Publication Type:
Journal Article
Citation:
Lecture Notes in Computer Science, 2013, 8283 (1), pp. 229 - 239
Issue Date:
2013-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013003789OK.pdf192.88 kB
Adobe PDF
When considering the NP-hard problem of scheduling precedence constrained tasks with preemptions on identical parallel machines with the goal of minimising the maximum lateness, approximation algorithms are commonly studied. It is desirable to characterise in some way the circumstances under which a given algorithm will provide an optimal solution. This paper considers a well-known scheduling algorithm called the Brucker-Garey-Johnson Algorithm, known to produce optimal schedules whenever the precedence constraints are in the form of in-trees. A new class of partial orders is presented and it is proved not only that the Brucker-Garey-Johnson Algorithm will solve every problem instance constrained by a partial order from that class but also that no larger class has this property.
Please use this identifier to cite or link to this item: