Premium
Cyclic sequencing problems in the two‐machine permutation flow shop: Complexity, worst‐case, and average‐case analysis
Author(s) -
Matsuo Hirofumi
Publication year - 1990
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199010)37:5<679::aid-nav3220370507>3.0.co;2-q
Subject(s) - travelling salesman problem , permutation (music) , scheduling (production processes) , mathematical optimization , computer science , fifo (computing and electronics) , schedule , job shop scheduling , mathematics , heuristic , heuristics , physics , acoustics , computer hardware , operating system
In this article, we formalize the cyclic sequencing problem in the two‐machine flow shop. When jobs are processed in a repetitive cycle, the size of a scheduling problem is significantly reduced, and the resulting schedule is easy to implement because of its simplicity. Two types of cyclic sequencing problems are considered: the no‐wait problem and the minimum‐wait problem. The no‐wait problem maximizes the throughput rate subject to the condition that there is no buffer space between the two machines. The minimum‐wait problem minimizes the average WIP level subject to the conditions that the maximum throughput rate is maintained and that the FIFO dispatching rule is used in the intermediate buffer space. The no‐wait problem is a well‐known special case of the traveling salesman problem (TSP) and is polynomially solvable. The minimum‐wait problem is shown to be NP‐hard; therefore, we develop a heuristic procedure along with the analysis of its worst‐case and average‐case performance. Here, the average‐case analysis is based on the expected length of the Hamiltonian tour for this special case of the TSP. The average‐case analysis indicates that when the number of jobs in a cycle is small, the derived cyclic schedule yields a low WIP level.