In this article the authors present an algorithm for the minimum makespan preemptive open shop, which is superior to existing algorithms in both space and time requirements. They define the more complex generalized open shop and flexible open shop and address the minimum makespan problem on these shops. The authors show how the algorithm for the minimum makespan open shop can be used to achieve load balancing in simple and generalized open shops without increasing the complexity of the algorithm. Load balancing dictates that the number of busy machines in each period is as even as possible. The authors also consider preventive maintenance issues in the open shop, and makespan retains its minimum value. In particular they consider the scenario where a machine can be maintained during any period that it happens to be idle. The authors also consider the case that a maintenance schedule is prespecified. They show that this problem can be solved via a linear programming formulation that can also take into account release times for the jobs and ready times for the machines. Faster algorithms are presented for open shops with three machines or less.
