ROLLING HORIZON ALGORITHMS FOR A SINGLE-MACHINE DYNAMIC SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES

被引：155

作者：

OVACIK, IM ^{[1
]}

UZSOY, R ^{[1
]}

机构：

[1] PURDUE UNIV,SCH IND ENGN,1287 GRISSOM HALL,W LAFAYETTE,IN 47907

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1994年 / 32卷 / 06期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1080/00207549408956998

中图分类号：

T [工业技术];

学科分类号：

08 [工学];

摘要：

We present a family of rolling horizon heuristics to minimize maximum lateness on a single machine in the presence of sequence-dependent setup times. This problem occurs as a subproblem in a decomposition procedure for more complicated job shop scheduling problems. The procedures solve a sequence of subproblems to optimality with a branch and bound algorithm and implements only part of the solution obtained. The size and number of the subproblems are controlled by algorithm parameters. Extensive computational experiments show that these procedures outperform myopic dispatching rules by an order of magnitude, both on average and in the worst case, in very reasonable computation times.

引用

页码：1243 / 1263

页数：21

共 29 条

[1]

Adams J., Balas E., Zawack D., The shifting bottleneck procedure for job*shop scheduling, Management Science, 34, pp. 391-401, (1988)

[2]

Balas E., Toth P., Branch and bound methods, The Traveling Salesman Problem, (1985)

[3]

Baker K.R., Introduction to Sequencing and Scheduling, (1974)

[4]

Baker K.R., Su Z.S., Sequencing with due dates and early start times to minimize maximum tardiness, Naval Research Logistics Quarterly, 21, pp. 171-176, (1974)

[5]

Bhaskaran K., Pinedo M., Dispatching, Handbook of Industrial Engineering, (1991)

[6]

Carlier J., The one-machine scheduling problem, European Journal of Operational Research, 11, pp. 42-47, (1982)

[7]

Inc C., Short Interval Scheduling System Users Manual, Internal Publication, (1988)

[8]

Fowler J.W., Hogg G.L., Phillips D.T., Control of multiproduct bulk service diffusion/oxidation processes, HE Transactions on Scheduling and Logistics, 24, pp. 84-96, (1992)

[9]

Garky M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP Completeness, (1979)

[10]

Glassey C.R., Weng W.W., Dynamic batching heuristic for simultaneous processing, IEEE Transaction on Semiconductor Manufacturing, 4, pp. 77-82, (1991)

← 1 2 3 →