No-wait two-stage flowshop problem with multi-task flexibility of the first machine

Abstract

For the creation of intelligent management systems in hospitals, efficient resource arrangement is essential. Motivated by a real-world scenario in hospitals, we introduce the no-wait two-stage flowshop scheduling problem with the first-stage machine having multi-task flexibility. In this problem, each job has two operations which are processed in order on a two-stage flowshop without preemption and time delay between or on machines. The multi-task flexibility allows the first-stage machine to process the second-stage operations. The goal is to minimize the maximum completion time of all jobs. To the best of our knowledge, this is a pioneering work on this problem. We discover several novel structural properties, based on which we present a linear-time combinatorial algorithm with an approximation ratio $\frac{13}{8}$ . This problem and its variants can find many other meaningful applications in modern manufacturing systems, such as the robot cell scheduling with computer numerical control machines or printed circuit boards. The idea behind our algorithm may inspire more practical algorithms.

Keywords: Approximation algorithm; Blocking; Flowshop; Multi-task flexibility; No-wait; Worst-case performance ratio.