Precedence Constraint Scheduling on a Fixed Number of MachinesResearch Paper
Scheduling unit-time jobs under precedence constraints on a fixed number of identical machines, written , is a long-standing question of scheduling theory (surveys: Lawler–Lenstra–Rinnooy Kan–Shmoys 1993, Mnich–van Bevern 2018). For the problem is immediate, and for it is solved in polynomial time. When the number of…