A note on parallel-machine scheduling with deteriorating jobs

被引：6
|
作者：
Jeng, A. A. K.
Lin, B. M. T. [1 ]
机构：
[1] Natl Chiao Tung Univ, Dept Informat & Finance Management, Hsinchu 300, Taiwan
[2] Natl Chiao Tung Univ, Dept Comp & Informat Sci, Hsinchu 300, Taiwan
来源：
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 2007年 / 58卷 / 06期
关键词：
parallel-machine scheduling; time-dependent processing time; lower bound;
D O I：
10.1057/palgrave.jors.2602208
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider a parallel-machine scheduling problem of minimizing the total completion time. The processing time of a job is a linear function of its starting time and deterioration rate. This problem is known to be NP-hard, even for the case with two machines. In this note, we generalize an existing lower bound for the two-machine case to the general case with an arbitrary number of machines. Despite the generalization concerning machine number, our bound has one extra term that makes our bound tighter than the existing one.
引用
收藏
页码：824 / 826
页数：3
相关论文
共 50 条
  • [21] Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs
    Lalla-Ruiz, Eduardo
    Voss, Stefan
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 255 (01) : 21 - 33
  • [22] Single machine parallel-batch scheduling with deteriorating jobs
    Qi, Xianglai
    Zhou, Shiguo
    Yuan, Jinjiang
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (8-10) : 830 - 836
  • [23] Single-Machine and Parallel-Machine Parallel-Batching Scheduling Considering Deteriorating Jobs, Various Group, and Time-Dependent Setup Time
    Liao, Baoyu
    Pei, Jun
    Yang, Shanlin
    Pardalos, Panos M.
    Lu, Shaojun
    INFORMATICA, 2018, 29 (02) : 281 - 301
  • [24] Precedence constrained parallel-machine scheduling of position-dependent jobs
    Przybylski, Bartomiej
    OPTIMIZATION LETTERS, 2017, 11 (07) : 1273 - 1281
  • [25] Precedence constrained parallel-machine scheduling of position-dependent jobs
    Bartłomiej Przybylski
    Optimization Letters, 2017, 11 : 1273 - 1281
  • [26] Unrelated parallel-machine scheduling problems with aging effects and deteriorating maintenance activities
    Hsu, Chou-Jung
    Ji, Min
    Guo, Jia-Yuarn
    Yang, Dar-Li
    INFORMATION SCIENCES, 2013, 253 : 163 - 169
  • [27] Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs
    Mazdeh, Mohammad Mahdavi
    Zaerpour, Farzad
    Zareei, Abalfazl
    Hajinezhad, Ali
    APPLIED MATHEMATICAL MODELLING, 2010, 34 (06) : 1498 - 1510
  • [28] A note on "On three-machine flow shop scheduling with deteriorating jobs"
    Jafari, Abbas-Ali
    Khademi-Zare, Hassan
    Lotfi, M. M.
    Tavakkoli-Moghaddam, Reza
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2017, 191 : 250 - 252
  • [29] Parallel machine scheduling of deteriorating jobs by modified steepest descent search
    Gawiejnowicz, Stanislaw
    Kurc, Wieslaw
    Pankowska, Lidia
    PARALLEL PROCESSING AND APPLIED MATHEMATICS, 2006, 3911 : 116 - 123
  • [30] Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
    Hui-Chih Hung
    Bertrand M. T. Lin
    Marc E. Posner
    Jun-Min Wei
    Journal of Scheduling, 2019, 22 : 413 - 431
12345