• Previous Article
    Infinite-time ruin probability of a renewal risk model with exponential Levy process investment and dependent claims and inter-arrival times
  • JIMO Home
  • This Issue
  • Next Article
    Continuity of the solution mappings to parametric generalized non-weak vector Ky Fan inequalities
April  2017, 13(2): 977-993. doi: 10.3934/jimo.2016057

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

Received  August 2015 Revised  June 2016 Published  August 2016

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.

Citation: Zhao-Hong Jia, Ting-Ting Wen, Joseph Y.-T. Leung, Kai Li. Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 977-993. doi: 10.3934/jimo.2016057
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.   Google Scholar

[2]

A. BilykL. 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.  Google Scholar

[3]

P. BruckerA. GladkyH. HoogeveenM.-Y. KovalyovC.-N. PottsT. 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.  Google Scholar

[4]

P.-Y. ChangP. Damodaran and S. Melouk, Minimizing makespan on parallel batch processing machines, International Journal of Production Research, 42 (2004), 4211-4220.  doi: 10.1080/00207540410001711863.  Google Scholar

[5]

H.-P. ChenB. 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.   Google Scholar

[6]

B.-Y. ChengK. 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.  Google Scholar

[7]

B.-Y. ChengS.-L. YangX.-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.  Google Scholar

[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.  Google Scholar

[9]

P. DamodaranD.-A. DiyadawagamageO. 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.  Google Scholar

[10]

P. DamodaranP.-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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[13]

B.-Q. FanJ.-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.  Google Scholar

[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.  Google Scholar

[15]

R.-L. GrahamE.-L. LawlerJ.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

A.-H. KashanB. 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.  Google Scholar

[20]

A.-H. KashanB. 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.  Google Scholar

[21]

A.-H. KashanM.-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.  Google Scholar

[22]

A. KlemmtG. WeigertC. 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.  Google Scholar

[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.  Google Scholar

[24]

C.-Y. LeeR. 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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[27]

S.-G. LiG.-J. LiX.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[32]

L. MönchJ.-W. FowlerS. Dauzere-PeresS.-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.  Google Scholar

[33]

J. OuJ.-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.  Google Scholar

[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.  Google Scholar

[35]

H. ShaoH.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[39]

R. Uzsoy, UScheduling batch processing machines with incompatible job families, International Journal of Production Research, 33 (1995), 2685-2708.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[46]

R. XuH.-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.  Google Scholar

[47]

R. XuH.-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.  Google Scholar

[48]

N. YinL.-Y. KangT.-C. SunC. 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.  Google Scholar

[49]

G. ZhangX. CaiC.-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.  Google Scholar

show all references

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.   Google Scholar

[2]

A. BilykL. 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.  Google Scholar

[3]

P. BruckerA. GladkyH. HoogeveenM.-Y. KovalyovC.-N. PottsT. 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.  Google Scholar

[4]

P.-Y. ChangP. Damodaran and S. Melouk, Minimizing makespan on parallel batch processing machines, International Journal of Production Research, 42 (2004), 4211-4220.  doi: 10.1080/00207540410001711863.  Google Scholar

[5]

H.-P. ChenB. 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.   Google Scholar

[6]

B.-Y. ChengK. 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.  Google Scholar

[7]

B.-Y. ChengS.-L. YangX.-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.  Google Scholar

[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.  Google Scholar

[9]

P. DamodaranD.-A. DiyadawagamageO. 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.  Google Scholar

[10]

P. DamodaranP.-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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[13]

B.-Q. FanJ.-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.  Google Scholar

[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.  Google Scholar

[15]

R.-L. GrahamE.-L. LawlerJ.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

A.-H. KashanB. 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.  Google Scholar

[20]

A.-H. KashanB. 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.  Google Scholar

[21]

A.-H. KashanM.-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.  Google Scholar

[22]

A. KlemmtG. WeigertC. 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.  Google Scholar

[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.  Google Scholar

[24]

C.-Y. LeeR. 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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[27]

S.-G. LiG.-J. LiX.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[32]

L. MönchJ.-W. FowlerS. Dauzere-PeresS.-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.  Google Scholar

[33]

J. OuJ.-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.  Google Scholar

[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.  Google Scholar

[35]

H. ShaoH.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[39]

R. Uzsoy, UScheduling batch processing machines with incompatible job families, International Journal of Production Research, 33 (1995), 2685-2708.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[46]

R. XuH.-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.  Google Scholar

[47]

R. XuH.-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.  Google Scholar

[48]

N. YinL.-Y. KangT.-C. SunC. 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.  Google Scholar

[49]

G. ZhangX. CaiC.-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.  Google Scholar

Figure 1.  Comparison of solution quality and robustness on the problems with different numbers of jobs.
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 $
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 $
Table 2.  Results for instances with 90 jobs.
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
1751.331.331.330.00
2755.334.005.330.00
3754.002.674.000.00
4754.004.004.002.67
5756.674.005.332.67
67513.3310.6713.338.00
77510.678.0010.671.33
87510.6710.6710.676.67
9751.331.334.000.00
10758.008.008.004.00
Average756.535.476.672.53
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
1751.331.331.330.00
2755.334.005.330.00
3754.002.674.000.00
4754.004.004.002.67
5756.674.005.332.67
67513.3310.6713.338.00
77510.678.0010.671.33
87510.6710.6710.676.67
9751.331.334.000.00
10758.008.008.004.00
Average756.535.476.672.53
Table 3.  Results for instances with 108 jobs.
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
17513.339.3314.676.67
27510.676.6710.674.00
37514.6710.6712.006.67
47521.3313.3320.008.00
57514.6710.6717.336.67
67514.6712.0014.6713.33
77510.678.0010.6710.67
87521.3312.008.0013.33
97520.0016.0021.3313.33
107517.3314.6717.3310.67
Average7515.8711.3314.679.33
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
17513.339.3314.676.67
27510.676.6710.674.00
37514.6710.6712.006.67
47521.3313.3320.008.00
57514.6710.6717.336.67
67514.6712.0014.6713.33
77510.678.0010.6710.67
87521.3312.008.0013.33
97520.0016.0021.3313.33
107517.3314.6717.3310.67
Average7515.8711.3314.679.33
Table 4.  Results for instances with 126 jobs.
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18021.2516.2520.0012.50
27534.6730.6732.0020.00
37528.0024.0024.0016.00
47536.0032.0034.6722.67
58321.6918.0720.4816.87
67529.3328.0028.0021.33
77824.3620.5123.0814.10
87927.8522.7926.5816.46
97727.2718.1825.9711.69
107722.0820.7822.0819.48
Average77.427.2523.1325.6917.11
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18021.2516.2520.0012.50
27534.6730.6732.0020.00
37528.0024.0024.0016.00
47536.0032.0034.6722.67
58321.6918.0720.4816.87
67529.3328.0028.0021.33
77824.3620.5123.0814.10
87927.8522.7926.5816.46
97727.2718.1825.9711.69
107722.0820.7822.0819.48
Average77.427.2523.1325.6917.11
Table 5.  Results for instances with 144 jobs.
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18638.3736.0538.3730.23
28923.6020.2320.2314.61
38632.5629.0731.4026.74
47635.5330.2634.2127.63
57940.5132.9137.9824.05
67534.6729.3336.0032.00
78330.1224.1028.9221.69
88225.6119.5123.1720.73
98825.0023.8625.0017.05
107841.0337.1841.0332.05
Average82.232.7028.2531.6324.68
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18638.3736.0538.3730.23
28923.6020.2320.2314.61
38632.5629.0731.4026.74
47635.5330.2634.2127.63
57940.5132.9137.9824.05
67534.6729.3336.0032.00
78330.1224.1028.9221.69
88225.6119.5123.1720.73
98825.0023.8625.0017.05
107841.0337.1841.0332.05
Average82.232.7028.2531.6324.68
Table 6.  Results for instances with 162 jobs.
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18237.8132.9337.8128.05
29139.5632.9739.5631.87
38734.4829.8931.0327.59
48827.2725.0027.2721.59
58831.8230.6832.9625.00
68038.7533.7537.5031.25
77927.8527.8527.8524.05
88333.7433.7436.1531.33
98139.5134.5737.0429.63
109030.0026.6727.7821.11
Average84.934.0830.8033.4927.15
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18237.8132.9337.8128.05
29139.5632.9739.5631.87
38734.4829.8931.0327.59
48827.2725.0027.2721.59
58831.8230.6832.9625.00
68038.7533.7537.5031.25
77927.8527.8527.8524.05
88333.7433.7436.1531.33
98139.5134.5737.0429.63
109030.0026.6727.7821.11
Average84.934.0830.8033.4927.15
Table 7.  Results for instances with 180 jobs.
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18848.8645.4644.3236.36
28641.8640.7040.7037.21
38435.7132.1435.7129.76
49042.2238.8942.2235.56
59038.8936.6737.7834.44
68344.5842.1739.7639.76
78836.3631.8235.2334.09
88640.7036.0540.7030.23
99346.2441.9443.0136.56
109042.2237.7838.8932.22
Average87.841.7738.3639.8334.62
Ins. No.LB$R_{FF}$$R_{FB}$$R_{BF}$$R_{BB}$
18848.8645.4644.3236.36
28641.8640.7040.7037.21
38435.7132.1435.7129.76
49042.2238.8942.2235.56
59038.8936.6737.7834.44
68344.5842.1739.7639.76
78836.3631.8235.2334.09
88640.7036.0540.7030.23
99346.2441.9443.0136.56
109042.2237.7838.8932.22
Average87.841.7738.3639.8334.62
[1]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[2]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087

[3]

Pascal Noble, Sebastien Travadel. Non-persistence of roll-waves under viscous perturbations. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 61-70. doi: 10.3934/dcdsb.2001.1.61

[4]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1673-1692. doi: 10.3934/dcdss.2020449

[5]

Liqin Qian, Xiwang Cao. Character sums over a non-chain ring and their applications. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020134

[6]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

[7]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055

[8]

Hyeong-Ohk Bae, Hyoungsuk So, Yeonghun Youn. Interior regularity to the steady incompressible shear thinning fluids with non-Standard growth. Networks & Heterogeneous Media, 2018, 13 (3) : 479-491. doi: 10.3934/nhm.2018021

[9]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195

[10]

Nabahats Dib-Baghdadli, Rabah Labbas, Tewfik Mahdjoub, Ahmed Medeghri. On some reaction-diffusion equations generated by non-domiciliated triatominae, vectors of Chagas disease. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021004

[11]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

[12]

Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017

[13]

Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849

[14]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393

[15]

Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040

[16]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004

[17]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (198)
  • HTML views (406)
  • Cited by (0)

[Back to Top]