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 条

[1]

Ahmadi J., Ahmadi R.H., Dasu S., Tang C.S., Batching and scheduling jobs on batch and discrete processors, Operations Research, 40, pp. 750-763, (1992)

[2]

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

[3]

Barnes J.W., Brennan J.J., An improved algorithm for scheduling jobs on identical machines, AIIE Transactions, 9, pp. 25-31, (1977)

[4]

Deb R.K., Serfozo R.F., Optimal control of batch service queues, Advances in Applied Probability, 5, pp. 340-361, (1973)

[5]

Eastman W.L., Even S., Isaacs I.M., Bounds for the optimal scheduling of n jobs on m processors, Management Science, 11, pp. 268-279, (1964)

[6]

Elmaghraby S.E., Park S.H., Scheduling jobs on a number of identical machines, AIIE Transactions, 6, pp. 1-13, (1974)

[7]

French S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job- Shop, (1982)

[8]

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

[9]

Ikura Y., Gimple M., Efficient scheduling algorithms for a single batch processing machine, Operations Research Letters, 5, pp. 61-65, (1986)

[10]

Kawaguchi T., Kyan S., Worst-case of an LRF schedule for the mean weighted flow time problem, SIAM Journal on Computing, 15, pp. 1119-1129, (1986)

← 1 2 3 →