AB - 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. © 2013 Springer-Verlag. AU - Walker, S AU - Zinder, Y DA - 2013/12/01 DO - 10.1007/978-3-642-45030-3_22 EP - 239 JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) PY - 2013/12/01 SP - 229 TI - The solvable cases of a scheduling algorithm VL - 8283 LNCS Y1 - 2013/12/01 Y2 - 2024/03/28 ER -