THE COFFMAN-GRAHAM ALGORITHM OPTIMALLY SOLVES UET TASK SYSTEMS WITH OVERINTERVAL ORDERS

摘要

Scheduling of unit execution time (UET) task systems on parallel machines with minimal schedule length is known to be NP-complete. The problem is polynomially solvable for some special cases. For a fixed number of parallel machines m > 2, the complexity of the problem is still open, but the problem becomes NP-hard if m is arbitrary. In this paper we characterize a new order class that properly contains quasi-interval orders and we prove that the Coffman—Graham algorithm yields optimal schedules for this new class on any number of machines. Finally, some extensions are discussed for a larger order class and for scheduling in the presence of unit communication delays.