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 条
  • [31] Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs
    Lin, BMT
    Jeng, AAK
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2004, 91 (02) : 121 - 134
  • [32] Single machine scheduling with deteriorating jobs
    Jiang, Shujun
    Tang, Lixin
    2008 4TH INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS, NETWORKING AND MOBILE COMPUTING, VOLS 1-31, 2008, : 7654 - 7657
  • [33] Uniform parallel-machine scheduling to minimize the number of tardy jobs in the MapReduce system
    Zheng, Feifeng
    Huang, Jidan
    PROCEEDINGS OF THE 2019 INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND SYSTEMS MANAGEMENT (IESM 2019), 2019, : 124 - 129
  • [34] Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
    Hung, Hui-Chih
    Lin, Bertrand M. T.
    Posner, Marc E.
    Wei, Jun-Min
    JOURNAL OF SCHEDULING, 2019, 22 (04) : 413 - 431
  • [35] Unrelated parallel-machine scheduling with deteriorating maintenance activities to minimize the total completion time
    Li-Yan Wang
    Xue Huang
    Ping Ji
    En-Min Feng
    Optimization Letters, 2014, 8 : 129 - 134
  • [36] Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan
    Li, Shisheng
    Yuan, Jinjiang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 19 (01) : 84 - 93
  • [37] Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan
    Shisheng Li
    Jinjiang Yuan
    Journal of Combinatorial Optimization, 2010, 19 : 84 - 93
  • [38] Unrelated parallel-machine scheduling with deteriorating maintenance activities to minimize the total completion time
    Wang, Li-Yan
    Huang, Xue
    Ji, Ping
    Feng, En-Min
    OPTIMIZATION LETTERS, 2014, 8 (01) : 129 - 134
  • [39] A note on single-machine makespan scheduling with deteriorating jobs and scheduled maintenance
    Lee, Wen-Chiung
    JOURNAL OF INFORMATION & OPTIMIZATION SCIENCES, 2007, 28 (03): : 469 - 477
  • [40] PARALLEL-MACHINE SCHEDULING IN SHARED MANUFACTURING
    Ji, Min
    Ye, Xinna
    Qian, Fangyao
    Cheng, T. C. E.
    Jiang, Yiwei
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2022, 18 (01) : 681 - 691
12345