Three-machine open shop with a bottleneck machine revisited
- PDF / 560,099 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 82 Downloads / 165 Views
Three-machine open shop with a bottleneck machine revisited Inna G. Drobouchevitch1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The paper considers the three-machine open shop scheduling problem to minimize the makespan. In the model, each job consists of two operations, one of which is to be processed on the bottleneck machine, which is the same for all jobs. A new linear-time algorithm to find an optimal non-preemptive schedule is developed. The suggested algorithm considerably simplifies the only previously known method as it straightforwardly exploits the structure of the problem and its key components to yield an optimal solution. Keywords Scheduling · Open shop · Minimum makespan
1 Introduction In this paper, we consider the non-preemptive open shop scheduling problem. In a general open shop scheduling model, each job consists of several operations to be processed on all or some of the given machines. For each job, an order of its operations (the processing route) is not known in advance but must be chosen. Different jobs are allowed to be assigned different routes. No preemption is allowed, i.e., once the processing of a job on a machine starts, it proceeds without interruption. A standard scheduling requirement says that a job is processed on at most one machine at a time, and a machine can process no more than one job at a time. In this paper, we consider the open shop problem in which the number of operations per job is less than the number of machines. Moreover, one of the operations of each job has to be processed on a particular machine, which is the same for all jobs. We call such a machine the bottleneck machine. The objective function to be minimized is the makespan, i.e., the maximum completion time of all jobs on all machines. The open shop scheduling problem with the minimum makespan criterion is denoted by Om||Cmax if the number of machines is fixed and equal to m (Lawler et al. 1993). The open shop problem was introduced by Gonzalez and Sahni (1976) who gave a linear-time algorithm to solve the O2||Cmax problem and proved that the O3||Cmax problem is
B 1
Inna G. Drobouchevitch [email protected]
N P-hard in the ordinary sense. Notice that the latter result only holds if the problem instance contains a job consisting of three operations. The O3||Cmax problem with two operations per job and a bottleneck machine was considered by Drobouchevitch and Strusevich (1999), where a new lower bound on the optimal makespan was found and a linear-time algorithm to solve the problem was developed. The complexity status of a general O3||Cmax problem with two operations per job remains unknown. The O4||Cmax problem with two operations per job and a bottleneck machine is N P-hard in the ordinary sense (Gonzalez and Sahni 1976). In an open shop model, the absence of an imposed order of job operations makes problems flexible but extremely combinatorial and computationally challenging. It is known that for the open shop with three operations per job finding a schedule close
Data Loading...
