| Abstract: | In this article we present an algorithm for the minimum makespan preemptive open shop, which is superior to existing algorithms in both space and time requirements. We define the more complex generalized open shop and flexible open shop and address the minimum makespan problem on these shops. We show how we can use the algorithm for the minimum makespan open shop 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. We also consider preventive maintenance issues in the open shop, and makespan retains its minimum value. In particular we consider the scenario where a machine can be maintained during any period that it happens to be idle. Also we consider the case that a maintenance schedule is prespecified. We 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. © 1995 John Wiley & Sons, Inc. |
