A SEQUENCING PROBLEM WITH RELEASE DATES AND CLUSTERED JOBS

被引：9

作者：

POSNER, ME

机构：

[1] New York Univ, New York, NY, USA, New York Univ, New York, NY, USA

来源：

MANAGEMENT SCIENCE | 1986年 / 32卷 / 06期

关键词：

COMPUTER PROGRAMMING - Algorithms - MANAGEMENT SCIENCE;

D O I：

10.1287/mnsc.32.6.731

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper considers a one-machine scheduling problem where the objective is to minimize the sum of weighted completion times subject to release dates. A polynomial time algorithm is developed for the case when the jobs are clustered. The jobs in each cluster must be processed sequentially and the clusters are ordered. The insights developed are used in an efficient heuristic for the weighted completion time problem without clusters. Also, a class of release date problems is described for which the heuristic finds an optimal solution.

引用

页码：731 / 738

页数：8

共 17 条

[1] OPTIMAL LINEAR ORDERING
ADOLPHSON, D
HU, TC
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1973, 25 (03) : 403 - 423
[2] Adolphson D. L., 1977, SIAM Journal on Computing, V6, P40, DOI 10.1137/0206002
[3] N-1-FBAR DYNAMIC DETERMINISTIC PROBLEMS
CHANDRA, R
[J]. NAVAL RESEARCH LOGISTICS, 1979, 26 (03) : 537 - 544
[4] ON SCHEDULING WITH READY TIMES TO MINIMIZE MEAN FLOW TIME
DEOGUN, JS
[J]. COMPUTER JOURNAL, 1983, 26 (04) : 320 - 328
[5] SEQUENCING JOBS WITH UNEQUAL READY TIMES TO MINIMIZE MEAN FLOW TIME
DESSOUKY, MI
DEOGUN, JS
[J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (01) : 192 - 202
[6] AN ALGORITHM FOR SINGLE-MACHINE SEQUENCING WITH RELEASE DATES TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME
HARIRI, AMA
POTTS, CN
[J]. DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) : 99 - 109
[7] SINGLE-MACHINE JOB SEQUENCING WITH TREELIKE PRECEDENCE ORDERING AND LINEAR DELAY PENALTIES
HORN, WA
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1972, 23 (02) : 189 - &
[8] ALGORITHM FOR ONE MACHINE JOB SEQUENCING WITH PRECEDENCE CONSTRAINTS
ICHIMORI, T
ISHII, H
NISHIDA, T
[J]. JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 1981, 24 (02) : 159 - 169
[9] Lawler EL., 1978, ANN DISCRETE MATH, V2, P75
[10] 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 2 →