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 条
  • [1] Reachability and Deadlocking Problems in Multi-stage Scheduling
    Eggermont, Christian E. J.
    Woeginger, Gerhard J.
    REACHABILITY PROBLEMS, 2011, 6945 : 153 - 164
  • [2] Job release scheduling problem: Complexity and an approximation algorithm
    Choi, Byung-Cheon
    Chung, Jibok
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (06) : 858 - 863
  • [3] Real-time scheduling of multi-stage flexible job shop floor
    Ham, Myoungsoo
    Lee, Young Hoon
    Kim, Sun Hoon
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2011, 49 (12) : 3715 - 3730
  • [4] On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties
    Lauff, V
    Werner, F
    COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (03) : 317 - 345
  • [5] A study of the multi-stage flowshop scheduling problem with alternative operation assignments
    Futatsuishi, Y
    Watanabe, I
    Nakanishi, T
    MATHEMATICS AND COMPUTERS IN SIMULATION, 2002, 59 (1-3) : 73 - 79
  • [6] A multi-stage dynamic soft scheduling algorithm for the uncertain steelmaking-continuous casting scheduling problem
    Jiang, Sheng-long
    Zheng, Zhong
    Liu, Min
    APPLIED SOFT COMPUTING, 2017, 60 : 722 - 736
  • [7] A MILP Scheduling Model for Multi-stage Batch Plants
    Kopanos, Georgios M.
    Puigjaner, Luis
    19TH EUROPEAN SYMPOSIUM ON COMPUTER AIDED PROCESS ENGINEERING, 2009, 26 : 369 - 374
  • [8] Modelling multi-stage manufacturing systems for efficient scheduling
    Charalambous, C
    Tahmassebi, T
    Hindi, K
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 122 (02) : 329 - 338
  • [9] A Dynamic Approach to Multi-stage Job Shop Scheduling in an Industry 4.0-Based Flexible Assembly System
    Ivanov, Dmitry
    Dolgui, Alexandre
    Sokolov, Boris
    ADVANCES IN PRODUCTION MANAGEMENT SYSTEMS: THE PATH TO INTELLIGENT, COLLABORATIVE AND SUSTAINABLE MANUFACTURING, 2017, 513 : 475 - 482
  • [10] An Iterative Greedy Insertion Technique for Flexible Job Shop Scheduling Problem
    Bekkar, Azzedine
    Guemri, Oualid
    Bekrar, Abdelghani
    Aissani, Nassima
    Beldjilali, Bouziane
    Trentesaux, Damien
    IFAC PAPERSONLINE, 2016, 49 (12): : 1956 - 1961
12345