Two-machine flowshop scheduling in a physical examination center

被引:2
|
作者
Wang, Yadong [1 ]
Fan, Baoqiang [1 ]
Zhai, Jingang [1 ]
Xiong, Wei [2 ]
机构
[1] Ludong Univ, Dept Math & Stat Sci, Yantai 264025, Shandong, Peoples R China
[2] Binzhou Med Univ, Yantai Affiliated Hosp, Dept Spinal Surg, Yantai 264025, Shandong, Peoples R China
关键词
Physical examination; Scheduling; Flowshop; Complexity; Algorithm; SEQUENCING SUBJECT; MAKESPAN;
D O I
10.1007/s10878-017-0233-y
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In this paper, we formulate two important operational processes of the physical examination center as a group scheduling problem in two-machine flowshop. The objective is to minimize the makespan. We first analyze the complexity of the problem with a fixed number of release dates and present a pseudo-polynomial-time algorithm. Then we provide an approximation algorithm and analyze its worst-case error bounds for the problem with two release dates and an optimal algorithm for a very practical special case of the problem.
引用
收藏
页码:363 / 374
页数:12
相关论文
共 50 条
  • [21] Batching and scheduling to minimize the makespan in the two-machine flowshop
    Cheng, TCE
    Wang, GQ
    IIE TRANSACTIONS, 1998, 30 (05) : 447 - 453
  • [22] Two-machine flowshop scheduling with consecutive availability constraints
    Cheng, TCE
    Wang, GQ
    INFORMATION PROCESSING LETTERS, 1999, 71 (02) : 49 - 54
  • [23] Scheduling the fabrication and assembly of components in a two-machine flowshop
    Cheng, TCE
    Wang, GQ
    IIE TRANSACTIONS, 1999, 31 (02) : 135 - 143
  • [24] An improved two-machine flowshop scheduling with intermediate transportation
    Jianming Dong
    Xueshi Wang
    Jueliang Hu
    Guohui Lin
    Journal of Combinatorial Optimization, 2016, 31 : 1316 - 1334
  • [25] A two-agent scheduling problem in a two-machine flowshop
    Ahmadi-Darani, Mohammad-Hasan
    Moslehi, Ghasem
    Reisi-Nafchi, Mohammad
    INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING COMPUTATIONS, 2018, 9 (03) : 289 - 306
  • [26] Two-machine flowshop scheduling with intermediate transportation under job physical space consideration
    Gong, Hua
    Tang, Lixin
    COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (09) : 1267 - 1274
  • [27] Two-machine flowshop scheduling problem with coupled-operations
    Nadjat Meziani
    Ammar Oulamara
    Mourad Boudhar
    Annals of Operations Research, 2019, 275 : 511 - 530
  • [28] Scheduling of a two-machine flowshop with travel time between machines
    Panwalkar, S.S.
    Journal of the Operational Research Society, 1991, 42 (07): : 609 - 613
  • [29] A two-machine flowshop scheduling problem with precedence constraint on two jobs
    Cheng, Shuenn-Ren
    Yin, Yunqiang
    Wen, Chih-Hou
    Lin, Win-Chin
    Wu, Chin-Chia
    Liu, Jun
    SOFT COMPUTING, 2017, 21 (08) : 2091 - 2103
  • [30] Scheduling of two-machine flowshop with outsourcing lead-time
    Kim, Eun-Seok
    Lee, Ik Sun
    COMPUTERS & OPERATIONS RESEARCH, 2022, 145