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

Jianming Dong, Hong Pan, Cunkui Ye, Weitian Tong, Jueliang Hu

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 [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.

Original languageEnglish
Pages (from-to)25-38
Number of pages14
JournalInformation Sciences
Volume544
DOIs
StatePublished - Jan 12 2021

Keywords

  • Approximation algorithm
  • Blocking
  • Flowshop
  • Multi-task flexibility
  • No-wait
  • Worst-case performance ratio

Fingerprint

Dive into the research topics of 'No-wait two-stage flowshop problem with multi-task flexibility of the first machine'. Together they form a unique fingerprint.

Cite this