The constrained minimum weighted sum of job completion times problem

被引：6
|
作者：
Levin, Asaf [1 ]
Woeginger, Gerhard J.
机构：
[1] Hebrew Univ Jerusalem, Dept Stat, IL-91905 Jerusalem, Israel
[2] Univ Twente, Dept Math, NL-7500 AE Enschede, Netherlands
[3] Tech Univ Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands
来源：
MATHEMATICAL PROGRAMMING | 2006年 / 108卷 / 01期
关键词：
scheduling; combinatorial optimization; approximation scheme;
D O I：
10.1007/s10107-005-0691-3
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We consider the problem of minimizing the weighted sum of job completion times on a single machine (subject to certain job weights) with an additional side constraint on the weighted sum of job completion times (with respect to different job weights). This problem is NP-hard, and we provide a polynomial time approximation scheme for this problem. Our method is based on Lagrangian relaxation mixed with carefully guessing the positions of certain jobs in the schedule.
引用
收藏
页码：115 / 126
页数：12
相关论文
共 50 条
  • [1] The constrained minimum weighted sum of job completion times problem
    Levin, A
    Woeginger, GJ
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2004, 3064 : 298 - 307
  • [2] The constrained minimum weighted sum of job completion times problem
    Asaf Levin
    Gerhard J. Woeginger
    Mathematical Programming, 2006, 108 : 115 - 126
  • [3] Truthfulness for the Sum of Weighted Completion Times
    Angel, Eric
    Bampis, Evripidis
    Pascual, Fanny
    Thibault, Nicolas
    COMPUTING AND COMBINATORICS, COCOON 2016, 2016, 9797 : 15 - 26
  • [4] Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
    Chekuri, C
    Motwani, R
    DISCRETE APPLIED MATHEMATICS, 1999, 98 (1-2) : 29 - 38
  • [5] The optimality box in uncertain data for minimising the sum of the weighted job completion times
    Lai, Tsung-Chyan
    Sotskov, Yuri N.
    Egorova, Natalja G.
    Werner, Frank
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2018, 56 (19) : 6336 - 6362
  • [6] Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times
    Krim, Hanane
    Zufferey, Nicolas
    Potvin, Jean-Yves
    Benmansour, Rachid
    Duvivier, David
    JOURNAL OF SCHEDULING, 2022, 25 (01) : 89 - 105
  • [7] Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times
    Hanane Krim
    Nicolas Zufferey
    Jean-Yves Potvin
    Rachid Benmansour
    David Duvivier
    Journal of Scheduling, 2022, 25 : 89 - 105
  • [8] Scheduling to minimize the weighted sum of completion times
    Zhao, Chuan-Li
    Zhang, Qing-Ling
    Tang, Heng-Yong
    Dongbei Daxue Xuebao/Journal of Northeastern University, 2003, 24 (06): : 515 - 518
  • [9] Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance
    Krim, Hanane
    Benmansour, Rachid
    Duvivier, David
    Ait-Kadi, Daoud
    Hanafi, Said
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2020, 75 (01) : 291 - 320
  • [10] Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance
    Hanane Krim
    Rachid Benmansour
    David Duvivier
    Daoud Aït-Kadi
    Said Hanafi
    Computational Optimization and Applications, 2020, 75 : 291 - 320
12345