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 条

[41] Algorithm to improve job scheduling problem in cloud computing environment [J].

Tareghian, Shahab ;

Bornaee, Zarrintaj .

2015 2ND INTERNATIONAL CONFERENCE ON KNOWLEDGE-BASED ENGINEERING AND INNOVATION (KBEI), 2015, :683-687

[42] Complexity and approximation for scheduling problem for a torpedo [J].

Simonin, G. ;

Giroudeau, R. ;

Koenig, J. C. .

COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 61 (02) :352-356

[43] A lot-sizing and scheduling model for multi-stage flow lines with zero lead times [J].

Stadtler, Hartmut ;

Sahling, Florian .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 225 (03) :404-419

[44] Multi-stage supply chain scheduling with non-preemptive continuous operations and execution control [J].

Ivanov, Dmitry ;

Sokolov, Boris ;

Dolgui, Alexandre .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (13) :4059-4077

[45] A note on the complexity of scheduling problems with linear job deterioration [J].

Koulamas, Christos ;

Panwalkar, S. S. .

JOURNAL OF GLOBAL OPTIMIZATION, 2015, 62 (02) :409-410

[46] The complexity of machine scheduling for stability with a single disrupted job [J].

Leus, R ;

Herroelen, W .

OPERATIONS RESEARCH LETTERS, 2005, 33 (02) :151-156

[47] A note on the complexity of scheduling problems with linear job deterioration [J].

Christos Koulamas ;

S. S. Panwalkar .

Journal of Global Optimization, 2015, 62 :409-410

[48] Solving the Job Shop Scheduling Problem by the Multi-Hybridization of Swarm Intelligence Techniques [J].

Hakim, Jebari ;

Rekiek, Siham ;

Reklaoui, Kamal .

INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS, 2022, 13 (07) :753-764

[49] Scheduling problems with position dependent job processing times: computational complexity results [J].

Radosław Rudek .

Annals of Operations Research, 2012, 196 :491-516

[50] On the computational complexity of the patrol boat scheduling problem with complete coverage [J].

Surendonk, Timothy J. ;

Chircop, Paul A. .

NAVAL RESEARCH LOGISTICS, 2020, 67 (04) :289-299

← 1 2 3 4 5 →