PREEMPTIVE SCHEDULING OF A SINGLE-MACHINE TO MINIMIZE MAXIMUM COST SUBJECT TO RELEASE DATES AND PRECEDENCE CONSTRAINTS

被引：65
作者：
BAKER, KR
LAWLER, EL
LENSTRA, JK
KAN, AHGR
机构：
[1] UNIV CALIF BERKELEY,BERKELEY,CA 94720
[2] MATH CENTRUM,1098 SJ AMSTERDAM,NETHERLANDS
[3] ERASMUS UNIV,3000 DR ROTTERDAM,NETHERLANDS
来源：
OPERATIONS RESEARCH | 1983年 / 31卷 / 02期
关键词：
D O I：
10.1287/opre.31.2.381
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
Suppose n jobs are to be processed on a single machine, subject to release dates and precedence constraints. The problem is to find a preemptive schedule which minimizes the maximum job completion cost. The authors present an O(n**2) algorithm for this problem, generalizing previous results of E. L. Lawler.
引用
收藏
页码：381 / 386
页数：6
相关论文
共 5 条
[1]  
Garey M. R., 1977, SIAM Journal on Computing, V6, P416, DOI 10.1137/0206029
[2]  
Graham R. L., 1979, Discrete Optimisation, P287
[3]  
Lageweg B.J., 1976, STAT NEERL, V30, P25
[4]   OPTIMAL SEQUENCING OF A SINGLE MACHINE SUBJECT TO PRECEDENCE CONSTRAINTS [J].
LAWLER, EL .
MANAGEMENT SCIENCE SERIES A-THEORY, 1973, 19 (05) :544-546
[5]  
Lenstra J.K., 1977, ANN DISCRETE MATH, V1, P343, DOI [/10.1016/S0167-5060(08)70743-X, DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]
1