Cyclic sequencing problems in the two-machine permutation flow shop: Complexity, worst-case and average case analysis

In this article, the cyclic sequencing problem in the two-machine flow shop is formalized. 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, a heuristic procedure is developed 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.