Decomposition heuristics for minimizing earliness-tardiness on parallel burn-in ovens with a common due date

被引：28

作者：

Institut für Wirtschaftsinformatik, Technische Universität Ilmenau, Germany ^{[1
]}

不详 ^{[2
]}

机构：

[1] Institut für Wirtschaftsinformatik, Technische Universität Ilmenau

[2] Institut für Angewandte Informatik, Technische Universität Dresden

来源：

Comp. Oper. Res. | 2007年 / 11卷 / 3380-3396期

基金：

中国国家自然科学基金;

关键词：

Common due date; Earliness-tardiness; Heuristics; Parallel burn-in ovens; Scheduling;

D O I：

10.1016/j.cor.2006.02.003

中图分类号：

学科分类号：

摘要：

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness-tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme. © 2006 Elsevier Ltd. All rights reserved.

引用

页码：3380 / 3396

页数：16

共 28 条

[1] Uzsoy R., Lee C.Y., Martin-Vega L.A., A review of production planning and scheduling models in the semiconductor industry. Part II: shop floor control, IIE Transactions, 26, pp. 44-55, (1994)
[2] Lee C.Y., Uzsoy R., Martin-Vega L.A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, pp. 764-775, (1992)
[3] Sung C.S., Choung Y.I., Minimizing makespan on a single burn-in oven in semiconductor manufacturing, European Journal of Operational Research, 120, pp. 559-574, (2000)
[4] Kanet J.J., Minimizing the average deviation of job completion times about a common due date, Naval Research Logistics Quarterly, 28, pp. 643-651, (1981)
[5] Hall N.G., Posner M.E., Earliness-tardiness scheduling problem I: weighted deviation of completion times about a common due date, Operations Research, 39, pp. 836-846, (1991)
[6] Potts C.N., Kovalyov M.Y., Scheduling with batching: a review, European Journal of Operational Research, 120, pp. 228-249, (2000)
[7] Chandru V., Lee C.Y., Uzsoy R., Minimizing total completion time on batch processing machines, International Journal of Production Research, 31, pp. 2097-2121, (1993)
[8] Chandru V., Lee C.Y., Uzsoy R., Minimizing total completion time on a batch processing machine with job families, Operations Research Letters, 13, pp. 61-65, (1993)
[9] Uzsoy R., Scheduling a single batch processing machine with non-identical job sizes, International Journal of Production Research, 32, pp. 1615-1635, (1994)
[10] Li C.L., Lee C.Y., Scheduling with agreeable release times and due dates on a batch processing machine, European Journal of Operational Research, 96, pp. 564-569, (1997)

← 1 2 3 →