SCHEDULING JOBS ON A SINGLE-MACHINE WITH RELEASE DATES, DELIVERY TIMES AND CONTROLLABLE PROCESSING TIMES - WORST-CASE ANALYSIS

被引：27
|
作者：
ZDRZALKA, S
机构：
[1] Technical University of Wrocław, Institute of Engineering Cybernetics, 50-372 Wrocław
来源：
OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 09期
关键词：
SCHEDULING; PROGRAMMING; ALGORITHMS; HEURISTIC;
D O I：
10.1016/0167-6377(91)90071-V
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The paper deals with the problem of scheduling jobs on a single machine, in which each job has a release date, a delivery time and a controllable processing time, having its own associated linearly varying cost. An approximation algorithm for minimizing the overall schedule cost is provided which has the performance guarantee of rho + 1/2, where rho is the worst-case performance bound of a procedure used in the proposed algorithm for solving the pure sequencing problem. The best approximation procedure known has rho = 4/3
引用
收藏
页码：519 / 523
页数：5
相关论文
共 50 条
  • [21] Single-Machine Scheduling with Release Times and Tails
    Nodari Vakhania
    Annals of Operations Research, 2004, 129 : 253 - 271
  • [22] Single-machine scheduling with release times and tails
    Vakhania, N
    ANNALS OF OPERATIONS RESEARCH, 2004, 129 (1-4) : 253 - 271
  • [23] Single-machine scheduling with convex resource dependent processing times and deteriorating jobs
    Wang, Xue-Ru
    Wang, Jian-Jun
    APPLIED MATHEMATICAL MODELLING, 2013, 37 (04) : 2388 - 2393
  • [24] Single CNC machine scheduling with controllable processing times and multiple due dates
    Atan, Mehmet Oguz
    Akturk, M. Selim
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2008, 46 (21) : 6087 - 6111
  • [25] Single machine scheduling problem with controllable processing times and resource dependent release times
    Choi, Byung-Cheon
    Yoon, Suk-Hun
    Chung, Sung-Jin
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 181 (02) : 645 - 653
  • [26] Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines
    Shioura, Akiyoshi
    Shakhlevich, Natalia V.
    Strusevich, Vitaly A.
    INFORMS JOURNAL ON COMPUTING, 2016, 28 (01) : 148 - 161
  • [27] SLACK DUE WINDOW ASSIGNMENT SCHEDULING IN THE SINGLE-MACHINE WITH CONTROLLABLE PROCESSING TIMES
    Sun, Xinyu
    Geng, Xin-na
    Wang, Jiayin
    Pan, Lei
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2024, 20 (01) : 15 - 35
  • [28] Scheduling with controllable release dates and processing times: Makespan minimization
    Cheng, T. C. Edwin
    Kovalyov, Mikhail Y.
    Shakhlevich, Natalia V.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 175 (02) : 751 - 768
  • [29] Rescheduling rework jobs on single-machine of original jobs with release times
    Guo, Yandong
    Huang, Min
    Wang, Qing
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 2015, 30 (06): : 473 - 480
  • [30] Single-machine scheduling with release times, deadlines, setup times, and rejection
    de Weerdt, Mathijs
    Baart, Robert
    He, Lei
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 291 (02) : 629 - 639
12345