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