Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. (English) Zbl 1391.90236
Summary: This research analyzes the problem of scheduling a set of \(n\) jobs with arbitrary job sizes and non-zero ready times on a set of \(m\) unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C27 | Combinatorial optimization |
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Xu, R.; Chen, H.; Li, X., A bi-objective scheduling problem on batch machines via a Pareto-based ant colony system, Int J Prod Econ, 145, 1, 371-386, (2013) |
| [2] | Mathirajan, M.; Sivakumar, A., Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families, Int J Adv Manuf Technol, 28, 9-10, 1038-1047, (2006) |
| [3] | Mönch, L.; Fowler, J. W.; Dauzère-Pérès, S.; Mason, S. J.; Rose, O., A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations, J Sched, 14, 6, 583-599, (2011) |
| [4] | Mazumdar, C. S.; Mathirajan, M.; Gopinath, R.; Sivakumar, A., Tabu search methods for scheduling a burn-in oven with non-identical job sizes and secondary resource constraints, Int J Oper Res, 3, 1-2, 119-139, (2008) · Zbl 1254.90074 |
| [5] | Mönch, L.; Fowler, J. W.; Mason, S., Production planning and control for semiconductor wafer fabrication facilities: modeling, analysis, and systems, vol. 52, (2012), Springer Science & Business Media Norfolk, VA, USA |
| [6] | Jia, Z.-h.; Li, K.; Leung, J. Y.-T., Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities, Int J Prod Econ, 169, 1-10, (2015) |
| [7] | Garey MR, Johnson DS. Computers and intractability; a guide to the theory of np-completeness. Tech report; 1979. · Zbl 0411.68039 |
| [8] | Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes, Int J Prod Res, 32, 7, 1615-1635, (1994) · Zbl 0906.90095 |
| [9] | Dupont, L.; Dhaenens-Flipo, C., Minimizing the makespan on a batch machine with non-identical job sizesan exact procedure, Comput Oper Res, 29, 7, 807-819, (2002) · Zbl 0995.90081 |
| [10] | Damodaran, P.; Chang, P.-Y., Heuristics to minimize makespan of parallel batch processing machines, Int J Adv Manuf Technol, 37, 9-10, 1005-1013, (2008) |
| [11] | Bramel, J.; Simchi-Levi, D., The logic of logisticstheory, algorithms and applications for logistics management, J Oper Res Soc, 49, 9, 1016-1017, (1998) |
| [12] | Damodaran, P.; Vélez-Gallego, M. C., A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times, Expert Syst Appl, 39, 1, 1451-1458, (2012) |
| [13] | Li, X.; Huang, Y.; Tan, Q.; Chen, H., Scheduling unrelated parallel batch processing machines with non-identical job sizes, Comput Oper Res, 40, 12, 2983-2990, (2013) · Zbl 1348.90285 |
| [14] | Mathirajan, M.; Sivakumar, A., A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor, Int J Adv Manuf Technol, 29, 9-10, 990-1001, (2006) |
| [15] | Lee, C.-Y.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Oper Res, 40, 4, 764-775, (1992) · Zbl 0759.90046 |
| [16] | Brucker, P.; Gladky, A.; Hoogeveen, H.; Kovalyov, M. Y.; Potts, C. N.; Tautenhahn, T.; Van De Velde, S. L., Scheduling a batching machine, J Sched, 1, 1, 31-54, (1998) · Zbl 0909.90172 |
| [17] | Balasubramanian, H.; Mönch, L.; Fowler, J.; Pfund, M., Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness, Int J Prod Res, 42, 8, 1621-1638, (2004) · Zbl 1099.90537 |
| [18] | Wang, J.-Q.; Leung, J. Y.-T., Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan, Int J Prod Econ, 156, 325-331, (2014) |
| [19] | Lausch S, Mönch L. Metaheuristic approaches for scheduling jobs on parallel batch processing machines. In: Heuristics, metaheuristics and approximate methods in planning and scheduling. Springer, Norfolk, VA, USA; 2016. p. 187-207. |
| [20] | Chang, P.-Y.; Damodaran, P.; Melouk, S., Minimizing makespan on parallel batch processing machines, Int J Prod Res, 42, 19, 4211-4220, (2004) |
| [21] | Kashan, A. H.; Karimi, B.; Jenabi, M., A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes, Comput Oper Res, 35, 4, 1084-1098, (2008) · Zbl 1180.90126 |
| [22] | Cheng, B.; Wang, Q.; Yang, S.; Hu, X., An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes, Appl Soft Comput, 13, 2, 765-772, (2013) |
| [23] | Jia, Z.-h.; Leung, J. Y.-T., A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes, Eur J Oper Res, 240, 3, 649-665, (2015) · Zbl 1338.90167 |
| [24] | Cheng, B.; Yang, S.; Hu, X.; Chen, B., Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes, Appl Math Model, 36, 7, 3161-3167, (2012) · Zbl 1252.90022 |
| [25] | Koh, S.-G.; Koo, P.-H.; Ha, J.-W.; Lee, W.-S., Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families, Int J Prod Res, 42, 19, 4091-4107, (2004) · Zbl 1060.90643 |
| [26] | Jia, Z.-h.; Wang, C.; Leung, J. Y.-T., An aco algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families, Appl Soft Comput, 38, 395-404, (2016) |
| [27] | Damodaran, P.; Diyadawagamage, D. A.; Ghrayeb, O.; Vélez-Gallego, M. C., A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines, Int J Adv Manuf Technol, 58, 9-12, 1131-1140, (2012) |
| [28] | Uzsoy, R., Scheduling batch processing machines with incompatible job families, Int J Prod Res, 33, 10, 2685-2708, (1995) · Zbl 0910.90180 |
| [29] | 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, Comput Oper Res, 32, 11, 2731-2750, (2005) · Zbl 1071.90019 |
| [30] | 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, Comput Oper Res, 34, 10, 3016-3028, (2007) · Zbl 1185.90086 |
| [31] | Chiang, T.-C.; Cheng, H.-C.; Fu, L.-C., A memetic algorithm for minimizing total weighted tardiness on parallel batch machines with incompatible job families and dynamic job arrival, Comput Oper Res, 37, 12, 2257-2269, (2010) · Zbl 1231.90183 |
| [32] | Klemmt A, Weigert G, Almeder C, Mönch L. A comparison of mip-based decomposition techniques and vns approaches for batch scheduling problems. In: Proceedings of the 2009 winter simulation conference (WSC). IEEE, Austin, Texas, USA; 2009. p. 1686-94. |
| [33] | Bilyk, A.; Mönch, L.; Almeder, C., Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics, Comput Ind Eng, 78, 175-185, (2014) |
| [34] | Wang, H.-M.; Chou, F.-D., Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics, Expert Syst Appl, 37, 2, 1510-1521, (2010) |
| [35] | Chung, S.; Tai, Y.; Pearn, W., Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes, Int J Prod Res, 47, 18, 5109-5128, (2009) · Zbl 1198.90174 |
| [36] | Damodaran, P.; Velez-Gallego, M. C., Heuristics for makespan minimization on parallel batch processing machines with unequal job ready times, Int J Adv Manuf Technol, 49, 9-12, 1119-1128, (2010) |
| [37] | Damodaran, P.; Vélez-Gallego, M. C.; Maya, J., A grasp approach for makespan minimization on parallel batch processing machines, J Intell Manuf, 22, 5, 767-777, (2011) |
| [38] | Ozturk, O.; Espinouse, M.-L.; Mascolo, M. D.; Gouin, A., Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates, Int J Prod Res, 50, 20, 6022-6035, (2012) |
| [39] | Gokhale, R.; Mathirajan, M., Minimizing total weighted tardiness on heterogeneous batch processors with incompatible job families, Int J Adv Manuf Technol, 70, 9-12, 1563-1578, (2014) |
| [40] | Abedi, M.; Seidgar, H.; Fazlollahtabar, H.; Bijani, R., Bi-objective optimisation for scheduling the identical parallel batch-processing machines with arbitrary job sizes, unequal job release times and capacity limits, Int J Prod Res, 53, 6, 1680-1711, (2015) |
| [41] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. R., Optimization and approximation in deterministic sequencing and schedulinga survey, Ann Discret Math, 5, 287-326, (1979) · Zbl 0411.90044 |
| [42] | Dupont, L.; Ghazvini, F. J., Minimizing makespan on a single batch processing machine with non-identical job sizes, J Eur Des Syst Autom, 32, 4, 431-440, (1998) |
| [43] | Coffman Jr EG, Garey MR, Johnson DS. Approximation algorithms for bin-packing: an updated survey. In: Algorithm design for computer system design. Springer, New York, USA; 1984. p. 49-106. · Zbl 0558.68062 |
| [44] | Lin, Y.-K.; Lin, C.-W., Dispatching rules for unrelated parallel machine scheduling with release dates, Int J Adv Manuf Technol, 67, 1-4, 269-279, (2013) |
| [45] | Glass, C.; Potts, C.; Shade, P., Unrelated parallel machine scheduling using local search, Math Comput Model, 20, 2, 41-52, (1994) · Zbl 0810.90066 |
| [46] | Ghirardi, M.; Potts, C. N., Makespan minimization for scheduling unrelated parallel machinesa recovering beam search approach, Eur J Oper Res, 165, 2, 457-467, (2005) · Zbl 1066.90029 |
| [47] | Lin, Y.-K.; Pfund, M. E.; Fowler, J. W., Processing time generation schemes for parallel machine scheduling problems with various correlation structures, J Sched, 17, 6, 569-586, (2014) · Zbl 1305.90215 |
| [48] | Fanjul-Peyro, L.; Ruiz, R., Iterated greedy local search methods for unrelated parallel machine scheduling, Eur J Oper Res, 207, 1, 55-69, (2010) · Zbl 1205.90121 |
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.
