An iterative improvement approach for the nonpreemptive open shop scheduling problem

This paper addresses the problem of scheduling nonpreemptive open shops with the objective of minimizing makespan. An iterative improvement approach based on Benders' decomposition is presented. This approach separates the sequencing and scheduling components of the problem allowing each to be attacked individually. The scheduling component is the dual of a longest path problem that can be efficiently solved by the well known label correcting method. The sequencing component defies rigorous optimization but leads to a useful sequence improvement procedure. Computational experiments show that most solutions found are within 1% of lower bounds and hence demonstrate the potential of the approach to efficiently schedule open shops.