# American Institute of Mathematical Sciences

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

show all references

##### References:
Comparison of solution quality and robustness on the problems with different numbers of jobs.
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$
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
 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
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
 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
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
 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
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
 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
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
 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
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
 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
 [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