^{1}

^{*}

^{2}

^{*}

This paper discusses review of literature of open shop scheduling problems. First, the problem is classified as per different measures of performance, viz., minimization of makespan, minimization of sum of completion times of jobs, minimization of sum of weighted completion times of all jobs, minimization of total tardiness of all jobs, minimization of sum of weighted tardiness of all jobs, minimization of weighted sum of tardy jobs, and miscellaneous measures of the open shop scheduling problem. In each category, the literature is further classified based on approaches used and then the contributions of researchers in the respective categories are presented. Directions for future research are discussed in the end.

Production scheduling is a key for organizational productivity, which prepares a calendar for producing components/products. The scheduling problems are classified into single machine scheduling, flow shop scheduling, job shop scheduling, open shop scheduling, and hybrid scheduling. In this paper, the open shop scheduling problem is considered. The open shop scheduling problem is alternatively called as moderated job shop scheduling problem (Panneerselvam [

The flow shop scheduling problem consists of “n” jobs, each with “m” operations. The process sequences of these jobs are one and the same for this problem. The job shop scheduling problem consists of n jobs, each with m operations. The process sequences of the jobs are not the same for this problem. The open shop scheduling problem consists of n jobs, each with at most m operations. The operations of each job can be processed in any sequence. If a job consists of three operations, viz., 1, 2 and 3, then this job can be processed using any one of the following six sequences, which is n:

Sequence 1: 1 - 2 - 3;

Sequence 2: 1 - 3 - 2;

Sequence 3: 2 - 1 - 3;

Sequence 4: 2 - 3 - 1;

Sequence 5: 3 - 1 - 2;

Sequence 6: 3 - 2 - 1.

If a problem consists of n jobs, each with at most m operations of the open shop scheduling problem, then a generalized data format of the processing times is shown in _{ij} is positive, then the job i requires t_{ij} units of processing time for the operation j; if it is zero, then the job i does not require the operation j.

In open shop scheduling problem (OSSP), there is a finite set J which consists of n jobs _{i} (i = 1 to n) is to be processed on machine M_{j} (j = 1 to m) for t_{ij} processing time, where ij stands for i^{th} job on a j^{th} machine. Each job J_{i} consists of at most m tasks. At a time, each job can be processed only on one machine and each machine can process only one job.

In this paper, a 3-field notation

・ α indicates the machine environment [O2 for open shop with 2 machines, O3 for open shop with 3 machines or O (without any suffix number) for m machines];

・ β indicates job characteristics [r_{i} for release date of every job, ord for ordered jobs, pmtn for preemption allowed, non-preempt for jobs where preemption cannot be allowed, t_{ij} = 1 for all jobs with unit processing time, etc.];

・ γ indicates optimality criteria or objectives [minimization of total completion time or flow time or makespan_{max}, etc.].

In practice, the scheduling of the jobs in the open shop scheduling has several measures of performance which are as listed below:

・ Minimize the makespan;

・ Minimize the sum of completion time of all the jobs;

・ Minimize the weighted sum of completion times of all jobs;

・ Minimize the total tardiness of all jobs;

Job i | Operation j | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

1 | 2 | 3 | . | . | j | . | . | M | ||

1 | t_{11} | t_{12} | t_{13} | . | . | t_{1j} | . | . | t_{1m} | |

2 | t_{21} | t_{22} | t_{23} | . | . | _{t}_{2j} | . | . | t_{2m} | |

3 | t_{31} | t_{32} | t_{33} | . | . | t_{3j} | . | . | t_{3m} | |

. | . | . | . | . | . | . | . | . | . | |

. | . | . | . | . | . | . | . | . | . | |

i | t_{i}_{1} | t_{i}_{2} | t_{i}_{3} | . | . | t_{ij} | . | . | T_{im} | |

. | . | . | . | . | . | . | . | . | . | |

. | . | . | . | . | . | . | . | . | . | |

n | T_{n}_{1} | T_{n}_{2} | T_{n}_{3} | . | . | t_{nj} | . | . | t_{nm} |

・ Minimize the weighted total tardiness of all jobs;

・ Minimize the number of tardy (late) jobs;

・ Minimize the number of weighted sum of tardy (late) jobs;

・ Minimize the maximum lateness.

Let

・ n be the number of jobs;

・ m be the number of machines (operations);

・ d_{i} is the due date of the job i;

・ C_{i} be the completion time of the last operation in the assumed sequence for processing of the job i;

・ W_{i} be the weight of the job i;

・ T_{i} (also called L_{i}) be the tardiness (lateness) of the job i.

The makespan (C_{max}) is the maximum of the completion times of all the jobs and it is given by the following formula. It is the measure, which indicates the earliest time at which the given batch of jobs can be fully completed, which is known as makespan. The objective is to minimize the makespan.

The sum of the completion times of the jobs is given by the following formula and it should be minimized. This objective minimizes the total flow time which amounts to minimizing the mean flow time of the jobs in the system. This in turn minimizes the in-process inventory.

Sum of the completion times of the jobs =

The weighted sum of completion times of the jobs is given by the following formula. This measure should be minimized. If the jobs differ in terms of importance (priority) for processing, then the jobs are assigned with weights W_{i},

Weighted sum of the completion times of the jobs = _{ }

The sum of the tardiness of the jobs is given by the following formula and it should be minimized.

Sum of the tardiness of all the jobs =

The tardiness (T_{i}) of the job i is given by the following formula.

The sum of the weighted tardiness is given by the following formula and this measure is to be minimized.

Sum of weighted tardiness of all the jobs =

The number of tardy/late jobs is given by the following formula and this measure is to be minimized.

The number of tardy/late jobs =_{i} = 1 if C_{i} is more than d_{i}; U_{i} = 0, otherwise.

The formula for the sum of the weighted number of tardy jobs is given by the following formula and it should be minimized.

Sum of weighted number of tardy jobs =

The formula for the maximum lateness (tardiness) [L_{max}] is given by the following formula and it should be minimized.

The main objective of this research paper is to classify the research papers on open shop scheduling problem in different ways. The other objectives of this review are to study the recent trends in the area of open shop scheduling and critically review the research papers. Many researchers earlier studied different open shop scheduling problems. Kubiak et al. [_{,} is strongly NP-hard. Brucker et al. [

S.No. | Measure of Performance | Methods | Reference Numbers of Articles |
---|---|---|---|

1 | C_{max} = max{C_{i}}―Minimize the makespan | Theoretical study | [ |

Mathematical models | [ | ||

Exact algorithms | [ | ||

Heuristics | [ | ||

Genetic algorithms | [ | ||

Tabu search algorithms | [ | ||

Simulated annealing algorithms | [ | ||

ACO algorithms | [ | ||

Bee colony optimization algorithms | [ | ||

Hybrid algorithms | [ | ||

2 | Exact algorithms | [ | |

Heuristics | [ | ||

Tabu search algorithms | [ | ||

Particle swarm optimization algorithm | [ | ||

Hybrid algorithms | [ | ||

Multiple algorithms | [ | ||

Miscellaneous algorithms | [ | ||

3 | Heuristics | [ | |

Genetic algorithms | [ | ||

Particle swam optimization algorithms | [ | ||

4 | Heuristics | [ | |

5 | Mathematical models | [ | |

Heuristics | [ | ||

Simulated annealing | [ | ||

6 | Heuristics | [ | |

7 | Heuristics | [ | |

8 | L_{max} = max{L_{i}}―Minimize maximum lateness | Heuristics | [ |

9 | Miscellaneous measures and theory | [ |

This section presents the review of literature in which the objective is to minimize the makepsan. The literature under this category is classified as given below:

・ Theoretical study;

・ Mathematical models;

・ Exact algorithms;

・ Heuristics;

・ Genetic algorithms;

・ Tabu search algorithms;

・ Simulated annealing algorithms;

・ ACO algorithms;

・ Bee colony optimization algorithms;

・ Hybrid algorithms.

This section presents the review of literature of the theoretical study conducted in the open shop scheduling problem.

Brasel et al. [_{max}). They showed that two-machine cyclic open shop problem to minimize makespan is polynomially solvable but three machines cyclic open shop problem is NP-hard. Also, they showed that two-machine compact cyclic open shop problem to minimize the makespan is NP-hard. Finally, they compared the computational complexity results of cyclic open shop problem and compact cyclic open shop problem.

Masuda and Ishii [

Brucker et al. [_{k} problem. Gueret et al. [

Gonzalez and Sahni [^{3}) algorithm for the two-machine open shop scheduling problem with single renewable resource and non-preemptive schedule. Based on this aspect, they developed a polynomial time algorithm to minimize the makespan. They further showed that the two-machine open shop with two different resources is NP-hard. They also showed that the optimal non-preemptive schedules are not longer than optimal preemptive schedules. Lu and Posner [

・

・

・

The authors developed a constructive and iterative heuristics to solve approximately the problems_{max}, which is the makespan. They developed three different constructive heuristics based on insertion techniques for 2 polynomially solvable special cases. They derived a strongly connected neighborhood structure and used it to develop an effective two iterative heuristics, viz., Simulated Annealing (SA) and multi-start procedure. They compared the result of insertion technique with that of iterative procedures. But, they did not use any statistical tool in their comparison. Rebaine [

Alcaide et al. [_{j} = 0) and all jobs have different release dates r_{j}. Zhang and Velde [_{m}(ρ) for m-machine case. Similarly, they provided an approximation algorithm Path-O2(σ) for path-version of 2-machine case and an approximation algorithm Path-Om for m-machine case of path-version. Bai and Tang [

Chung and Mohanty [_{i} and deadline d_{i}. Liaw [

Modarres and Ghandehari [

Naderi et al. [

Fang et al. [

Liaw [

Zobolas et al. [

Liaw [

This section gives the review of literature of the simulated annealing algorithm used to obtain solution for the open shop scheduling problem.

Roshanaei et al. [

Panahi and Tavakkoli-Moghaddam [

This section presents a review of literature of the open shop scheduling problem using bee colony optimization algorithms.

Huang and Lin [_{max} will be”.

Liu and Ong [

The review of literature of the open shop scheduling problem with the objective of minimizing the makespan reveals that more researchers developed several heuristics and genetic algorithms to solve the problem. So, future researchers may attempt to develop other meta-heuristics and hybrid algorithms to minimize the makespan of this problem. Further, comparisons of the proposed algorithms with existing algorithms have been carried out using mean and percentage analysis. Instead, in future researchers may follow a complete factorial experiment for comparison purpose by taking several factors of importance, out of which “algorithm” must be a factor. This will help to study the effects of the main factors as well as those of interaction terms in ANOVA model on the response variable, namely performance measure(s) of interest.

This sections presents review of literature on the minimization of the sum of completion time of all the jobs under the following subdivisions:

・ Exact algorithm;

・ Heuristics;

・ Tabu search algorithm;

・ Particle swarm optimization algorithm;

・ Hybrid algorithm;

・ Multiple algorithm;

・ Miscellaneous algorithm.

Dror [

Achugbue and Chin [

Tautenhahn [_{ }(where GS (1) means given sequence for 1 machine). They developed a one-pass heuristic with an adjustment strategy to adjust the parameter in each of the iterations. They then derived a lower bound followed by branch-and-bound algorithm to obtain optimal value.

Seraj and Tavakkoli-Moghaddam [

Sha et al. [

This section presents a review of literature of hybrid algorithms to solve the open shop scheduling problem. Naderi et al. [

This section presents a review of literature involving more than one algorithm used to solve the open shop scheduling problem.

Andresen et al. [

Leung et al. [

The review of the open shop problem with the objective of minimizing the sum of completion times of jobs shows that more research have been carried out using heuristics. So, future researchers may concentrate in developing meta-heuristics and hybrid algorithms for this problem. As mentioned in the previous section, a complete factorial experiment may be used for comparison of proposed algorithms with existing algorithms. Further, it is advisable to randomly generate data as per the complete factorial experiment so that a perfect balance will be there under all levels of the factors.

This section presents the review of literature on the minimization of the sum of the weighted completion times of all the jobs under the sub-classifications heuristics, genetic algorithm and particle swarm optimization algorithm.

Gandhi et al. [

Doulabi et al. [

Noori-Darvish et al. [

The review under this section clearly shows that less works have been carried out to minimize the sum of weighted completion times of all the jobs of the open shop scheduling problem. So, future researchers may concentrate in developing heuristics, meta-heuristics and hybrid algorithms for this problem. As mentioned in Section 3.1, a complete factorial experiment may be used for comparison of proposed algorithms with existing algorithms.

This section gives a review of literature of the minimization of total tardiness of all the jobs of the open shop scheduling problem under the sub-classification heuristics.

HeuristicsLiu and Bulfin [

From the review of this section, one can infer that very fewer researches have been carried out to minimize the total tardiness of all jobs of the open shop scheduling problem. So, future researchers may concentrate in developing heuristics, meta-heuristics and hybrid algorithms for this problem. As mentioned in Section 3.1, a complete factorial experiment may be used for comparison of proposed algorithms with existing algorithms.

This section gives review of literature on the minimization of the sum of weighted tardiness of the open shop scheduling problem under the sub-classifications mathematical model, heuristic and simulated annealing algorithm.

Doulabi [

Blazewicz et al. [_{w}) with a special case of preemption allowed for open shop scheduling problem. Later, they proposed an algorithm to minimize weighted tardiness (T_{w}) and total tardiness (T) in two-machine open shop with a common due date for all the jobs.

Andresen et al. [

From the review of this section, it is clear that few researchers contributed to minimize the sum of weighted tardiness of all jobs of the open shop scheduling problem. So, future researchers may concentrate in developing heuristics, meta-heuristics and hybrid algorithms for this problem.

This section presents the review of literature on the minimization of the weighted sum of tardy jobs of the open shop scheduling problem under the sub-classification heuristic.

HeuristicNg et al. [

Under this measure of minimizing the weighted sum of tardy jobs of the open shop scheduling problem, only article is presented. In fact, this measure is considered to be an important measure. So, researchers may select this measure for their researches and develop heuristics/meta-heuristics/hybrid algorithms.

Cho and Sahni [_{i} for each edge and each color i. Giaro et al. [

Open shop scheduling problem is a special kind of scheduling problem, which has n jobs, each with m operations, similar to follow shop, but the operations of each job can be processed in any order. So, this problem comes under combinatorial category, which warrants the use of meta-heuristic to find good solution. In this paper, a comprehensive review of literature has been carried out under the categories, viz., minimization of makespan, minimization of sum of completion times of jobs, minimization of sum of weighted completion times of all jobs, minimization of total tardiness of all jobs, minimization of sum of weighted tardiness of all jobs, minimization of weighted sum of tardy jobs, and miscellaneous measures. It is observed that the researchers have used theoretical study, mathematical models, exact algorithms, heuristics, genetic algorithms, tabu search algorithms, simulated annealing algorithms, ACO algorithms, bee colony optimization algorithms, and hybrid algorithms for the open shop scheduling problem to minimize the makespan. The literature to minimize the sum of completion times of jobs of the open shop scheduling problem is presented under exact algorithm, heuristics, tabu search algorithm, particle swarm optimization algorithm, hybrid algorithm, multiple algorithm, and miscellaneous algorithms. It is observed that heuristics, genetic algorithm and particle swarm optimization algorithm are used to minimize the sum of weighted completion times of all jobs. From literature, it is found that only heuristics are used to minimize the total tardiness of all the jobs. The sum of weighted tardiness of all jobs is minimized using mathematical model, heuristic and simulated annealing algorithm. Only one article discusses the minimization of the weighted sum of tardy jobs of the open shop scheduling problem.

From the review, it is clear that wherever comparison of the proposed algorithm with existing algorithm(s) has been carried out, it is done using mean and percentage analysis. In future, researchers may follow a complete factorial experiment for comparison purpose by taking several factors of importance, out of which “algorithm” must be a factor. This will help to study the effects of the main factors, as well as those of interaction terms in ANOVA model on the response variable, namely, performance measure(s) of interest. Further, randomly generated data may be used for comparison purpose, so that the problems under the levels of the factorial experiment are in balanced nature.

From the literature, it is clear that many researchers have contributed to the minimization of the makespan, as well as minimization of the sum of completion times of jobs of the open shop problem, in terms of several approaches, including meta-heuristics. For other measures of performance, the number of contributions, as well as applications of different meta-heuristics, is less in number. So, future researchers may focus on developing meta-heuristics for the other measures of performance. Since the minimization of makespan is considered to be a dominant measure of performance, development of varied hybrid algorithms to minimize the makespan may also be attempted by researchers in future.

The authors thank the anonymous referees for their constructive suggestions, which have improved the paper.