Minimizing Maximum Lateness in a Two-Machine Open Shop
Published Online:1 Feb 1981https://doi.org/10.1287/moor.6.1.153
Abstract
We consider the problem of scheduling independent jobs in a two-machine open shop so as to minimize the maximum lateness with respect to due dates for the jobs. For the case in which preemption is allowed, a linear-time algorithm is presented. For the nonpreemptive case, NP-hardness is established.
