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

Guo Zhou; Yongquan Zhou; Ruxin Zhao

doi:10.3934/jimo.2019122

Previous Article
Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization
JIMO Home
This Issue
Next Article
Collaborative environmental management for transboundary air pollution problems: A differential levies game

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 March 2021 Early access 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 and 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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in Industrial Scheduling, Prentice Hall, 1963, 225–251.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[29]	P. Pongchairerks, A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem, Complexity, 1 (2019), 1-11. doi: 10.1155/2019/8683472.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[38]	C. M. Xiang, Observation on the flying habits of social spiders, Chinese J. of Zoology, 3 (1986), 11-11.
[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.
[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.
[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.
[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.
[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.

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in Industrial Scheduling, Prentice Hall, 1963, 225–251.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[29]	P. Pongchairerks, A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem, Complexity, 1 (2019), 1-11. doi: 10.1155/2019/8683472.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[38]	C. M. Xiang, Observation on the flying habits of social spiders, Chinese J. of Zoology, 3 (1986), 11-11.
[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.
[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.
[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.
[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.
[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.

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]	Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[2]	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 and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[3]	Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[4]	Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[5]	Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029
[6]	Soheil Dolatabadi. Weighted vertices optimizer (WVO): A novel metaheuristic optimization algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 461-479. doi: 10.3934/naco.2018029
[7]	Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469
[8]	Qiong Liu, Jialiang Liu, Zhaorui Dong, Mengmeng Zhan, Zhen Mei, Baosheng Ying, Xinyu Shao. Integrated optimization of process planning and scheduling for reducing carbon emissions. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1025-1055. doi: 10.3934/jimo.2020010
[9]	Zhenhuan Yang, Yiming Ying, Qilong Min. Online optimization for residential PV-ESS energy system scheduling. Mathematical Foundations of Computing, 2019, 2 (1) : 55-71. doi: 10.3934/mfc.2019005
[10]	Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021142
[11]	Wenjuan Zhao, Shunfu Jin, Wuyi Yue. A stochastic model and social optimization of a blockchain system based on a general limited batch service queue. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1845-1861. doi: 10.3934/jimo.2020049
[12]	Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete and Continuous Dynamical Systems, 2021, 41 (6) : 2907-2946. doi: 10.3934/dcds.2020391
[13]	Xing Wang, Chang-Qi Tao, Guo-Ji Tang. Differential optimization in finite-dimensional spaces. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1495-1505. doi: 10.3934/jimo.2016.12.1495
[14]	Bun Theang Ong, Masao Fukushima. Global optimization via differential evolution with automatic termination. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 57-67. doi: 10.3934/naco.2012.2.57
[15]	Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial and Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253
[16]	M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial and Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445
[17]	Zhiyuan Wen, Meirong Zhang. On the optimization problems of the principal eigenvalues of measure differential equations with indefinite measures. Discrete and Continuous Dynamical Systems - B, 2020, 25 (8) : 3257-3274. doi: 10.3934/dcdsb.2020061
[18]	Youssef El Hadfi, Zhaosheng Feng, Abdelghani Ghazdali, Amine Laghrib. Preface to the special issue "Partial Differential Equations, Optimization and their Applications". Discrete and Continuous Dynamical Systems - S, 2022, 15 (1) : i-ii. doi: 10.3934/dcdss.2021163
[19]	Oliver Jenkinson. Ergodic Optimization. Discrete and Continuous Dynamical Systems, 2006, 15 (1) : 197-224. doi: 10.3934/dcds.2006.15.197
[20]	Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

2020 Impact Factor: 1.801

Tools

Metrics

Tools

Article outline

Figures and Tables

2020 Impact Factor: 1.801

Tools

Figures and Tables

2020 Impact Factor: 1.801

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors