Complexity of the job insertion problem in multi-stage scheduling

被引：1
作者：
Vestjens, Arjen P. A.
Wennink, Marc
Woeginger, Gerhard J.
机构：
[1] TU Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands
[2] Ctr Quantitat Methods CQM BV, NL-5600 AK Eindhoven, Netherlands
来源：
OPERATIONS RESEARCH LETTERS | 2007年 / 35卷 / 06期
关键词：
scheduling; computational complexity;
D O I：
10.1016/j.orl.2007.02.004
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops. (C) 2007 Published by Elsevier B.V.
引用
收藏
页码：754 / 758
页数：5
相关论文
共 50 条
[31]   An effective multi-stage evolutionary algorithm for distributed scheduling with splitting jobs in heterogeneous factories [J].
Guo, Xin ;
Deng, Qianwang ;
Luo, Qiang ;
Xie, Guanhua .
ENGINEERING OPTIMIZATION, 2025, 57 (03) :688-716
[32]   Scheduling multi-stage parallel-processor services to minimize average response time [J].
Allahverdi, A ;
Al-Anzi, FS .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2006, 57 (01) :101-110
[33]   Autonomous decentralized scheduling system for multi-stage parallel-unit production processes [J].
Kitajima, T ;
Nishitani, H ;
Saitoh, A ;
Hasebe, S ;
Hashimoto, I .
KAGAKU KOGAKU RONBUNSHU, 1996, 22 (05) :1031-1038
[34]   The consecutive multiprocessor job scheduling problem [J].
Bukchin, Yossi ;
Raviv, Tal ;
Zaides, Ilya .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 284 (02) :427-438
[35]   On cyclic job shop scheduling problem [J].
Bozejko, Wojciech ;
Wodecki, Mieczyslaw .
2018 IEEE 22ND INTERNATIONAL CONFERENCE ON INTELLIGENT ENGINEERING SYSTEMS (INES 2018), 2018, :265-270
[36]   Analysis of multi-stage open shop processing systems [J].
Eggermont, Christian E. J. ;
Schrijver, Alexander ;
Woeginger, Gerhard J. .
28TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2011), 2011, 9 :484-494
[37]   Analysis of multi-stage open shop processing systems [J].
Eggermont, Christian E. J. ;
Schrijver, Alexander ;
Woeginger, Gerhard J. .
MATHEMATICAL PROGRAMMING, 2013, 142 (1-2) :331-348
[38]   Analysis of multi-stage open shop processing systems [J].
Christian E. J. Eggermont ;
Alexander Schrijver ;
Gerhard J. Woeginger .
Mathematical Programming, 2013, 142 :331-348
[39]   Optimal Scheduling of Multi-stage Multi-product Biopharmaceutical Processes Using a Continuous-time Formulation [J].
Vieira, Miguel ;
Pinto-Varela, Tania ;
Barbosa-Povoa, Ana Paula .
24TH EUROPEAN SYMPOSIUM ON COMPUTER AIDED PROCESS ENGINEERING, PTS A AND B, 2014, 33 :301-306
[40]   Complexity and approximation for scheduling problem for a torpedo [J].
Giroudeau, R. ;
Koenig, J. C. ;
Simonin, G. .
CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, :300-304
12345