AN APPROXIMATION ALGORITHM FOR A SINGLE-MACHINE SCHEDULING PROBLEM WITH RELEASE TIMES, DELIVERY TIMES AND CONTROLLABLE PROCESSING TIMES

被引：6
|
作者：
NOWICKI, E
机构：
[1] Technical University of Wroclaw, Institute of Engineering Cybernetics, 50-372 Wroclaw
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1994年 / 72卷 / 01期
关键词：
SINGLE-MACHINE SCHEDULING; APPROXIMATION ALGORITHMS; WORST-CASE ANALYSIS;
D O I：
10.1016/0377-2217(94)90331-X
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
The paper deals with a single-machine scheduling problem with release times, delivery times and controllable job processing times. It is assumed that the cost of performing a job is a linear function of its processing time, and the total schedule cost to be minimized is the total processing cost plus maximum completion time cost. In consequence, the processing order of jobs and their processing times are decision variables. A (rho + 1/3)-approximation algorithm for the problem is provided, where rho is the worst-case performance bound of a procedure for solving the pure sequencing problem.
引用
收藏
页码：74 / 81
页数：8
相关论文
共 50 条
  • [41] Single-machine scheduling problem considering jobs'release times and flexible maintenances
    Li X.
    Si J.
    Yin C.
    Li Y.
    Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, 2023, 29 (02): : 581 - 592
  • [42] Single-machine bicriterion group scheduling with deteriorating setup times and job processing times
    Wang, Jian-Jun
    Liu, Ya-Jing
    APPLIED MATHEMATICS AND COMPUTATION, 2014, 242 : 309 - 314
  • [43] Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties
    Biskup, D
    Cheng, TCE
    ENGINEERING OPTIMIZATION, 1999, 31 (03) : 329 - 336
  • [44] A bicriterion single-machine scheduling problem with step-improving processing times
    Wu, Chin -Chia
    Lin, Win -Chin
    Azzouz, Ameni
    Xu, Jianyou
    Chiu, Yen -Lin
    Tsai, Yung -Wei
    Shen, Pengyi
    COMPUTERS & INDUSTRIAL ENGINEERING, 2022, 171
  • [45] A bicriterion single-machine scheduling problem with step-improving processing times
    Wu, Chin-Chia
    Lin, Win-Chin
    Azzouz, Ameni
    Xu, Jianyou
    Chiu, Yen-Lin
    Tsai, Yung-Wei
    Shen, Pengyi
    COMPUTERS & INDUSTRIAL ENGINEERING, 2022, 171
  • [46] An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times
    YE Qiang LIU Xinbao LIU Lin YANG Shanglin School of ManagementHefei University of TechnologyHefei China
    武汉理工大学学报, 2006, (S3) : 956 - 961
  • [47] An improved ant colony algorithm for a single-machine scheduling problem with setup times
    Ye Qiang
    Liu Xinbao
    Liu Lin
    Yang Shanglin
    1ST INTERNATIONAL SYMPOSIUM ON DIGITAL MANUFACTURE, VOLS 1-3, 2006, : 956 - 961
  • [48] A single machine scheduling problem with common due window and controllable processing times
    Liman, S. D.
    Panwalkar, S. S.
    Thongmee, S.
    Annals of Operations Research, (70):
  • [49] A single machine scheduling problem with common due window and controllable processing times
    Liman, SD
    Panwalkar, SS
    Thongmee, S
    ANNALS OF OPERATIONS RESEARCH, 1997, 70 (0) : 145 - 154
  • [50] A single machine scheduling problem with common due window and controllable processing times
    Surya D. Liman
    Shrikant S. Panwalkar
    Sansern Thongmee
    Annals of Operations Research, 1997, 70 : 145 - 154
12345