Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes. (English) Zbl 1252.90022
Summary: We consider the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be \(2\) and (\(8/3-2/3 m\)) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | 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 |
| [2] | Zhang, G.; Cai, X.; Lee, C. Y.; Wang, C. K., Minimizing makespan on a single batch processing machine with nonidentical job sizes, Naval Research Logistics, 48, 226-240 (2001) · Zbl 1027.90041 |
| [3] | Kashan, A. H.; Karimi, B.; Fatemi Ghomi, S. M.T., Theoretical Computer Science, 410, 2754-2758 (2009) · Zbl 1177.90166 |
| [4] | Li, S.; Li, G.; Wang, X.; Liu, Q., Minimizing makespan on a single batch processing machine with release times and non-identical job sizes, Operations Research Letters, 33, 157-164 (2005) · Zbl 1099.90021 |
| [5] | Dupont, L.; Flipo, C. D., Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure, Computers & Operations Research, 29, 807-819 (2002) · Zbl 0995.90081 |
| [6] | Sevaux, M.; Peres, S. D., Genetic algorithms to minimize the weighted number of late jobs on a single machine, European Journal of Operational Research, 151, 2, 296-306 (2003) · Zbl 1053.90046 |
| [7] | A.H. Kashan, B. Karimi, F. Jolai, Minimizing makespan on a single batch-processing machine with non-identical job sizes: a hybrid genetic approach. Evolutionary computation in combinatorial optimization-6th European conference, 2006, Proceedings, Lecture notes in computer science 2006, 3906: 35-146.; A.H. Kashan, B. Karimi, F. Jolai, Minimizing makespan on a single batch-processing machine with non-identical job sizes: a hybrid genetic approach. Evolutionary computation in combinatorial optimization-6th European conference, 2006, Proceedings, Lecture notes in computer science 2006, 3906: 35-146. · Zbl 1095.90039 |
| [8] | Damodaran, P.; Manjeshwar, P. K.; Srihari, K., Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithm, International Journal of Production Economics, 103, 882-891 (2006) |
| [9] | Melouk, S.; Demodaran, P.; Chang, P. Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing, International Journal of Production Economics, 87, 141-147 (2004) |
| [10] | Parsa, N. R.; Karimi, B.; Kashan, A. H., A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes, Computers & Operations Research, 37, 1720-1730 (2010) · Zbl 1188.90105 |
| [11] | Azizoglu, M.; Webster, S., Scheduling a batch processing machine with incompatible job families, Computers & Industrial Engineering, 39, 325-335 (2001) |
| [12] | Jolai, F., Minimizing number of tardy jobs on a batch processing machine with incompatible job families, European Journal of Operational Research, 162, 184-190 (2005) · Zbl 1132.90326 |
| [13] | Koh, S.; Koo, P.; Kim, D.; Hur, W., Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families, International Journal of Production Economics, 98, 81-96 (2005) |
| [14] | Omar, M. K.; Teo, S. C., Minimizing the sum of earliness/tardiness in identical parallel machines schedule with incompatible job families: an improved MIP approach, Applied Mathematics and Computation, 181, 1008-1017 (2006) · Zbl 1119.68038 |
| [15] | Malve, S.; Uzsoy, R., A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families, Computers & Operational Research, 34, 3016-3028 (2007) · Zbl 1185.90086 |
| [16] | Mönch, L.; Balasubramanian, H.; Fowler, J. W.; Pfund, M. E., Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times, Computers & Operations Research, 32, 2731-2750 (2005) · Zbl 1071.90019 |
| [17] | Mönch, L.; Zimmermann, J.; Otto, P., Machine learning techniques for scheduling jobs with incompatible families and unequal ready times on parallel batch machines, Engineering Applications of Artificial Intelligence, 19, 235-245 (2006) |
| [18] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annuals of Discrete Mathematics., 5, 287-326 (1979) · Zbl 0411.90044 |
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.
