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

We study the problem of constructing a minimum makespan schedule for the n-jobm-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.