SOLVABLE CASE OF ONE-MACHINE SCHEDULING PROBLEM WITH READY AND DUE TIMES

被引：84

作者：

KISE, H ^{[1
]}

IBARAKI, T ^{[1
]}

MINE, H ^{[1
]}

机构：

[1] KYOTO UNIV,KYOTO 606,JAPAN

来源：

OPERATIONS RESEARCH | 1978年 / 26卷 / 01期

关键词：

D O I：

10.1287/opre.26.1.121

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Consideration of a class of n-job one-machine scheduling problems with ready time r(i), processing time p(i), and due time d(i) for each job i. Preemption is not allowed, and precedence constraints among jobs are not assumed. For this problem the authors show that there is a 0(n**2)-time algorithm to find a schedule that minimizes the number of tardy jobs, under the assumption that r(i) less than r(j) implies d(i) less than or equal to d(j).

引用

页码：121 / 126

页数：6

共 7 条

[1] Bricker P., 1977, ANN DISCRETE MATH, V1, P343, DOI [DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]
[2] Karp Richard M., 1972, COMPLEXITY COMPUTER, P85
[3] KISE H, 1975, 22 INT TIMS M KYOT
[4] ON SCHEDULING PROBLEMS WITH DEFERRAL COSTS
LAWLER, EL
[J]. MANAGEMENT SCIENCE, 1964, 11 (02) : 280 - 288
[5] LAWLER EL, 1976, REV FRANC AUTOMAT S, P27
[6] N JOB, ONE MACHINE SEQUENCING ALGORITHM FOR MINIMIZING THE NUMBER OF LATE JOBS
MOORE, JM
[J]. MANAGEMENT SCIENCE, 1968, 15 (01) : 102 - 109
[7] SIDNEY JB, 1973, S THEORY SCHEDULING, P393

← 1 →