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 条
12345