American Institute of Mathematical Sciences

Advanced
March  2021, 17(2): 533-548. doi: 10.3934/jimo.2019122

Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem

Guo Zhou 1, , Yongquan Zhou 2,, and  Ruxin Zhao 3,4,

1. 

Department of Science and Technology Teaching, China University of Political Science and Law, Beijing 100088, China
2. 

College of Information Science and Engineering, Guangxi University for Nationalities, Key Laboratories of Guangxi High Schools Complex System and Computational Intelligence, Nanning 530006, China
3. 

School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
4. 

College of Information Science and Engineering, Guangxi University for Nationalities, Nanning 530006, China

* Corresponding author: Yongquan Zhou

Received  July 2018 Revised  July 2019 Published  October 2019

The job-shop scheduling problem is one of the well-known hardest combinatorial optimization problems. The problem has captured the interest of a significant number of researchers, but no efficient solution algorithm has been found yet for solving it to optimality in polynomial time. In this paper, a hybrid social-spider optimization algorithm with differential mutation operator is presented to solve the job-shop scheduling problem. To improve the exploration capabilities of the social spider optimization algorithm (SSO), we incorporate the DM operator (a mutation operator taken from the deferential evolutionary (DE) algorithm) into the framework of the female cooperative operator. The experimental results show that the proposed method effectiveness in solving job-shop scheduling compared to other optimization algorithms in the literature.

Keywords: Social spider optimization, differential mutation operator, job-shop scheduling, metaheuristic optimization.
Mathematics Subject Classification: Primary: 78M50, 90C27.
Citation: Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
References:
[1]

R. F. Abdel-Kader, An improved PSO algorithm with genetic and neighborhood-based diversity operators for the job shop scheduling problem, Applied Artificial Intelligence, 32 (2018), 433-462.  doi: 10.1080/08839514.2018.1481903.  Google Scholar

[2]

M. Amirghasemi and R. Zamani, An effective asexual genetic algorithm for solving the job shop scheduling problem, Computers & Industrial Engineering, 83 (2015), 123-138.  doi: 10.1016/j.cie.2015.02.011.  Google Scholar

[3]

A. Elmi, M. Solimanpurb, S. Topaloglua and A. Elmic, A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts, Computers & Industrial Engineering, 61 (2011), 171-178.  doi: 10.1016/j.cie.2011.03.007.  Google Scholar

[4]

J. E. Beasley, Or-library: Distributing test problems by electronic mail, J. of the Operational Research Society, 41 (1990), 1069-1072.  doi: 10.2307/2582903.  Google Scholar

[5]

E. Cuevas, M. A. Díaz Cortés and D. A. O. Navarro, Advances of Evolutionary Computation: Methods and Operators, Studies in Computational Intelligence, 629, Springer, 2016, 9–33. doi: 10.1007/978-3-319-28503-0.  Google Scholar

[6]

E. Cuevas, M. Cienfuegos, R. Rojas and A. Padilla, Computational Intelligence Applications in Modeling and Control, Studies in Computational Intelligence, 575, Springer, 2015, 123–146. doi: 10.1007/978-3-319-11017-2.  Google Scholar

[7]

E. Cuevas, M. Cienfuegos, D. Zaldivar and M. Perez-Cisneros, A swarm optimization algorithm inspired in the behavior of the social-spider, Expert Systems with Applications, 40 (2013), 6374-6384.  doi: 10.1016/j.eswa.2013.05.041.  Google Scholar

[8]

E. Cuevas, V. Osuna and D. Oliva, Evolutionary Computation Techniques: A Comparative Perspective, Studies in Computational Intelligence, 686 (2017), 65–93. doi: 10.1007/978-3-319-51109-2.  Google Scholar

[9]

T. K. Dao, T. S. Pan and J. S. Pan, Parallel bat algorithm for optimizing makespan in job shop scheduling problems, J. of Intelligent Manufacturing, 29 (2018), 451-462.  doi: 10.1007/s10845-015-1121-x.  Google Scholar

[10]

N. Fiǧlali, C. Özkale, O. Engin A. and Fi ǧlali, Investigation of Ant System parameter interactions by using design of experiments for job-shop scheduling problems, Computers & Industrial Engineering, 56 (2009), 538-559.  doi: 10.1016/j.cie.2007.06.001.  Google Scholar

[11]

H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in Industrial Scheduling, Prentice Hall, 1963, 225–251. Google Scholar

[12]

L. Gao, X. Li, X. Wen, C. Lu and F. Wen, A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem, Computers & Industrial Engineering, 88 (2015), 417-429.  doi: 10.1016/j.cie.2015.08.002.  Google Scholar

[13]

A. S. Jain and S. Meeran, Deterministic job-shop scheduling: Past, present and future, European J. of Operational Research, 113 (1999), 390-434.  doi: 10.1016/S0377-2217(98)00113-1.  Google Scholar

[14]

S. Kavitha, P. Venkumar, N. Rajini and P. Pitchipoo, An efficient social spider optimization for flexible job shop scheduling problem, J. of Advanced Manufacturing Systems, 17 (2018), 181-196.  doi: 10.1142/S0219686718500117.  Google Scholar

[15]

M. Kurdi, A new hybrid island model genetic algorithm for job shop scheduling problem, Computers & Industrial Engineering, 88 (2015), 273-283.  doi: 10.1016/j.cie.2015.07.015.  Google Scholar

[16]

M. Kurdi, A Social Spider Optimization Algorithm for Hybrid Flow Shop Scheduling with Multiprocessor Task, 12th International NCM Conference: Challenges in Industrial Engineering & Operation Management, 2018. Google Scholar

[17]

M. Kurdi, An effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem, International J. of Intelligent Systems and Applications in Engineering, 7 (2019), 13-18.  doi: 10.18201/ijisae.2019751247.  Google Scholar

[18]

M. Kurdi, An effective new island model genetic algorithm for job shop scheduling problem, Comput. Oper. Res., 67 (2016), 132-142.  doi: 10.1016/j.cor.2015.10.005.  Google Scholar

[19]

M. Kurdi, An improved island model memetic algorithm with a new cooperation phase for multi-objective job shop scheduling problem, Computers & Industrial Engineering, 111 (2017), 183-201.  doi: 10.1016/j.cie.2017.07.021.  Google Scholar

[20]

T.-L. Lin, S.-J. Horng, T.-W. Kao, Y-.H. Chen, R.-S. Run, R.-J. Chen, J.-L. Lai and I.-H. Kuo, An efficient job-shop scheduling algorithm based on particle swarm optimization, Expert Systems with Applications, 37 (2010), 2629-2636.  doi: 10.1016/j.eswa.2009.08.015.  Google Scholar

[21]

M. Liu, Z.-J. Sun, J.-W. Yan and J.-S. Kang, An adaptive annealing genetic algorithm for the job-shop planning and scheduling problem, Expert Systems with Applications, 38 (2011), 9248-9255.  doi: 10.1016/j.eswa.2011.01.136.  Google Scholar

[22]

S. Lu, C. Sun and Z. Lu, An improved quantum-behaved particle swarm optimization method for short-term combined economic emission hydrothermal scheduling, Energy Conversion and Management, 51 (2010), 561-571.  doi: 10.1016/j.enconman.2009.10.024.  Google Scholar

[23]

T. B. Lubin, The Evolution of Sociality in Spiders, Advances in the Study of Behavior, 37 (2007), 83-145.  doi: 10.1016/S0065-3454(07)37003-4.  Google Scholar

[24]

A. Muthiah and R. Rajkumar, A novel algorithm for solving job-shop scheduling problem, Mechanika, 23 (2017), 610-617.  doi: 10.5755/j01.mech.23.4.14055.  Google Scholar

[25]

B. Naderi, S. M. T. Fatemi Ghomi, M. Aminnayeri and M. Zandieh, Scheduling open shops with parallel machines to minimize total completion time, J. Comput. Appl. Math., 5 (2011), 1275-1287.  doi: 10.1016/j.cam.2010.08.013.  Google Scholar

[26]

Y. Nagata and I. Ono, A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem, Comput. Oper. Res., 90 (2018), 60-71.  doi: 10.1016/j.cor.2017.09.017.  Google Scholar

[27]

S. Ouadfel and A. Taleb-Ahmed, Social spiders optimization and flower pollination algorithm for multilevel image thresholding: A performance study, Expert Syst. with Applications, 55 (2016), 566-584.  doi: 10.1016/j.eswa.2016.02.024.  Google Scholar

[28]

B. Peng, Z. Lü and T. C. E. Cheng, A tabu search/path relinking algorithm to solve the job shop scheduling problem, Comput. Oper. Res., 53 (2015), 154-164.  doi: 10.1016/j.cor.2014.08.006.  Google Scholar

[29]

P. Pongchairerks, A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem, Complexity, 1 (2019), 1-11.  doi: 10.1155/2019/8683472.  Google Scholar

[30]

A. Ponsich and C. A. Coello Coello, A hybrid Differential Evolution-Tabu Search algorithm for the solution of Job-Shop Scheduling Problems, Applied Soft Computing, 13 (2013), 462-474.  doi: 10.1016/j.asoc.2012.07.034.  Google Scholar

[31]

R. Qing-dao-er-ji and Y. Wang, A new hybrid genetic algorithm for job shop scheduling problem, Comput. Oper. Res., 39 (2012), 2291-2299.  doi: 10.1016/j.cor.2011.12.005.  Google Scholar

[32]

K. Rameshkumar and C. Rajendran, A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan, IOP Conference Series: Materials Science and Engineering, 310 (2018), 21-43.  doi: 10.1088/1757-899X/310/1/012143.  Google Scholar

[33]

F. Ramezani and S. Lotfi, Social-Based Algorithm (SBA), Applied Soft Computing, 13 (2013), 2837-2856.  doi: 10.1016/j.asoc.2012.05.018.  Google Scholar

[34]

R. Storn and K. Price, Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11 (1997), 341-359.  doi: 10.1023/A:1008202821328.  Google Scholar

[35]

C. J. Tan, S. C. Neoh, C. P. Lim, S. Hanoun, W. P. Wong, C. K. Loo and S. Nahavandi, Application of an evolutionary algorithm-based ensemble model to job-shop scheduling, J. of Intelligent Manufacturing, 30 (2019), 879-890.  doi: 10.1007/s10845-016-1291-1.  Google Scholar

[36]

R. F. Tavares Neto and M. Godinho Filho, Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research, Engineering Applications of Artificial Intelligence, 26 (2013), 150-161.  doi: 10.1016/j.engappai.2012.03.011.  Google Scholar

[37]

W. Teekeng and A. Thammano, Modified genetic algorithm for flexible job-shop scheduling problems, Procedia Computer Science, 12 (2012), 122-128.  doi: 10.1016/j.procs.2012.09.041.  Google Scholar

[38]

C. M. Xiang, Observation on the flying habits of social spiders, Chinese J. of Zoology, 3 (1986), 11-11.   Google Scholar

[39]

L.-N. Xing, Y.-W. Chen, P. Wang, Q.-S. Zhao and J. Xiong, A knowledge-based ant colony optimization for flexible job shop scheduling problems, Applied Soft Computing, 10 (2010), 888-896.  doi: 10.1016/j.asoc.2009.10.006.  Google Scholar

[40]

R. Yusof, M. Khalid, G. T. Hui and S. M. Yusof, Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm, Applied Soft Computing, 11 (2011), 5782-5792.  doi: 10.1016/j.asoc.2011.01.046.  Google Scholar

[41]

R. Zhang and C. Wu, A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective, Comput. Oper. Res., 38 (2011), 854-867.  doi: 10.1016/j.cor.2010.09.014.  Google Scholar

[42]

G. Zobolas, C. D. Tarantilis and G. loannou, A hybrid evolutionary algorithm for the job shop scheduling problem, J. of the Oper. Res. Society, 60 (2009), 221-235.  doi: 10.1057/palgrave.jors.2602534.  Google Scholar

[43]

G. I. Zobolas, C. D. Tarantilis and G. Ioannou, Exact, heuristic and meta-heuristic algorithms for solving job shop scheduling problems, in Metaheuristics for Scheduling in Industrial and Manufacturing Applications, Studies in Computational Intelligence, 2, Springer, Berlin, 2008, 19–40. doi: 10.1007/978-3-540-78985-7_1.  Google Scholar

show all references

References:
[1]

R. F. Abdel-Kader, An improved PSO algorithm with genetic and neighborhood-based diversity operators for the job shop scheduling problem, Applied Artificial Intelligence, 32 (2018), 433-462.  doi: 10.1080/08839514.2018.1481903.  Google Scholar

[2]

M. Amirghasemi and R. Zamani, An effective asexual genetic algorithm for solving the job shop scheduling problem, Computers & Industrial Engineering, 83 (2015), 123-138.  doi: 10.1016/j.cie.2015.02.011.  Google Scholar

[3]

A. Elmi, M. Solimanpurb, S. Topaloglua and A. Elmic, A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts, Computers & Industrial Engineering, 61 (2011), 171-178.  doi: 10.1016/j.cie.2011.03.007.  Google Scholar

[4]

J. E. Beasley, Or-library: Distributing test problems by electronic mail, J. of the Operational Research Society, 41 (1990), 1069-1072.  doi: 10.2307/2582903.  Google Scholar

[5]

E. Cuevas, M. A. Díaz Cortés and D. A. O. Navarro, Advances of Evolutionary Computation: Methods and Operators, Studies in Computational Intelligence, 629, Springer, 2016, 9–33. doi: 10.1007/978-3-319-28503-0.  Google Scholar

[6]

E. Cuevas, M. Cienfuegos, R. Rojas and A. Padilla, Computational Intelligence Applications in Modeling and Control, Studies in Computational Intelligence, 575, Springer, 2015, 123–146. doi: 10.1007/978-3-319-11017-2.  Google Scholar

[7]

E. Cuevas, M. Cienfuegos, D. Zaldivar and M. Perez-Cisneros, A swarm optimization algorithm inspired in the behavior of the social-spider, Expert Systems with Applications, 40 (2013), 6374-6384.  doi: 10.1016/j.eswa.2013.05.041.  Google Scholar

[8]

E. Cuevas, V. Osuna and D. Oliva, Evolutionary Computation Techniques: A Comparative Perspective, Studies in Computational Intelligence, 686 (2017), 65–93. doi: 10.1007/978-3-319-51109-2.  Google Scholar

[9]

T. K. Dao, T. S. Pan and J. S. Pan, Parallel bat algorithm for optimizing makespan in job shop scheduling problems, J. of Intelligent Manufacturing, 29 (2018), 451-462.  doi: 10.1007/s10845-015-1121-x.  Google Scholar

[10]

N. Fiǧlali, C. Özkale, O. Engin A. and Fi ǧlali, Investigation of Ant System parameter interactions by using design of experiments for job-shop scheduling problems, Computers & Industrial Engineering, 56 (2009), 538-559.  doi: 10.1016/j.cie.2007.06.001.  Google Scholar

[11]

H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in Industrial Scheduling, Prentice Hall, 1963, 225–251. Google Scholar

[12]

L. Gao, X. Li, X. Wen, C. Lu and F. Wen, A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem, Computers & Industrial Engineering, 88 (2015), 417-429.  doi: 10.1016/j.cie.2015.08.002.  Google Scholar

[13]

A. S. Jain and S. Meeran, Deterministic job-shop scheduling: Past, present and future, European J. of Operational Research, 113 (1999), 390-434.  doi: 10.1016/S0377-2217(98)00113-1.  Google Scholar

[14]

S. Kavitha, P. Venkumar, N. Rajini and P. Pitchipoo, An efficient social spider optimization for flexible job shop scheduling problem, J. of Advanced Manufacturing Systems, 17 (2018), 181-196.  doi: 10.1142/S0219686718500117.  Google Scholar

[15]

M. Kurdi, A new hybrid island model genetic algorithm for job shop scheduling problem, Computers & Industrial Engineering, 88 (2015), 273-283.  doi: 10.1016/j.cie.2015.07.015.  Google Scholar

[16]

M. Kurdi, A Social Spider Optimization Algorithm for Hybrid Flow Shop Scheduling with Multiprocessor Task, 12th International NCM Conference: Challenges in Industrial Engineering & Operation Management, 2018. Google Scholar

[17]

M. Kurdi, An effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem, International J. of Intelligent Systems and Applications in Engineering, 7 (2019), 13-18.  doi: 10.18201/ijisae.2019751247.  Google Scholar

[18]

M. Kurdi, An effective new island model genetic algorithm for job shop scheduling problem, Comput. Oper. Res., 67 (2016), 132-142.  doi: 10.1016/j.cor.2015.10.005.  Google Scholar

[19]

M. Kurdi, An improved island model memetic algorithm with a new cooperation phase for multi-objective job shop scheduling problem, Computers & Industrial Engineering, 111 (2017), 183-201.  doi: 10.1016/j.cie.2017.07.021.  Google Scholar

[20]

T.-L. Lin, S.-J. Horng, T.-W. Kao, Y-.H. Chen, R.-S. Run, R.-J. Chen, J.-L. Lai and I.-H. Kuo, An efficient job-shop scheduling algorithm based on particle swarm optimization, Expert Systems with Applications, 37 (2010), 2629-2636.  doi: 10.1016/j.eswa.2009.08.015.  Google Scholar

[21]

M. Liu, Z.-J. Sun, J.-W. Yan and J.-S. Kang, An adaptive annealing genetic algorithm for the job-shop planning and scheduling problem, Expert Systems with Applications, 38 (2011), 9248-9255.  doi: 10.1016/j.eswa.2011.01.136.  Google Scholar

[22]

S. Lu, C. Sun and Z. Lu, An improved quantum-behaved particle swarm optimization method for short-term combined economic emission hydrothermal scheduling, Energy Conversion and Management, 51 (2010), 561-571.  doi: 10.1016/j.enconman.2009.10.024.  Google Scholar

[23]

T. B. Lubin, The Evolution of Sociality in Spiders, Advances in the Study of Behavior, 37 (2007), 83-145.  doi: 10.1016/S0065-3454(07)37003-4.  Google Scholar

[24]

A. Muthiah and R. Rajkumar, A novel algorithm for solving job-shop scheduling problem, Mechanika, 23 (2017), 610-617.  doi: 10.5755/j01.mech.23.4.14055.  Google Scholar

[25]

B. Naderi, S. M. T. Fatemi Ghomi, M. Aminnayeri and M. Zandieh, Scheduling open shops with parallel machines to minimize total completion time, J. Comput. Appl. Math., 5 (2011), 1275-1287.  doi: 10.1016/j.cam.2010.08.013.  Google Scholar

[26]

Y. Nagata and I. Ono, A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem, Comput. Oper. Res., 90 (2018), 60-71.  doi: 10.1016/j.cor.2017.09.017.  Google Scholar

[27]

S. Ouadfel and A. Taleb-Ahmed, Social spiders optimization and flower pollination algorithm for multilevel image thresholding: A performance study, Expert Syst. with Applications, 55 (2016), 566-584.  doi: 10.1016/j.eswa.2016.02.024.  Google Scholar

[28]

B. Peng, Z. Lü and T. C. E. Cheng, A tabu search/path relinking algorithm to solve the job shop scheduling problem, Comput. Oper. Res., 53 (2015), 154-164.  doi: 10.1016/j.cor.2014.08.006.  Google Scholar

[29]

P. Pongchairerks, A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem, Complexity, 1 (2019), 1-11.  doi: 10.1155/2019/8683472.  Google Scholar

[30]

A. Ponsich and C. A. Coello Coello, A hybrid Differential Evolution-Tabu Search algorithm for the solution of Job-Shop Scheduling Problems, Applied Soft Computing, 13 (2013), 462-474.  doi: 10.1016/j.asoc.2012.07.034.  Google Scholar

[31]

R. Qing-dao-er-ji and Y. Wang, A new hybrid genetic algorithm for job shop scheduling problem, Comput. Oper. Res., 39 (2012), 2291-2299.  doi: 10.1016/j.cor.2011.12.005.  Google Scholar

[32]

K. Rameshkumar and C. Rajendran, A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan, IOP Conference Series: Materials Science and Engineering, 310 (2018), 21-43.  doi: 10.1088/1757-899X/310/1/012143.  Google Scholar

[33]

F. Ramezani and S. Lotfi, Social-Based Algorithm (SBA), Applied Soft Computing, 13 (2013), 2837-2856.  doi: 10.1016/j.asoc.2012.05.018.  Google Scholar

[34]

R. Storn and K. Price, Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11 (1997), 341-359.  doi: 10.1023/A:1008202821328.  Google Scholar

[35]

C. J. Tan, S. C. Neoh, C. P. Lim, S. Hanoun, W. P. Wong, C. K. Loo and S. Nahavandi, Application of an evolutionary algorithm-based ensemble model to job-shop scheduling, J. of Intelligent Manufacturing, 30 (2019), 879-890.  doi: 10.1007/s10845-016-1291-1.  Google Scholar

[36]

R. F. Tavares Neto and M. Godinho Filho, Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research, Engineering Applications of Artificial Intelligence, 26 (2013), 150-161.  doi: 10.1016/j.engappai.2012.03.011.  Google Scholar

[37]

W. Teekeng and A. Thammano, Modified genetic algorithm for flexible job-shop scheduling problems, Procedia Computer Science, 12 (2012), 122-128.  doi: 10.1016/j.procs.2012.09.041.  Google Scholar

[38]

C. M. Xiang, Observation on the flying habits of social spiders, Chinese J. of Zoology, 3 (1986), 11-11.   Google Scholar

[39]

L.-N. Xing, Y.-W. Chen, P. Wang, Q.-S. Zhao and J. Xiong, A knowledge-based ant colony optimization for flexible job shop scheduling problems, Applied Soft Computing, 10 (2010), 888-896.  doi: 10.1016/j.asoc.2009.10.006.  Google Scholar

[40]

R. Yusof, M. Khalid, G. T. Hui and S. M. Yusof, Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm, Applied Soft Computing, 11 (2011), 5782-5792.  doi: 10.1016/j.asoc.2011.01.046.  Google Scholar

[41]

R. Zhang and C. Wu, A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective, Comput. Oper. Res., 38 (2011), 854-867.  doi: 10.1016/j.cor.2010.09.014.  Google Scholar

[42]

G. Zobolas, C. D. Tarantilis and G. loannou, A hybrid evolutionary algorithm for the job shop scheduling problem, J. of the Oper. Res. Society, 60 (2009), 221-235.  doi: 10.1057/palgrave.jors.2602534.  Google Scholar

[43]

G. I. Zobolas, C. D. Tarantilis and G. Ioannou, Exact, heuristic and meta-heuristic algorithms for solving job shop scheduling problems, in Metaheuristics for Scheduling in Industrial and Manufacturing Applications, Studies in Computational Intelligence, 2, Springer, Berlin, 2008, 19–40. doi: 10.1007/978-3-540-78985-7_1.  Google Scholar

Figure 1.  FT20, Size = 100
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  LA40, Size = 225
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  ORB10, Size = 100
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  YN04, Size = 400
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  FT20, Size = 100
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  LA40, Size = 225
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  ORB10, Size = 100
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  YN04, Size = 400
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Notations for the JSSP
$ n $ the number of jobs
$ m $ the number of operations for one job
$ O_i $ the completion time of operation $ i $($ i=\{0, 1, 2, \dots, n*m+1\} $)
$ t_i $ the processing time of operation $ i $ on a given machine
$ \omega_{im} $ the flag of operation $ i $ initiated by machine $ m $
$ P_i $ all the predecessor operations of operation $ i $
$ A(t) $ the set of operations processed at time $ t $
$ o_{ji} $ the $ i $th operation of job $ j $
$ C_{\max} $ the makespan
Table Options

Download as excel

$ n $ the number of jobs
$ m $ the number of operations for one job
$ O_i $ the completion time of operation $ i $($ i=\{0, 1, 2, \dots, n*m+1\} $)
$ t_i $ the processing time of operation $ i $ on a given machine
$ \omega_{im} $ the flag of operation $ i $ initiated by machine $ m $
$ P_i $ all the predecessor operations of operation $ i $
$ A(t) $ the set of operations processed at time $ t $
$ o_{ji} $ the $ i $th operation of job $ j $
$ C_{\max} $ the makespan
Table 2.  Simulation results for FT, LA, ORB and YN
Name Size($ n*m $) Algorithm Best Worst Mean Std.
FT20 20*5 PSO 1374.00 1521.00 1442.50 42.02
IGA 1744.00 2527.00 2025.50 198.95
DE 1456.00 1554.00 1506.00 27.64
SSO 1527.00 1527.00 1527.00 0
SSO-DM 1374.00 1374.00 1374.00 0
LA40 15*15 PSO 1498.00 1732.00 1576.05 59.79
IGA 2154.00 2803.00 2340.25 155.90
DE 1691.00 1824.00 1767.05 36.46
SSO 1834.00 1834.00 1834.00 0
SSO-DM 1528.00 1528.00 1528.00 0
ORB10 10*10 PSO 1039.00 1263.00 1150.05 48.84
IGA 1431.00 2121.00 1761.25 158.12
DE 1190.00 1293.00 1244.40 25.04
SSO 1345.00 1345.00 1345.00 0
SSO-DM 1114.00 1114.00 1114.00 0
YN4 20*20 PSO 1340.00 1607.00 1425.15 64.84
IGA 1826.00 2192.00 1997.90 116.48
DE 1486.00 1601.00 1570.75 26.15
SSO 1583.00 1583.00 1583.00 0
SSO-DM 1492.00 1492.00 1492.00 0
Table Options

Download as excel

Name Size($ n*m $) Algorithm Best Worst Mean Std.
FT20 20*5 PSO 1374.00 1521.00 1442.50 42.02
IGA 1744.00 2527.00 2025.50 198.95
DE 1456.00 1554.00 1506.00 27.64
SSO 1527.00 1527.00 1527.00 0
SSO-DM 1374.00 1374.00 1374.00 0
LA40 15*15 PSO 1498.00 1732.00 1576.05 59.79
IGA 2154.00 2803.00 2340.25 155.90
DE 1691.00 1824.00 1767.05 36.46
SSO 1834.00 1834.00 1834.00 0
SSO-DM 1528.00 1528.00 1528.00 0
ORB10 10*10 PSO 1039.00 1263.00 1150.05 48.84
IGA 1431.00 2121.00 1761.25 158.12
DE 1190.00 1293.00 1244.40 25.04
SSO 1345.00 1345.00 1345.00 0
SSO-DM 1114.00 1114.00 1114.00 0
YN4 20*20 PSO 1340.00 1607.00 1425.15 64.84
IGA 1826.00 2192.00 1997.90 116.48
DE 1486.00 1601.00 1570.75 26.15
SSO 1583.00 1583.00 1583.00 0
SSO-DM 1492.00 1492.00 1492.00 0
Table 3.  Experimental results of running time of the algorithm
IGA PSO DE SSO SSO-DM
FT20 4.7350 1.3626 0.6521 0.7993 0.8725
LA40 4.2764 2.6175 1.0695 1.2537 1.2961
ORB10 2.7547 1.8100 1.1091 1.3127 1.0230
YN04 6.8851 3.0504 1.9461 2.3814 2.5842
Table Options

Download as excel

IGA PSO DE SSO SSO-DM
FT20 4.7350 1.3626 0.6521 0.7993 0.8725
LA40 4.2764 2.6175 1.0695 1.2537 1.2961
ORB10 2.7547 1.8100 1.1091 1.3127 1.0230
YN04 6.8851 3.0504 1.9461 2.3814 2.5842
Table 4.  $ p $-values produced by Wilcoxon's test comparing SSO-DM vs. PSO, SSO-DM vs. IGA, SSO-DM vs. DE and SSO-DM vs. SSO, over the "average best-so-far" (Mean) values from Table 1 to Table 4
PSO IGA DE SSO
FT20 7.9772E-09 8.0065E-09 4.0136E-03 4.6826E-10
LA40 7.9918E-09 7.9918E-09 8.0065E-09 4.6826E-10
ORB10 7.9918E-09 8.0065E-09 7.9772E-09 4.6826E-10
YN04 2.0993E-07 8.0065E-09 4.0289E-02 4.6826E-10
Table Options

Download as excel

PSO IGA DE SSO
FT20 7.9772E-09 8.0065E-09 4.0136E-03 4.6826E-10
LA40 7.9918E-09 7.9918E-09 8.0065E-09 4.6826E-10
ORB10 7.9918E-09 8.0065E-09 7.9772E-09 4.6826E-10
YN04 2.0993E-07 8.0065E-09 4.0289E-02 4.6826E-10
[1]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008
[2]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008
[3]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[4]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[5]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[6]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[7]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[8]

Gheorghe Craciun, Abhishek Deshpande, Hyejin Jenny Yeon. Quasi-toric differential inclusions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2343-2359. doi: 10.3934/dcdsb.2020181
[9]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[10]

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
[11]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020
[12]

Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277
[13]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203
[14]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409
[15]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192
[16]

Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175
[17]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213
[18]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[19]

Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200
[20]

Changpin Li, Zhiqiang Li. Asymptotic behaviors of solution to partial differential equation with Caputo–Hadamard derivative and fractional Laplacian: Hyperbolic case. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021023

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (161)
  • HTML views (540)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences