 Cyclic sequencing problems in the two‐machine permutation flow shop: Complexity, worst‐case, and average‐case analysisHirofumi Matsuo Naval Research Logistics (NRL), 1990, vol. 37, issue 5, 679-694 Abstract: 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. Date: 1990 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:37:y:1990:i:5:p:679-694 Access Statistics for this article More articles in Naval Research Logistics (NRL) from John Wiley & Sons |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.