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 条
  • [21] A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
    Yakov Zinder
    Alexandr Kononov
    Joey Fung
    [J]. Journal of Combinatorial Optimization, 2021, 42 : 276 - 309
  • [22] The one machine scheduling problem: Insertion of a job under the real-time constraint
    Duron, C.
    Louly, M. A. Ould
    Proth, J. -M.
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 199 (03) : 695 - 701
  • [23] The reversibility property in a job-insertion tiebreaker for the permutational flow shop scheduling problem
    Benavides, Alexander J.
    Vera, Antony
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 297 (02) : 407 - 421
  • [24] Multi-period scheduling of a multi-stage multi-product bio-pharmaceutical process
    Kabra, Shaurya
    Shaik, Munawar A.
    Rathore, Anurag S.
    [J]. COMPUTERS & CHEMICAL ENGINEERING, 2013, 57 : 95 - 103
  • [25] Elastic and Flexible Multi-stage Task Scheduling with Deadline-constraint in Clouds
    Zhu, Jie
    Li, Xiaoping
    [J]. 2016 IEEE 20th International Conference on Computer Supported Cooperative Work in Design (CSCWD), 2016, : 286 - 291
  • [26] Makespan optimization in a single-machine scheduling problem with dynamic job ready times-Complexity and algorithms
    Gorczyca, Mateusz
    Janiak, Adam
    Janiak, Wladyslaw
    Dymanski, Marcin
    [J]. DISCRETE APPLIED MATHEMATICS, 2015, 182 : 162 - 168
  • [27] A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines
    Yang, Jaehwan
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2010, 48 (05) : 1531 - 1538
  • [28] Iterated greedy insertion approaches for the flexible job shop scheduling problem with transportation times constraint
    Bekkar A.
    Belalem G.
    Beldjilali B.
    [J]. International Journal of Manufacturing Research, 2019, 14 (01) : 43 - 66
  • [29] A Robust Multi-Stage Scheduling Approach for Semiconductor Manufacturing Production Areas with Time Contraints
    Maleck, Christian
    Nieke, Gottfried
    Bock, Karlheinz
    Pabst, Detlef
    Schulze, Meinhard
    Stehli, Marcel
    [J]. 2019 30TH ANNUAL SEMI ADVANCED SEMICONDUCTOR MANUFACTURING CONFERENCE (ASMC), 2019,
  • [30] Multi-stage man-machine cooperated scheduling method for steelmaking & continuous casting
    Zhao, Ning
    Li, Liang
    Du, Yan-Hua
    [J]. Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, 2014, 20 (07): : 1675 - 1683
12345