Minimizing the makespan on a batch machine with non-identical job sizes: An exact procedure. (English) Zbl 0995.90081
Summary: A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems we use this enumeration scheme as a heuristic method.
MSC:
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Ikura, Y.; Gimple, M., Efficient scheduling algorithms for a single batch processing machine, Operations Research Letters, 5, 61-65 (1986) · Zbl 0594.90045 |
| [2] | 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 |
| [3] | 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 |
| [4] | Ahmadi, J. H.; Ahmadi, R. H.; Dasu, S.; Tang, C. S., Batching and scheduling jobs on batch and discrete processors, Operations Research, 40, 750-763 (1992) · Zbl 0758.90042 |
| [5] | Brucker, P.; Gladky, A.; Hoogeveen, H.; Kovalyov, M. Y.; Potts, C.; Tautenhahn, T.; Van De Velde, S., Scheduling a batching machine, Journal of Scheduling, 1, 31-55 (1998) · Zbl 0909.90172 |
| [6] | Chandru, V.; Lee, C. Y.; Uzsoy, R., Minimizing total completion time on batch processing machines, International Journal of Production Research, 31, 2097-2121 (1993) |
| [7] | Dupont, L.; Jolai Ghazvini, F., Branch and bound method for single batch processing machine with mean flow time criteria, International Journal of Industrial Engineering: Practice and Theory, 4, 197-203 (1997) |
| [8] | Uzsoy, R.; Yang, Y., Minimizing total weighted completion time on a single batch processing machine, Production and Operations Management, 6, 57-73 (1997) |
| [9] | Lee, C. Y.; Uzsoy, R., Minimizing makespan on a single batch processing machine with dynamic job arrivals, International Journal of Production Research, 1, 219-236 (1999) · Zbl 0939.90537 |
| [10] | Kempf, K. G.; Uzsoy, R.; Wang, C.-. S., Scheduling a single batch processing machine with secondary resource constraints, Journal of Manufacturing Systems, 17, 37-51 (1998) |
| [11] | Uzsoy, R., Scheduling batch processing machines with incompatible job families, International Journal of Production Research, 33, 2685-2708 (1995) · Zbl 0910.90180 |
| [12] | Mehta, S. V.; Uzsoy, R., Minimizing total tardiness on a batch processing machine with incompatible job families, IIE Transactions on Scheduling and Logistics, 31, 165-178 (1998) |
| [13] | 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 |
| [14] | Hochbaum, D. S.; Landy, D., Scheduling semiconductor burn-in operations to minimize total flowtime, Operations Research, 45, 874-885 (1997) · Zbl 0895.90116 |
| [15] | Kubiak W, Jolai Ghazvini F. Minimizing earliness/tardiness criteria on a single batch processing machine with families of jobs. Proceeding of the 2nd Annual International Conference on Industrial Engineering, vol. 2, San Diego, California, USA, 12-15 November 1997. p. 785-90.; Kubiak W, Jolai Ghazvini F. Minimizing earliness/tardiness criteria on a single batch processing machine with families of jobs. Proceeding of the 2nd Annual International Conference on Industrial Engineering, vol. 2, San Diego, California, USA, 12-15 November 1997. p. 785-90. |
| [16] | Dobson G, Nambinadom RS. The batch loading and scheduling problem. Research Report, Simon School of Business Administration, University of Rochester, Rochester, NY, 1992.; Dobson G, Nambinadom RS. The batch loading and scheduling problem. Research Report, Simon School of Business Administration, University of Rochester, Rochester, NY, 1992. |
| [17] | Uzsoy, R., A single batch processing machine with non-identical job sizes, International Journal of Production Research, 32, 1615-1635 (1994) · Zbl 0906.90095 |
| [18] | Jolai Ghazvini, F.; Dupont, L., Minimizing mean flow time criteria on a single batch processing machine with non-identical job sizes, International Journal of Production Economics, 55, 273-280 (1998) |
| [19] | Dupont, L.; Jolai Ghazvini, F., Minimizing makespan on a single batch processing machine with non-identical job sizes, European Journal of Automation (JESA), 32, 431-440 (1998) |
| [20] | Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin-packing – an updated survey, (Ausiello, G.; Lucertini, M.; Serafini, P., Algorithm design for computer system design (1984), Springer: Springer New York), p49-106 · Zbl 0558.68062 |
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.
