This paper considers the minimization of makespan in the unrelated parallel batch processing machines scheduling problem with considering non-identical job size and dynamic job ready time. The considered unrelated machines have different capacity and different processing speed. Each machine processes a number of the jobs as a batch at the same time so that the machine’s capacity is not exceeded. The batch processing time and the batch ready time are equal to the largest processing time and the largest ready time of jobs in the same batch, respectively. In this paper, a Mixed Integer Linear Programming (MILP) model, two categories of the heuristic procedures (six heuristics) and a meta-heuristic algorithm are proposed to solve the problem. A lower bound is also presented by relaxing of the original problem to evaluate the quality of the proposed algorithms. The computational experiments show the performance of the proposed algorithms under the considered measures.
Keywords: Unrelated parallel machines, batch-processing, heuristic, dynamic job ready times, Makespan, mathematical modeling
@article{RO_2021__55_3_1501_0,
author = {Zarook, Yaser and Rezaeian, Javad and Mahdavi, Iraj and Yaghini, Masoud},
title = {Efficient algorithms to minimize makespan of the unrelated parallel batch-processing machines scheduling problem with unequal job ready times},
journal = {RAIRO. Operations Research},
pages = {1501--1522},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {3},
doi = {10.1051/ro/2021062},
mrnumber = {4269470},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021062/}
}
TY - JOUR AU - Zarook, Yaser AU - Rezaeian, Javad AU - Mahdavi, Iraj AU - Yaghini, Masoud TI - Efficient algorithms to minimize makespan of the unrelated parallel batch-processing machines scheduling problem with unequal job ready times JO - RAIRO. Operations Research PY - 2021 SP - 1501 EP - 1522 VL - 55 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021062/ DO - 10.1051/ro/2021062 LA - en ID - RO_2021__55_3_1501_0 ER -
%0 Journal Article %A Zarook, Yaser %A Rezaeian, Javad %A Mahdavi, Iraj %A Yaghini, Masoud %T Efficient algorithms to minimize makespan of the unrelated parallel batch-processing machines scheduling problem with unequal job ready times %J RAIRO. Operations Research %D 2021 %P 1501-1522 %V 55 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021062/ %R 10.1051/ro/2021062 %G en %F RO_2021__55_3_1501_0
Zarook, Yaser; Rezaeian, Javad; Mahdavi, Iraj; Yaghini, Masoud. Efficient algorithms to minimize makespan of the unrelated parallel batch-processing machines scheduling problem with unequal job ready times. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1501-1522. doi: 10.1051/ro/2021062
[1] , Principles of Sequencing and Scheduling. Wiley, New Jersey (1943).
[2] , Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6 (1994) 154–160. | Zbl | DOI
[3] , and , Minimizing makespan on parallel batch processing machines. Int. J. Prod. Res. 42 (2004) 4211–4220. | DOI
[4] and , Heuristics to minimize makespan of parallel batch processing machines. Int. J. Adv. Manuf. Technol. 37 (2008) 1005–1013. | DOI
[5] , and , Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. Int. J. Prod. Econ. 103 (2006) 882–891. | DOI
[6] , and , Scheduling identical parallel batch processing machines to minimize makespan using genetic algorithms. Eur. J. Ind. Eng. 3 (2009) 187–206. | DOI
[7] and , Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective. Comput. Oper. Res. 40 (2013) 1224–1233. | MR | Zbl | DOI
[8] , Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975). | MR | Zbl
[9] and , Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times. Comput. Oper. Res. 78 (2017) 117–128. | MR | Zbl | DOI
[10] , and , An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times. Eng. App. Artif. Intell. 77 (2019) 239–254. | DOI
[11] , and , A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Comput. Oper. Res. 35 (2008) 1084–1098. | Zbl | DOI
[12] , , and , Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families. Int. J. Prod. Res. 42 (2004) 4091–4107. | Zbl | DOI
[13] , , and , Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families. Int. J. Prod. Econ. 98 (2005) 81–96. | DOI
[14] and , A Mata heuristic framework for batch machine scheduling problems with incompatible job families and regular sum objective. Appl. Soft Comput. J. 68 (2018) 835–846. | DOI
[15] , and , Efficient algorithms for scheduling semi-conductor burn-in operations. Oper. Res. 40 (1992) 764–775. | MR | Zbl | DOI
[16] and , A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research 34 (2007) 3016–3028. | MR | Zbl | DOI
[17] and , A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. Int. J. Adv. Manuf. Technol. 29 (2006) 990–1001. | DOI
[18] , and , Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ. 87 (2004) 141–147. | DOI
[19] , , , and , A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. J. Scheduling 14 (2011) 583–599. | MR | DOI
[20] , Exact algorithms to minimize makespan on single and parallel batch processing machines. Eur. J. Oper. Res. 285 (2020) 470–483. | MR | Zbl | DOI
[21] , Scheduling Theory, Algorithms, and Systems, 3rd edition. Springer, New York (2008). | MR | Zbl
[22] , and , Makespan minimization on single batch-processing machine via ant colony optimization. Comput. Oper. Res. 39 (2012) 582–593. | MR | Zbl | DOI
[23] , and , Distance matrix based heuristics to minimize makespan of parallel-batch processing machines with arbitrary job sizes and release times. Appl. Soft Comput. 52 (2017) 630–641. | DOI
[24] , Introduction to Quality Engineering. Asian Productivity Organization/UNIPUB White Plains (1986).
[25] , Scheduling a single batch processing machine with non-identical job sizes. Int. J. Prod. Res. 32 (1994) 1615–1635. | Zbl | DOI
[26] and , A genetic algorithm for scheduling parallel non-identical batch processing machines. In: . IEEE Symposium on Computational Intelligence in Scheduling (2007) 143–150.
[27] , and , A bi-objective scheduling problem on batch machines via a pareto-based ant colony system. Int. J. Prod. Econ. 145 (2013) 371–386. | DOI
[28] , , , and , Minimization of makespan for the single batch-processing machine scheduling problem with considering aging effect and multi-maintenance activities. Int. J. Adv. Manuf. Technol. 76 (2015) 1879–1892. | DOI
[29] , , and , Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. J. Ind. Manage. Optim. 13 (2017) 977–993. | MR | Zbl | DOI
[30] , and , Energy-efficient scheduling of a single batch processing machine with dynamic job arrival times. Energy 209 (2020) 118420. | DOI
Cité par Sources :
