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

被引：62

作者：

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
LAWLER, EL
[J]. 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 →