A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines. (English) Zbl 0953.90030
Summary: This paper considers a scheduling problem for a multi-stage flowshop of Batch Processing Machines (BPM) where each BPM can process a batch of jobs simultaneously so that all jobs contained in each batch are released together to the next machine after their processing. With respect to any regular measure of performance, several solution properties are characterized to exploit a problem reduction procedure for removing dominated machines. The reduction procedure is incorporated into two efficient heuristic solution algorithms for minimizing two corresponding regular measures of performance including ‘makespan’ and ‘sum of completion times’. Several numerical experiments show that the proposed reduction procedure contributes to remove many non-bottleneck machines for the two heuristics to generate good schedules.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 49M27 | Decomposition methods |
References:
| [1] | Ahmadi, J. H.; Ahmadi, R. H.; Dasu, S.; Tang, C. S., Batching and scheduling jobs on batch and discrete processors, Operations Research, 39, 750-763 (1992) · Zbl 0758.90042 |
| [2] | Chandru, V.; Lee, C. Y.; Uzsoy, R., Minimizing total completion time on a batch processing machine with job families, Operations Research Letters, 13, 61-65 (1993) · Zbl 0771.90054 |
| [3] | Chandru, V.; Lee, C. Y.; Uzsoy, R., Minimizing total completion time on batch processing machines, International Journal of Production Research, 31, 2097-2121 (1993) |
| [4] | Glassey, C. R.; Weng, W. W., Dynamic batching heuristic for simultaneous processing, IEEE Transactions on Semiconductor Manufacturing, 4, 77-82 (1991) |
| [5] | Hochbaum, D. S.; Landy, D., Scheduling semiconductor burn-in operations to minimize total flowtime, Operations Research, 45, 874-885 (1997) · Zbl 0895.90116 |
| [6] | Ignall, E.; Schrage, L. E., Application of the branch and bound technique to some flow-shop scheduling problems, Operations Research, 13, 400-412 (1965) |
| [7] | Ikura, Y.; Gimple, M., Scheduling algorithms for a single batch processing machine, Operations Research Letters, 5, 61-65 (1986) · Zbl 0594.90045 |
| [8] | Lee, C. Y.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, 764-775 (1992) · Zbl 0759.90046 |
| [9] | 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, 564-569 (1997) · Zbl 0929.90038 |
| [10] | Sung, C. S.; Yoon, S. H., Minimizing maximum completion time in a two-batch-processing-machine flowshop with dynamic arrivals allowed, Engineering Optimization, 28, 231-243 (1997) |
| [11] | Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes, International Journal of Production Research, 32, 1615-1635 (1994) · Zbl 0906.90095 |
| [12] | Webster, S.; Baker, K. R., Scheduling groups of jobs on a single machine, Operations Research, 43, 692-703 (1995) · Zbl 0857.90062 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
