2017, 7(4): 465-480. doi: 10.3934/naco.2017029

A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem

1. 

Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran

2. 

Department of Industrial and Systems Engineering, Isfahan University of Technology, 84156-83111, Isfahan, Iran

* Corresponding author

Received  December 2016 Revised  September 2017 Published  October 2017

Fund Project: The reviewing process of this paper was handled by Associate Editors A. (Nima) Mirzazadeh, Kharazmi University, Tehran, Iran, and Gerhard-Wilhelm Weber, Middle East Technical University, Ankara, Turkey, at the occasion of 12th International Conference on Industrial Engineering (ICIE 2016), which was held in Tehran, Iran during 25-26 January, 2016

In this paper, first, the problem of dynamic two-machine flow shop scheduling with the objective of minimizing the number of tardy jobs is investigated. Second, a hybrid algorithm based on genetic algorithm and parallel simulated annealing algorithm is presented. In order to solve large scale instances of the problem and to generate the initial population for the hybrid approach, a heuristic algorithm is also presented. To evaluate the efficiency of the proposed algorithms, they are compared with an optimal branch-and-bound algorithm which has been already developed in the literature. Computational experiments demonstrate that the proposed hybrid algorithm can solve the entire small-sized problems and more than 95% of medium-sized problems optimally.

Citation: Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029
References:
[1]

M. Abouei Ardakan, A. Hakimian, M. T. Rezvan, A branch-and-bound algorithm for minimising the number of tardy jobs in a two-machine flow-shop problem with release datest, International Journal of Computer Integrated Manufacturing, 27 (2014), 519-528.

[2]

Ph. Baptiste, L. Peridy, E. Pinson, A branch and bound to minimize the number of late jobs on a single machine with release time constraints, European Journal of Operational Research, 144 (2003), 1-11.

[3]

J. C. Bean, Genetics and random keys for sequencing and optimization, ORSA Journal on Computing, 6 (1994), 154-160.

[4]

R. L. Bulfin, R. M'hallah, Minimizing the weighted number of tardy jobs on a two-machine flow shop, Computers & Operations Research, 30 (2003), 1887-1900. doi: 10.1016/S0305-0548(02)00114-4.

[5]

W. Chen, Minimizing number of tardy jobs on a single machine subject to periodic maintenance, Omega, 37 (2009), 591-599.

[6]

T. Chiang, L. Fu, A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop, International Journal of Production Research, 46 (2008), 6913-6931.

[7]

S. W. Choi, Y. D. Kim, Minimizing total tardiness on a two-machine re-entrant flowshop, European Journal of Operational Research, 199 (2009), 375-384. doi: 10.1016/j.ejor.2008.11.037.

[8]

H. S. Choi, D. H. Lee, Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops, Computers & Industrial Engineering, 56 (2009), 113-120.

[9]

D. T. Connolly, An improved annealing scheme for the QAP, European Journal of Operational Research, 46 (1990), 93-100. doi: 10.1016/0377-2217(90)90301-Q.

[10]

C. Desprez, F. Chu, C. Chu, Minimising the weighted number of tardy jobs in a hybrid flow shop with genetic algorithm, International Journal of Computer Integrated Manufacturing, 22 (2009), 745-757.

[11]

X. Feng, F. Zheng, Y. Xu, Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times, International Journal of Production Research, 54 (2016), 3706-3717.

[12]

E. M. González-Neira, J. R. Montoya-Torres, D. Barrera, Flow-shop scheduling problem under uncertainties: Review and trends, International Journal of Industrial Engineering Computations, 8 (2017), 399-426.

[13]

A. M. A. Hariri, C. N. Potts, A branch and bound algorithm to minimize the number of late jobs in a permutation flow-shop, European Journal of Operational Research, 38 (1989), 228-237. doi: 10.1016/0377-2217(89)90107-0.

[14]

Ch. He, Y. Lin, J. Yuan, A note on the single machine scheduling to minimize the number of tardy jobs with deadlines, European Journal of Operational Research, 201 (2010), 966-970. doi: 10.1016/j.ejor.2009.05.013.

[15]

F. Jolai, M. Rabbani, S. Amalnick, A. Dabaghi, M. Dehghan, M. Yazadn Parast, Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs, Applied Mathematics and Computation, 194 (2007), 552-560. doi: 10.1016/j.amc.2007.04.063.

[16]

J. Lenstra, A. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977), 343-362.

[17]

G. Sh. Liu, Y. Zhou, H. D. Yang, Minimizing energy consumption and tardiness penalty for fuzzy flow shop scheduling with state-dependent setup time, Journal of Cleaner Production, 147 (2017), 470-484.

[18]

M. Liu, Sh. Wang, Ch. Chu, F. Chu, An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance, International Journal of Production Research, 54 (2016), 3591-3602.

[19]

E. Lodree, W. Jang, C. M. Klein, A new rule for minimizing the number of tardy jobs in dynamic flow shops, European Journal of Operational Research, 159 (2004), 258-263. doi: 10.1016/S0377-2217(03)00404-1.

[20]

M. Lundy, A. Mees, Convergence of an annealing algorithm, Mathematical Programming, 34 (1986), 111-124. doi: 10.1007/BF01582166.

[21]

R. M'Hallah, T. Al-Khamis, A Benders decomposition approach to the weighted number of tardy jobs scheduling problem on unrelated parallel machines with production costs, International Journal of Production Research, 53 (2015), 5977-5987.

[22]

R. M'Hallah, R. L. Bulfin, Minimizing the weighted number of tardy jobs on a single machine with release dates, European Journal of Operational Research, 176 (2007), 727-744. doi: 10.1016/j.ejor.2005.08.013.

[23]

M. Mirabi, SMT. Fatemi Ghomi, F. Jolai, A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem, Journal of Industrial Engineering International, 10 (2014), 1-9.

[24]

E. Molaee, Gh. Moslehi, M. Reisi, Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem, Computers & Mathematics with Applications, 60 (2010), 2909-2919. doi: 10.1016/j.camwa.2010.09.046.

[25]

J. M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15 (1968), 102-109.

[26]

G. Mosheiov, A. Sarig, Minimum weighted number of tardy jobs on an m-machine flow-shop with a critical machine, European Journal of Operational Research, 201 (2010), 404-408. doi: 10.1016/j.ejor.2009.03.018.

[27]

Gh. Moslehi, M. Abouei Ardakan, Minimizing the number of Tardy jobs in a two-machine flowshop problem with non-simultaneous job entrance, International Journal of Industrial Engineering & amp; Production Management, 23 (2013), 389-400.

[28]

Gh. Moslehi, A. Jafari, Minimizing the number of tardy jobs under piecewise-linear deterioration, Computers & Industrial Engineering, 59 (2010), 573-584.

[29]

B. Naderi, E. Najafi, M. Yazdani, An electromagnetism-like metaheuristic for open-shop problems with no buffer, Journal of Industrial Engineering International, 8 (2012), 1-8.

[30]

S. Noori-Darvish, R. Tavakkoli-Moghaddam, Minimizing the total tardiness and makespan in an open shop scheduling problem with sequence-dependent setup times, Journal of Industrial Engineering International, 8 (2012), 1-13.

[31]

M. Rohaninejad, A. Saman Kheirkhah, B. Vahedi Nouri, P. Fattahi, Two hybrid tabu search-firefly algorithms for the capacitated job shop scheduling problem with sequence-dependent setup cost, International Journal of Computer Integrated Manufacturing, 28 (2015), 470-487.

[32]

A. J. Ruiz-Torres, G. Centeno, Minimizing the number of late jobs for the permutation flowshop problem with secondary resources, Computers & Operations Research, 35 (2008), 1227-1249. doi: 10.1016/j.cor.2006.07.013.

[33]

A. J. Ruiz-Torres, J. H. Ablanedo-Rosas, J. C. Ho, Minimizing the number of tardy jobs in the flowshop problem with operation and resource flexibility, Computers & Operations Research, 37 (2010), 282-291. doi: 10.1016/j.cor.2009.04.018.

[34]

R. Şahin, O. Türkbey, A simulated annealing algorithm to find approximate Pareto optimal solutions for the multi-objective facility layout problem, The International Journal of Advanced Manufacturing Technology, 41 (2009), 1003-1018.

[35]

R. Sadykov, A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates, European Journal of Operational Research, 189 (2008), 1284-1304. doi: 10.1016/j.ejor.2006.06.078.

[36]

G. Wan, B. P-C. Yen, Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs, European Journal of Operational Research, 195 (2009), 89-97. doi: 10.1016/j.ejor.2008.01.029.

[37]

Zh. Wang, C. M. Wei, L. Sun, Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect, International Journal of Production Research, (2016), 1-8.

[38]

J. Yuan, Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans, Journal of Combinatorial Optimization, 34 (2017), 443-440. doi: 10.1007/s10878-016-0078-9.

show all references

References:
[1]

M. Abouei Ardakan, A. Hakimian, M. T. Rezvan, A branch-and-bound algorithm for minimising the number of tardy jobs in a two-machine flow-shop problem with release datest, International Journal of Computer Integrated Manufacturing, 27 (2014), 519-528.

[2]

Ph. Baptiste, L. Peridy, E. Pinson, A branch and bound to minimize the number of late jobs on a single machine with release time constraints, European Journal of Operational Research, 144 (2003), 1-11.

[3]

J. C. Bean, Genetics and random keys for sequencing and optimization, ORSA Journal on Computing, 6 (1994), 154-160.

[4]

R. L. Bulfin, R. M'hallah, Minimizing the weighted number of tardy jobs on a two-machine flow shop, Computers & Operations Research, 30 (2003), 1887-1900. doi: 10.1016/S0305-0548(02)00114-4.

[5]

W. Chen, Minimizing number of tardy jobs on a single machine subject to periodic maintenance, Omega, 37 (2009), 591-599.

[6]

T. Chiang, L. Fu, A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop, International Journal of Production Research, 46 (2008), 6913-6931.

[7]

S. W. Choi, Y. D. Kim, Minimizing total tardiness on a two-machine re-entrant flowshop, European Journal of Operational Research, 199 (2009), 375-384. doi: 10.1016/j.ejor.2008.11.037.

[8]

H. S. Choi, D. H. Lee, Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops, Computers & Industrial Engineering, 56 (2009), 113-120.

[9]

D. T. Connolly, An improved annealing scheme for the QAP, European Journal of Operational Research, 46 (1990), 93-100. doi: 10.1016/0377-2217(90)90301-Q.

[10]

C. Desprez, F. Chu, C. Chu, Minimising the weighted number of tardy jobs in a hybrid flow shop with genetic algorithm, International Journal of Computer Integrated Manufacturing, 22 (2009), 745-757.

[11]

X. Feng, F. Zheng, Y. Xu, Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times, International Journal of Production Research, 54 (2016), 3706-3717.

[12]

E. M. González-Neira, J. R. Montoya-Torres, D. Barrera, Flow-shop scheduling problem under uncertainties: Review and trends, International Journal of Industrial Engineering Computations, 8 (2017), 399-426.

[13]

A. M. A. Hariri, C. N. Potts, A branch and bound algorithm to minimize the number of late jobs in a permutation flow-shop, European Journal of Operational Research, 38 (1989), 228-237. doi: 10.1016/0377-2217(89)90107-0.

[14]

Ch. He, Y. Lin, J. Yuan, A note on the single machine scheduling to minimize the number of tardy jobs with deadlines, European Journal of Operational Research, 201 (2010), 966-970. doi: 10.1016/j.ejor.2009.05.013.

[15]

F. Jolai, M. Rabbani, S. Amalnick, A. Dabaghi, M. Dehghan, M. Yazadn Parast, Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs, Applied Mathematics and Computation, 194 (2007), 552-560. doi: 10.1016/j.amc.2007.04.063.

[16]

J. Lenstra, A. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977), 343-362.

[17]

G. Sh. Liu, Y. Zhou, H. D. Yang, Minimizing energy consumption and tardiness penalty for fuzzy flow shop scheduling with state-dependent setup time, Journal of Cleaner Production, 147 (2017), 470-484.

[18]

M. Liu, Sh. Wang, Ch. Chu, F. Chu, An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance, International Journal of Production Research, 54 (2016), 3591-3602.

[19]

E. Lodree, W. Jang, C. M. Klein, A new rule for minimizing the number of tardy jobs in dynamic flow shops, European Journal of Operational Research, 159 (2004), 258-263. doi: 10.1016/S0377-2217(03)00404-1.

[20]

M. Lundy, A. Mees, Convergence of an annealing algorithm, Mathematical Programming, 34 (1986), 111-124. doi: 10.1007/BF01582166.

[21]

R. M'Hallah, T. Al-Khamis, A Benders decomposition approach to the weighted number of tardy jobs scheduling problem on unrelated parallel machines with production costs, International Journal of Production Research, 53 (2015), 5977-5987.

[22]

R. M'Hallah, R. L. Bulfin, Minimizing the weighted number of tardy jobs on a single machine with release dates, European Journal of Operational Research, 176 (2007), 727-744. doi: 10.1016/j.ejor.2005.08.013.

[23]

M. Mirabi, SMT. Fatemi Ghomi, F. Jolai, A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem, Journal of Industrial Engineering International, 10 (2014), 1-9.

[24]

E. Molaee, Gh. Moslehi, M. Reisi, Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem, Computers & Mathematics with Applications, 60 (2010), 2909-2919. doi: 10.1016/j.camwa.2010.09.046.

[25]

J. M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15 (1968), 102-109.

[26]

G. Mosheiov, A. Sarig, Minimum weighted number of tardy jobs on an m-machine flow-shop with a critical machine, European Journal of Operational Research, 201 (2010), 404-408. doi: 10.1016/j.ejor.2009.03.018.

[27]

Gh. Moslehi, M. Abouei Ardakan, Minimizing the number of Tardy jobs in a two-machine flowshop problem with non-simultaneous job entrance, International Journal of Industrial Engineering & amp; Production Management, 23 (2013), 389-400.

[28]

Gh. Moslehi, A. Jafari, Minimizing the number of tardy jobs under piecewise-linear deterioration, Computers & Industrial Engineering, 59 (2010), 573-584.

[29]

B. Naderi, E. Najafi, M. Yazdani, An electromagnetism-like metaheuristic for open-shop problems with no buffer, Journal of Industrial Engineering International, 8 (2012), 1-8.

[30]

S. Noori-Darvish, R. Tavakkoli-Moghaddam, Minimizing the total tardiness and makespan in an open shop scheduling problem with sequence-dependent setup times, Journal of Industrial Engineering International, 8 (2012), 1-13.

[31]

M. Rohaninejad, A. Saman Kheirkhah, B. Vahedi Nouri, P. Fattahi, Two hybrid tabu search-firefly algorithms for the capacitated job shop scheduling problem with sequence-dependent setup cost, International Journal of Computer Integrated Manufacturing, 28 (2015), 470-487.

[32]

A. J. Ruiz-Torres, G. Centeno, Minimizing the number of late jobs for the permutation flowshop problem with secondary resources, Computers & Operations Research, 35 (2008), 1227-1249. doi: 10.1016/j.cor.2006.07.013.

[33]

A. J. Ruiz-Torres, J. H. Ablanedo-Rosas, J. C. Ho, Minimizing the number of tardy jobs in the flowshop problem with operation and resource flexibility, Computers & Operations Research, 37 (2010), 282-291. doi: 10.1016/j.cor.2009.04.018.

[34]

R. Şahin, O. Türkbey, A simulated annealing algorithm to find approximate Pareto optimal solutions for the multi-objective facility layout problem, The International Journal of Advanced Manufacturing Technology, 41 (2009), 1003-1018.

[35]

R. Sadykov, A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates, European Journal of Operational Research, 189 (2008), 1284-1304. doi: 10.1016/j.ejor.2006.06.078.

[36]

G. Wan, B. P-C. Yen, Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs, European Journal of Operational Research, 195 (2009), 89-97. doi: 10.1016/j.ejor.2008.01.029.

[37]

Zh. Wang, C. M. Wei, L. Sun, Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect, International Journal of Production Research, (2016), 1-8.

[38]

J. Yuan, Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans, Journal of Combinatorial Optimization, 34 (2017), 443-440. doi: 10.1007/s10878-016-0078-9.

Figure 1.  The flowchart of the proposed hybrid meta-heuristic algorithm
Figure 2.  An example for R-K method
Figure 3.  Crossover operator
Table 1.  The differences between two groups of generated problems
Influential ParameterHigh settingLow setting
$r_j$Jobs are available in a longer time interval after the beginning of schedulingJobs are available in a short time interval which is closer to the close to the beginning of scheduling
$D_j$Tight due date intervalsLoose due date intervals
$D_j$Different due datesSimilar due dates
Number of tardy jobsMore tardy jobsLess tardy jobs
Influential ParameterHigh settingLow setting
$r_j$Jobs are available in a longer time interval after the beginning of schedulingJobs are available in a short time interval which is closer to the close to the beginning of scheduling
$D_j$Tight due date intervalsLoose due date intervals
$D_j$Different due datesSimilar due dates
Number of tardy jobsMore tardy jobsLess tardy jobs
Table 2.  Performance of PSA-GA and HEU1 algorithms in set High (compared with B & B)
CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1
nminavgmaxOPT#OPT(%)avgmaxavgmax
50.000.090.1720100%1.001.001.061.50
60.050.160.2820100%1.001.001.111.33
70.020.200.3720100%1.001.001.091.40
80.020.180.3720100%1.001.001.101.20
90.020.210.4520100%1.001.001.061.17
100.080.160.4120100%1.001.001.121.29
120.020.060.5020 $100\%$1.001.001.011.10
140.230.410.8620 $100\%$1.001.001.121.25
160.330.701.1519 $95\%$1.001.071.111.25
180.621.342.1119$95\%$1.011.071.041.13
200.440.901.6719 $95\%$1.011.081.051.12
CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1
nminavgmaxOPT#OPT(%)avgmaxavgmax
50.000.090.1720100%1.001.001.061.50
60.050.160.2820100%1.001.001.111.33
70.020.200.3720100%1.001.001.091.40
80.020.180.3720100%1.001.001.101.20
90.020.210.4520100%1.001.001.061.17
100.080.160.4120100%1.001.001.121.29
120.020.060.5020 $100\%$1.001.001.011.10
140.230.410.8620 $100\%$1.001.001.121.25
160.330.701.1519 $95\%$1.001.071.111.25
180.621.342.1119$95\%$1.011.071.041.13
200.440.901.6719 $95\%$1.011.081.051.12
Table 3.  Performance of PSA-GA and HEU1 algorithms in set Low (compared with B & B)
CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1
nminavgmaxOPT#OPT(%)avgmaxavgmax
50.020.090.1620100%1.001.001.101.33
60.060.150.3120100%1.001.001.101.25
70.140.270.3820100%1.001.001.051.20
80.110.200.3420100%1.001.001.071.40
90.230.410.5520100%1.001.001.061.33
100.110.290.5520100%1.001.001.091.60
120.220.330.6120 $100\%$1.001.001.071.43
140.220.480.6720 $100\%$1.001.001.081.20
160.370.701.0820 $100\%$1.001.001.091.17
180.701.141.6219$95\%$1.011.031.061.15
200.781.122.2919 $95\%$1.011.031.071.12
CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1
nminavgmaxOPT#OPT(%)avgmaxavgmax
50.020.090.1620100%1.001.001.101.33
60.060.150.3120100%1.001.001.101.25
70.140.270.3820100%1.001.001.051.20
80.110.200.3420100%1.001.001.071.40
90.230.410.5520100%1.001.001.061.33
100.110.290.5520100%1.001.001.091.60
120.220.330.6120 $100\%$1.001.001.071.43
140.220.480.6720 $100\%$1.001.001.081.20
160.370.701.0820 $100\%$1.001.001.091.17
180.701.141.6219$95\%$1.011.031.061.15
200.781.122.2919 $95\%$1.011.031.071.12
Table 4.  Performance of algorithms HEU1 and PSA-GA in large problems; set High
CPU time (Sec.) for PSA-GACPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$
nminavgmaxminavgmaxavgmax
301.062.163.450.000.000.011.161.26
401.442.012.870.010.010.011.131.31
502.794.906.720.010.020.031.111.20
605.017.9611.060.000.010.041.111.21
706.4410.6314.450.010.020.041.111.25
8011.2918.6526.460.030.040.061.081.22
9010.4223.2336.600.020.040.071.071.14
10013.2919.3924.730.030.050.091.061.10
CPU time (Sec.) for PSA-GACPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$
nminavgmaxminavgmaxavgmax
301.062.163.450.000.000.011.161.26
401.442.012.870.010.010.011.131.31
502.794.906.720.010.020.031.111.20
605.017.9611.060.000.010.041.111.21
706.4410.6314.450.010.020.041.111.25
8011.2918.6526.460.030.040.061.081.22
9010.4223.2336.600.020.040.071.071.14
10013.2919.3924.730.030.050.091.061.10
Table 5.  Performance of algorithms HEU1 and PSA-GA in large problems; set Low
CPU time (Sec.) for PSA-GA CPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$
nminavgmaxminavgmaxavgmax
301.532.523.890.000.000.011.061.13
402.784.166.070.010.010.011.051.10
504.546.839.190.010.010.031.051.10
606.259.6512.780.000.020.031.031.06
708.4212.0719.630.020.030.041.031.09
8013.3417.4028.780.010.040.081.041.08
9015.3422.2428.780.030.060.091.031.07
10017.8238.9558.250.050.100.141.031.07
CPU time (Sec.) for PSA-GA CPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$
nminavgmaxminavgmaxavgmax
301.532.523.890.000.000.011.061.13
402.784.166.070.010.010.011.051.10
504.546.839.190.010.010.031.051.10
606.259.6512.780.000.020.031.031.06
708.4212.0719.630.020.030.041.031.09
8013.3417.4028.780.010.040.081.041.08
9015.3422.2428.780.030.060.091.031.07
10017.8238.9558.250.050.100.141.031.07
Table 6.  Results of the HEU1 algorithm; large-sized problem instances
CPU time (Sec.) set High CPU times(Sec.) set Low
nminavgmaxminavgmax
2000.080.130.170.220.250.30
4000.701.051.331.641.852.06
6002.313.033.645.606.136.55
606.259.6512.780.000.020.03
8005.537.108.6412.9714.4619.42
100011.1613.9816.3725.5532.0843.46
CPU time (Sec.) set High CPU times(Sec.) set Low
nminavgmaxminavgmax
2000.080.130.170.220.250.30
4000.701.051.331.641.852.06
6002.313.033.645.606.136.55
606.259.6512.780.000.020.03
8005.537.108.6412.9714.4619.42
100011.1613.9816.3725.5532.0843.46
[1]

T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53

[2]

Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435

[3]

Chuanli Zhao. An FPTAS for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033

[4]

Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219

[5]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[6]

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, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2018017

[7]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[8]

Muminu O. Adamu, Aderemi O. Adewumi. Minimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1465-1493. doi: 10.3934/jimo.2016.12.1465

[9]

Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279

[10]

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

[11]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457

[12]

Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1

[13]

Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059

[14]

Yang Woo Shin, Dug Hee Moon. Throughput of flow lines with unreliable parallel-machine workstations and blocking. Journal of Industrial & Management Optimization, 2017, 13 (2) : 901-916. doi: 10.3934/jimo.2016052

[15]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99

[16]

Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240

[17]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023

[18]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[19]

Liangliang Sun, Fangjun Luan, Yu Ying, Kun Mao. Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1431-1448. doi: 10.3934/jimo.2016081

[20]

Ping-Chen Lin. Portfolio optimization and risk measurement based on non-dominated sorting genetic algorithm. Journal of Industrial & Management Optimization, 2012, 8 (3) : 549-564. doi: 10.3934/jimo.2012.8.549

[Back to Top]