TY - JOUR
T1 - No-wait two-stage flowshop problem with multi-task flexibility of the first machine
AU - Dong, Jianming
AU - Pan, Hong
AU - Ye, Cunkui
AU - Tong, Weitian
AU - Hu, Jueliang
N1 - Publisher Copyright:
© 2020
PY - 2021/1/12
Y1 - 2021/1/12
N2 - 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 [Formula presented]. 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.
AB - 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 [Formula presented]. 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.
KW - Approximation algorithm
KW - Blocking
KW - Flowshop
KW - Multi-task flexibility
KW - No-wait
KW - Worst-case performance ratio
UR - http://www.scopus.com/inward/record.url?scp=85088917146&partnerID=8YFLogxK
U2 - 10.1016/j.ins.2020.06.052
DO - 10.1016/j.ins.2020.06.052
M3 - Article
AN - SCOPUS:85088917146
SN - 0020-0255
VL - 544
SP - 25
EP - 38
JO - Information Sciences
JF - Information Sciences
ER -