Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times

Zhao-Hong Jia; Ting-Ting Wen; Joseph Y.-T. Leung; Kai Li

doi:10.3934/jimo.2016057

Article Contents

2017, Volume 13, Issue 2: 977-993. Doi: 10.3934/jimo.2016057

This issue Previous Article Continuity of the solution mappings to parametric generalized non-weak vector Ky Fan inequalities Next Article Infinite-time ruin probability of a renewal risk model with exponential Levy process investment and dependent claims and inter-arrival times

Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times

1.
Key Lab of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei, Anhui, 230039, China
2.
School of Management, Hefei University of Technology, Hefei, Anhui, 230009, China
3.
Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA

* Corresponding author: Zhao-Hong Jia
* Corresponding author: Zhao-Hong Jia

Received: August 2015

Revised: June 2016

Published: August 2017

Abstract / Introduction Full Text(HTML) Figure(1) / Table(7) Related Papers Cited by

Abstract

We consider the problem of scheduling a set of $n$ jobs with arbitrary job sizes, processing times and release times on a set of $m$ parallel batch machines with non-identical capacities; the objective is to minimize the makespan. We first present an algorithm to compute a lower bound for the optimal makespan. Based on different rules of batching the jobs and assigning the batches to the machines, several heuristics are proposed to solve the problem. The performance of the proposed heuristics is evaluated by computational experiments. The proposed heuristics are compared against the lower bound and against each other. Our results show that the one of the proposed algorithms outperforms all the other heuristics.

Keywords:

Mathematics Subject Classification: Primary: 68T20, 68T05; Secondary: 05-04.

Citation:

Full Text(HTML)

Figure 1. Comparison of solution quality and robustness on the problems with different numbers of jobs.

Download: Full-size image PowerPoint slide

Table 1. Parameters setting

factors	categories and values
machine capacities	$S_1=10, S_2=25, S_3=65$
machine numbers	$m_1=5, m_2=3, m_3=2$
job numbers $n$	$n=\{90,108,126,144,162,180\}$
processing times of jobs $p_j$	U[5, 15]
job arrival times	$r_0=0,r_1=20,r_3=40,r_4=60 $

| Show Table

DownLoad: CSV

Table 2. Results for instances with 90 jobs.

Ins. No.	LB	$R_{FF}$	$R_{FB}$	$R_{BF}$	$R_{BB}$
1	75	1.33	1.33	1.33	0.00
2	75	5.33	4.00	5.33	0.00
3	75	4.00	2.67	4.00	0.00
4	75	4.00	4.00	4.00	2.67
5	75	6.67	4.00	5.33	2.67
6	75	13.33	10.67	13.33	8.00
7	75	10.67	8.00	10.67	1.33
8	75	10.67	10.67	10.67	6.67
9	75	1.33	1.33	4.00	0.00
10	75	8.00	8.00	8.00	4.00
Average	75	6.53	5.47	6.67	2.53

| Show Table

DownLoad: CSV

Table 3. Results for instances with 108 jobs.

Ins. No.	LB	$R_{FF}$	$R_{FB}$	$R_{BF}$	$R_{BB}$
1	75	13.33	9.33	14.67	6.67
2	75	10.67	6.67	10.67	4.00
3	75	14.67	10.67	12.00	6.67
4	75	21.33	13.33	20.00	8.00
5	75	14.67	10.67	17.33	6.67
6	75	14.67	12.00	14.67	13.33
7	75	10.67	8.00	10.67	10.67
8	75	21.33	12.00	8.00	13.33
9	75	20.00	16.00	21.33	13.33
10	75	17.33	14.67	17.33	10.67
Average	75	15.87	11.33	14.67	9.33

| Show Table

DownLoad: CSV

Table 4. Results for instances with 126 jobs.

Ins. No.	LB	$R_{FF}$	$R_{FB}$	$R_{BF}$	$R_{BB}$
1	80	21.25	16.25	20.00	12.50
2	75	34.67	30.67	32.00	20.00
3	75	28.00	24.00	24.00	16.00
4	75	36.00	32.00	34.67	22.67
5	83	21.69	18.07	20.48	16.87
6	75	29.33	28.00	28.00	21.33
7	78	24.36	20.51	23.08	14.10
8	79	27.85	22.79	26.58	16.46
9	77	27.27	18.18	25.97	11.69
10	77	22.08	20.78	22.08	19.48
Average	77.4	27.25	23.13	25.69	17.11

| Show Table

DownLoad: CSV

Table 5. Results for instances with 144 jobs.

Ins. No.	LB	$R_{FF}$	$R_{FB}$	$R_{BF}$	$R_{BB}$
1	86	38.37	36.05	38.37	30.23
2	89	23.60	20.23	20.23	14.61
3	86	32.56	29.07	31.40	26.74
4	76	35.53	30.26	34.21	27.63
5	79	40.51	32.91	37.98	24.05
6	75	34.67	29.33	36.00	32.00
7	83	30.12	24.10	28.92	21.69
8	82	25.61	19.51	23.17	20.73
9	88	25.00	23.86	25.00	17.05
10	78	41.03	37.18	41.03	32.05
Average	82.2	32.70	28.25	31.63	24.68

| Show Table

DownLoad: CSV

Table 6. Results for instances with 162 jobs.

Ins. No.	LB	$R_{FF}$	$R_{FB}$	$R_{BF}$	$R_{BB}$
1	82	37.81	32.93	37.81	28.05
2	91	39.56	32.97	39.56	31.87
3	87	34.48	29.89	31.03	27.59
4	88	27.27	25.00	27.27	21.59
5	88	31.82	30.68	32.96	25.00
6	80	38.75	33.75	37.50	31.25
7	79	27.85	27.85	27.85	24.05
8	83	33.74	33.74	36.15	31.33
9	81	39.51	34.57	37.04	29.63
10	90	30.00	26.67	27.78	21.11
Average	84.9	34.08	30.80	33.49	27.15

| Show Table

DownLoad: CSV

Table 7. Results for instances with 180 jobs.

Ins. No.	LB	$R_{FF}$	$R_{FB}$	$R_{BF}$	$R_{BB}$
1	88	48.86	45.46	44.32	36.36
2	86	41.86	40.70	40.70	37.21
3	84	35.71	32.14	35.71	29.76
4	90	42.22	38.89	42.22	35.56
5	90	38.89	36.67	37.78	34.44
6	83	44.58	42.17	39.76	39.76
7	88	36.36	31.82	35.23	34.09
8	86	40.70	36.05	40.70	30.23
9	93	46.24	41.94	43.01	36.56
10	90	42.22	37.78	38.89	32.22
Average	87.8	41.77	38.36	39.83	34.62

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Almeder and L. Mönch, Metaheuristics for scheduling jobs with incompatible families on parallel batch machines, Journal of the Operational Research Society, 62 (2011), 2083-2096.
[2]	A. Bilyk, L. Mönch and C. Almeder, Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics, Computers & Industrial Engineering, 78 (2014), 175-185. doi: 10.1016/j.cie.2014.10.008.
[3]	P. Brucker, A. Gladky, H. Hoogeveen, M.-Y. Kovalyov, C.-N. Potts, T. Tautenhahn and S.-L. Van de Velde, Scheduling a batching machine, Journal of Scheduling, 1 (1998), 31-45. doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R.
[4]	P.-Y. Chang, P. Damodaran and S. Melouk, Minimizing makespan on parallel batch processing machines, International Journal of Production Research, 42 (2004), 4211-4220. doi: 10.1080/00207540410001711863.
[5]	H.-P. Chen, B. Du and G. Huang, Metaheuristics to minimize makespan on parallel batch processing machines with dynamic job arrivals, International Journal of Computer Integrated Manufacturing, 23 (2010), 942-956.
[6]	B.-Y. Cheng, K. Li and B. Chen, Scheduling a single batch-processing machine with non-identical job sizes in fuzzy environment using an improved ant colony optimization, Journal of Manufacturing Systems, 29 (2010), 29-34. doi: 10.1016/j.jmsy.2010.06.007.
[7]	B.-Y. Cheng, S.-L. Yang, X.-X. Hu and B. Chen, Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes, Applied Mathematical Modelling, 36 (2012), 3161-3167. doi: 10.1016/j.apm.2011.09.061.
[8]	P. Damodaran and P.-Y. Chang, Heuristics to minimize makespan of parallel batch processing machines, International Journal of Advanced Manufacturing Technology, 37 (2008), 1005-1013. doi: 10.1007/s00170-007-1042-8.
[9]	P. Damodaran, D.-A. Diyadawagamage, O. Ghrayeb and M.-C. Vélez-Gallego, A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines, International Journal of Advanced Manufacturing Technology, 58 (2012), 1131-1140. doi: 10.1007/s00170-011-3442-z.
[10]	P. Damodaran, P.-K. Manjeshwar and K. Srihari, Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms, International Journal of Production Economics, 103 (2006), 882-891. doi: 10.1016/j.ijpe.2006.02.010.
[11]	L. Dupont and C. Dhaenens-Flipo, Minimizing the makespan on a batch machine with nonidentical job sizes: An exact procedure, Computers & Operations Research, 29 (2002), 807-819. doi: 10.1016/S0305-0548(00)00078-2.
[12]	L. Dupont and F. Jolai Ghazvini, Minimizing makespan on a single batch processing machine with non identical job sizes, European Journal of Automation System, 32 (1998), 431-440.
[13]	B.-Q. Fan, J.-J. Yuan and S.-S. Li, Bi-criteria scheduling on a single parallel-batch machine, Applied Mathematical Modelling, 36 (2012), 1338-1346. doi: 10.1016/j.apm.2011.07.084.
[14]	F.-J. Ghazvini and L. Dupont, Minimizing mean flow time criteria on a single batch processing machine with non-identical job sizes, International Journal of Production Economics, 55 (1998), 273-280. doi: 10.1016/S0925-5273(98)00067-X.
[15]	R.-L. Graham, E.-L. Lawler, J.-K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326. doi: 10.1016/S0167-5060(08)70356-X.
[16]	Y. Huo and J.-Y.-T. Leung, Fast approximation algorithms for job scheduling with processing set restrictions, Theoretical Computer Science, 411 (2010), 3947-3955. doi: 10.1016/j.tcs.2010.08.008.
[17]	Y. Ikura and M. Gimple, Efficient scheduling algorithms for a single batch processing machine, Operations Research Letter, 5 (1986), 61-65. doi: 10.1016/0167-6377(86)90104-5.
[18]	Z.-H. Jia and J.-Y.-T. Leung, An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes, Computers & Operations Research, 46 (2014), 49-58. doi: 10.1016/j.cor.2014.01.001.
[19]	A.-H. Kashan, B. Karimi and M. Jenabi, A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes, Computers & Operations Research, 35 (2008), 1084-1098. doi: 10.1016/j.cor.2006.07.005.
[20]	A.-H. Kashan, B. Karimi and F. Jolai, Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes, International Journal of Production Research, 44 (2006), 2337-2360. doi: 10.1080/00207540500525254.
[21]	A.-H. Kashan, M.-H. Kashan and S. Karimiyan, Particle swarm optimizer for grouping problems, Information Sciences, 252 (2013), 81-95. doi: 10.1016/j.ins.2012.10.036.
[22]	A. Klemmt, G. Weigert, C. Almeder and L. Mönch, A Comparison of MIP-based Decomposition Techniques and VNS Approaches for Batch Scheduling Problems, Proceedings of the Modeling and Analysis of Semiconductor Manufacturing Conference (MASM), (2009), 1686-1694. doi: 10.1109/WSC.2009.5429173.
[23]	M.-E. Kurz and S.-J. Mason, Minimizing total weighted tardiness on a batch-processing machine with incompatible job families and job ready times, International Journal of Production Research, 46 (2008), 131-151. doi: 10.1080/00207540600786665.
[24]	C.-Y. Lee, R. Uzsoy and L.-A. Martin-Vega, Efficient algorithms for scheduling semi-conductor burn-in operations, Operations Research, 40 (1992), 764-775. doi: 10.1287/opre.40.4.764.
[25]	C.-Y. Lee and R. Uzsoy, Minimizing makespan on a single batchnimizing makespan on a single burn-in oven in semiconductor manufacturing, European Journal of Operational Research, 120 (2000), 559-574.
[26]	J.-Y.-T. Leung and C.-L. Li, Scheduling with processing set restrictions: A survey, International Journal of Production Economics, 116 (2008), 251-262. doi: 10.1016/j.ijpe.2008.09.003.
[27]	S.-G. Li, G.-J. Li, X.-L. Wang and Q.-M. Liu, Minimizing makespan on a single batching machine with release times and non-identical job sizes, Operations Research Letters, 33 (2005), 157-164. doi: 10.1016/j.orl.2004.04.009.
[28]	M. Liu, Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect, Applied Mathematical Modelling, 37 (2013), 9630-9633. doi: 10.1016/j.apm.2013.05.025.
[29]	S. Malve and R. Uzsoy, 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), 3061-3028. doi: 10.1016/j.cor.2005.11.011.
[30]	M. Mathirajan and A.-I. Sivakumar, A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor, International Journal of Advanced Manufacturing Technology, 29 (2006), 990-1001. doi: 10.1007/s00170-005-2585-1.
[31]	L. Mönch and C. Almeder, Ant colony optimization approaches for scheduling jobs with incompatible families on parallel batch machines, Proceedings 4th Multi-disciplinary International Conference on Scheduling: Theory and Applications (MISTA), Dublin, Ireland, 2009,106-114.
[32]	L. Mönch, J.-W. Fowler, S. Dauzere-Peres, S.-J. Mason and O. Rose, A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations, Journal of Scheduling, 14 (2011), 583-599. doi: 10.1007/s10951-010-0222-9.
[33]	J. Ou, J.-Y.-T. Leung and C.-L. Li, Scheduling parallel machines with inclusive processing set restrictions, Naval Research Logistics, 55 (2008), 328-338. doi: 10.1002/nav.20286.
[34]	C. Potts and M. Kovalyov, Scheduling with batching: A review, European Journal of Operational Research, 120 (2000), 228-249. doi: 10.1016/S0377-2217(99)00153-8.
[35]	H. Shao, H.-P. Chen and G. Huang, Minimizing makespan for parallel batch processing machines with non-identical job sizes using neural nets approach, Proceedings of the 23rd IEEE Conference on Industrial Electronics and Applications, Singapore, 32 (2008), 1921-1924. doi: 10.1109/ICIEA.2008.4582854.
[36]	C.-S. Sung and Y.-I. Choung, Minimizing makespan on a single burn-in oven in semiconductor manufacturing, European Journal of Operational Research, 120 (2000), 559-574. doi: 10.1016/S0377-2217(98)00391-9.
[37]	L.-X. Tang and H. Gong, A hybrid two-stage transportation and batch scheduling problem, Applied Mathematical Modelling, 32 (2008), 2467-2479. doi: 10.1016/j.apm.2007.09.028.
[38]	R. Uzsoy, Scheduling a single batch processing machine with non-identical job sizes, International Journal of Production Research, 32 (1994), 1615-1635. doi: 10.1080/00207549408957026.
[39]	R. Uzsoy, UScheduling batch processing machines with incompatible job families, International Journal of Production Research, 33 (1995), 2685-2708.
[40]	R. Uzsoy and Y. Yang, Minimizing total weighted completion time on a single batch processing machine, Production and Operations Management, 6 (1997), 57-73. doi: 10.1111/j.1937-5956.1997.tb00415.x.
[41]	M. Venkataramana and N.-R. Srinivasa Raghavan, Ant colony-based algorithms for scheduling parallel batch processors with incompatible job families, International Journal of Mathematics in Operational Research, 2 (2010), 73-98. doi: 10.1504/IJMOR.2010.029691.
[42]	C.-S. Wang and R. Uzsoy, A genetic algorithm to minimize maximum lateness on a batch processing machine, Computers & Operations Research, 29 (2002), 1621-1640. doi: 10.1016/S0305-0548(01)00031-4.
[43]	H.-M. Wang and F.-D. Chou, Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics, Expert Systems with Applications, 37 (2010), 1510-1521. doi: 10.1016/j.eswa.2009.06.070.
[44]	X.-Y. Wang and J.-J. Wang, Scheduling deteriorating jobs with a learning effect on unrelated parallel machines, Applied Mathematical Modelling, 38 (2014), 5231-5238. doi: 10.1016/j.apm.2014.04.002.
[45]	S.-B. Xu and J.-C. Bean, A genetic algorithm for scheduling parallel non-identical batch processing machines, IEEE Symposium on Computational Intelligence in Scheduling, SCIS'07, (2007), 143-150. doi: 10.1109/SCIS.2007.367682.
[46]	R. Xu, H.-P. Chen and X.-P. Li, Makespan minimization on single batch-processing machine via ant colony optimization, Computers & Operations Research, 39 (2012), 582-593. doi: 10.1016/j.cor.2011.05.011.
[47]	R. Xu, H.-P. Chen and X.-P. Li, A bi-objective scheduling problem on batch machines via a pareto-based ant colony system, International Journal of Production Economics, 145 (2013), 371-386. doi: 10.1016/j.ijpe.2013.04.053.
[48]	N. Yin, L.-Y. Kang, T.-C. Sun, C. Yue and X.-R. Wang, Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times, Applied Mathematical Modelling, 38 (2014), 4747-4755. doi: 10.1016/j.apm.2014.03.022.
[49]	G. Zhang, X. Cai, C.-Y. Lee and C.-K. Wong, Minimizing makespan on a single batch processing machine with nonidentical job sizes, Naval Research Logistics, 48 (2001), 226-240. doi: 10.1002/nav.4.