Approximation schemes for job shop scheduling problems with controllable processing times

被引：42
|
作者：
Jansen, K
Mastrolilli, M
Solis-Oba, R
机构：
[1] IDSIA Ist Molle Studi Intelligenza Artificiale, CH-6928 Lugano, Switzerland
[2] Univ Kiel, D-24198 Kiel, Germany
[3] Univ Western Ontario, Dept Comp Sci, London, ON N6A 5B7, Canada
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2005年 / 167卷 / 02期
基金：
加拿大自然科学与工程研究理事会;
关键词：
scheduling; job shop; controllable processing times; approximation schemes;
D O I：
10.1016/j.ejor.2004.03.025
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper we study the job shop scheduling problem under the assumption that the jobs have controllable processing times. The fact that the jobs have controllable processing times means that it is possible to reduce the processing time of the jobs by paying a certain cost. We consider two models of controllable processing times: continuous and discrete. For both models we present polynomial time approximation schemes when the number of machines and the number of operations per job are fixed. (c) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：297 / 319
页数：23
相关论文
共 50 条
  • [1] Approximation schemes for parallel machine scheduling problems with controllable processing times
    Jansen, K
    Mastrolilli, M
    COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (10) : 1565 - 1581
  • [2] Proactive scheduling research on job shop with stochastically controllable processing times
    Xiao, Shichang
    Sun, Shudong
    Yang, Hongan
    Xibei Gongye Daxue Xuebao/Journal of Northwestern Polytechnical University, 2014, 32 (06): : 929 - 936
  • [3] Efficient scheduling of a stochastic no-wait job shop with controllable processing times
    Aschauer, Alexander
    Roetzer, Florian
    Steinboeck, Andreas
    Kugi, Andreas
    EXPERT SYSTEMS WITH APPLICATIONS, 2020, 162
  • [4] A decomposition approach to job-shop scheduling problem with discretely controllable processing times
    LAFON Pascal
    Science China(Technological Sciences), 2011, (05) : 1240 - 1248
  • [5] A decomposition approach to job-shop scheduling problem with discretely controllable processing times
    Niu GangGang
    Sun ShuDong
    Lafon, Pascal
    Yang HongAn
    SCIENCE CHINA-TECHNOLOGICAL SCIENCES, 2011, 54 (05) : 1240 - 1248
  • [6] Job shop scheduling with unit, processing times
    Bansal, Nikhil
    Kimbrel, Tracy
    Sviridenko, Maxim
    PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2005, : 207 - 214
  • [7] Job shop scheduling with unit processing times
    Bansal, Nikhil
    Kimbrel, Tracy
    Sviridenko, Maxim
    MATHEMATICS OF OPERATIONS RESEARCH, 2006, 31 (02) : 381 - 389
  • [8] A decomposition approach to job-shop scheduling problem with discretely controllable processing times
    LAFON Pascal
    Science China(Technological Sciences), 2011, 54 (05) : 1240 - 1248
  • [9] A decomposition approach to job-shop scheduling problem with discretely controllable processing times
    GangGang Niu
    ShuDong Sun
    Pascal Lafon
    HongAn Yang
    Science China Technological Sciences, 2011, 54 : 1240 - 1248
  • [10] Robust scheduling for flexible job-shop problems with uncertain processing times
    Li, Wan-Ling
    Murata, Tomohiro
    Fazli Bin Md Fauadi, Muhammad Hafidz
    IEEJ Transactions on Electronics, Information and Systems, 2015, 135 (06) : 713 - 720
12345