✦ LIBER ✦

Open shop problem with zero-one time operations and integer release date/deadline intervals

✍ Scribed by Marek Kubale

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 744 KB
Volume: 76
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(96)00126-6

No coin nor oath required. For personal study only.

✦ Synopsis

We study the problem of constructing a minimum makespan schedule for the n-job m-machine open shop with zero-one time operations and integer release dates and deadlines. The general scheduling problem is shown to be NP-complete. Two polynomial-time algorithms are given for the following special cases: (1) all possible mn operations have unit execution time, and (2) at most m + n operations have unit execution time. Next, the second algorithm is generalized to bounded cyclicity graphs. All the algorithms are capable of minimizing not only makespan but maximum lateness and maximum tardiness as well.