• 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]

M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial & Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445

[2]

Han Wu, Changfan Zhang, Jing He, Kaihui Zhao. Distributed fault-tolerant consensus tracking for networked non-identical motors. Journal of Industrial & Management Optimization, 2017, 13 (2) : 917-929. doi: 10.3934/jimo.2016053

[3]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[4]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[5]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[6]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[7]

Denis de Carvalho Braga, Luis Fernando Mello, Carmen Rocşoreanu, Mihaela Sterpu. Lyapunov coefficients for non-symmetrically coupled identical dynamical systems. Application to coupled advertising models. Discrete & Continuous Dynamical Systems - B, 2009, 11 (3) : 785-803. doi: 10.3934/dcdsb.2009.11.785

[8]

Ling Lin, Dong He, Zhiyi Tan. Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm. Journal of Industrial & Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817

[9]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[10]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[11]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041

[12]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651

[13]

A.V. Borisov, I.S. Mamaev, A.A. Kilin. New periodic solutions for three or four identical vortices on a plane and a sphere. Conference Publications, 2005, 2005 (Special) : 110-120. doi: 10.3934/proc.2005.2005.110

[14]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771

[15]

Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385

[16]

Changli Yuan, Mojdeh Delshad, Mary F. Wheeler. Modeling multiphase non-Newtonian polymer flow in IPARS parallel framework. Networks & Heterogeneous Media, 2010, 5 (3) : 583-602. doi: 10.3934/nhm.2010.5.583

[17]

Alex Mahalov, Mohamed Moustaoui, Basil Nicolaenko. Three-dimensional instabilities in non-parallel shear stratified flows. Kinetic & Related Models, 2009, 2 (1) : 215-229. doi: 10.3934/krm.2009.2.215

[18]

Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial & Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685

[19]

Renaud Leplaideur, Benoît Saussol. Large deviations for return times in non-rectangle sets for axiom a diffeomorphisms. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 327-344. doi: 10.3934/dcds.2008.22.327

[20]

Ye Tian, Wei Yang, Gene Lai, Menghan Zhao. Predicting non-life insurer's insolvency using non-kernel fuzzy quadratic surface support vector machines. Journal of Industrial & Management Optimization, 2019, 15 (2) : 985-999. doi: 10.3934/jimo.2018081

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (29)
  • HTML views (301)
  • Cited by (0)

[Back to Top]