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

Yakov Zinder ;

Alexandr Kononov ;

Joey Fung .

Journal of Combinatorial Optimization, 2021, 42 :276-309

[22] The one machine scheduling problem: Insertion of a job under the real-time constraint [J].

Duron, C. ;

Louly, M. A. Ould ;

Proth, J. -M. .

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

Benavides, Alexander J. ;

Vera, Antony .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 297 (02) :407-421

[24] Multi-period scheduling of a multi-stage multi-product bio-pharmaceutical process [J].

Kabra, Shaurya ;

Shaik, Munawar A. ;

Rathore, Anurag S. .

COMPUTERS & CHEMICAL ENGINEERING, 2013, 57 :95-103

[25] Elastic and Flexible Multi-stage Task Scheduling with Deadline-constraint in Clouds [J].

Zhu, Jie ;

Li, Xiaoping .

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

Gorczyca, Mateusz ;

Janiak, Adam ;

Janiak, Wladyslaw ;

Dymanski, Marcin .

DISCRETE APPLIED MATHEMATICS, 2015, 182 :162-168

[27] A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines [J].

Yang, Jaehwan .

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

Bekkar A. ;

Belalem G. ;

Beldjilali B. .

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

Maleck, Christian ;

Nieke, Gottfried ;

Bock, Karlheinz ;

Pabst, Detlef ;

Schulze, Meinhard ;

Stehli, Marcel .

2019 30TH ANNUAL SEMI ADVANCED SEMICONDUCTOR MANUFACTURING CONFERENCE (ASMC), 2019,

[30] Multi-stage man-machine cooperated scheduling method for steelmaking & continuous casting [J].

Zhao, Ning ;

Li, Liang ;

Du, Yan-Hua .

Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, 2014, 20 (07) :1675-1683

← 1 2 3 4 5 →