MINIMIZING TOTAL COMPLETION-TIME ON BATCH PROCESSING MACHINES

被引：167

作者：

CHANDRU, V ^{[1
]}

LEE, CY ^{[1
]}

UZSOY, R ^{[1
]}

机构：

[1] INDIAN INST SCI,DEPT COMP SCI & AUTOMAT,BANGALORE 560012,KARNATAKA,INDIA

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1993年 / 31卷 / 09期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1080/00207549308956847

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

We study the problem of minimizing total completion time on single and parallel batch processing machines. A batch processing machine is one which can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. This problem is motivated by burnin operations in the final testing stage of semiconductor manufacturing and is expected to occur in other production environments. We provide an exact solution procedure for the single-machine problem and heuristic algorithms for both single and parallel machine problems. While the exact algorithms have limited applicability due to high computational requirements, extensive experiments show that the heuristics are capable of consistently obtaining near-optimal solutions in very reasonable CPU times.

引用

页码：2097 / 2121

页数：25

共 21 条

[11]

Lageweg B.J., Lawler E.L., Lenstra J.K., Rinnooy Kan A., Computer-Aided Complexity Classification of Deterministic Scheduling Problems, (1981)

[12]

Lawler E.L., Moore J.M., A functional equation and its application to resource allocation and sequencing problems, Management Science, 16, pp. 77-84, (1969)

[13]

Lee C.Y., Uzsoy R., A new dynamic programming algorithm for the parallel machine total weighted completion time problem, Operations Research Letters, 11, pp. 73-75, (1992)

[14]

Lee C.Y., Uzsoy R., Martin-Vega L.A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, pp. 764-775, (1992)

[15]

Lenstra J.K., Rinnooy Kan A., Brucker P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, pp. 343-362, (1977)

[16]

Medhi J., Waiting time distribution in a poisson queue with a general bulk service rule, Management Science, 21, pp. 777-782, (1975)

[17]

Neuts M., A general class of bulk queues with poisson input, Annals of Mathematical Statistics, 38, pp. 759-770, (1967)

[18]

Rothkopf M.H., Scheduling independent tasks on parallel processors, Management Science, 12, pp. 437-447, (1966)

[19]

Sahni S.K., Algorithms for scheduling independent tasks, Journal of the Acm, 23, pp. 116-127, (1976)

[20]

Sarin S., Ahn C., Bishop S., An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime, International Journal of Production Research, 26, pp. 1183-1191, (1988)

← 1 2 3 →