In the current global cooperative production environment, modern industries are confronted with intricate production plans, demanding the adoption of contemporary production scheduling strategies. Within this context, distributed manufacturing has emerged as a prominent trend. Manufacturing enterprises, especially those engaged in activities like automotive mold production and welding, are facing a significant challenge in managing a significant amount of small-scale tasks characterized by short processing times. In this situation, it becomes imperative to consider the transportation time of jobs between machines. This paper simultaneously considers the transportation time of jobs between machines and the start-stop operation of the machines, which is the first time to our knowledge. An improved memetic algorithm (IMA) is proposed to solve the multi-objective distributed flexible job shop scheduling problem (MODFJSP) with the goal of minimizing maximum completion time and energy consumption. Then, a new multi-start simulated annealing algorithm is proposed and integrated into the IMA to improve the exploration ability and diversity of the algorithm. Furthermore, a new multiple-initialization rule is designed to enhance the quality of the initial population. Additionally, four improved variable neighborhood search strategies and two energy-saving strategies are designed to enhance the search ability and reduce energy consumption. To verify the effectiveness of the IMA, we conducted extensive testing and comprehensive evaluation on 20 instances. The results indicate that, when faced with the MODFJSP, the IMA can achieve better solutions in almost all instances, which is of great significance for the improvement of production scheduling in intelligent manufacturing.
Citation: Yifan Gu, Hua Xu, Jinfeng Yang, Rui Li. An improved memetic algorithm to solve the energy-efficient distributed flexible job shop scheduling problem with transportation and start-stop constraints[J]. Mathematical Biosciences and Engineering, 2023, 20(12): 21467-21498. doi: 10.3934/mbe.2023950
In the current global cooperative production environment, modern industries are confronted with intricate production plans, demanding the adoption of contemporary production scheduling strategies. Within this context, distributed manufacturing has emerged as a prominent trend. Manufacturing enterprises, especially those engaged in activities like automotive mold production and welding, are facing a significant challenge in managing a significant amount of small-scale tasks characterized by short processing times. In this situation, it becomes imperative to consider the transportation time of jobs between machines. This paper simultaneously considers the transportation time of jobs between machines and the start-stop operation of the machines, which is the first time to our knowledge. An improved memetic algorithm (IMA) is proposed to solve the multi-objective distributed flexible job shop scheduling problem (MODFJSP) with the goal of minimizing maximum completion time and energy consumption. Then, a new multi-start simulated annealing algorithm is proposed and integrated into the IMA to improve the exploration ability and diversity of the algorithm. Furthermore, a new multiple-initialization rule is designed to enhance the quality of the initial population. Additionally, four improved variable neighborhood search strategies and two energy-saving strategies are designed to enhance the search ability and reduce energy consumption. To verify the effectiveness of the IMA, we conducted extensive testing and comprehensive evaluation on 20 instances. The results indicate that, when faced with the MODFJSP, the IMA can achieve better solutions in almost all instances, which is of great significance for the improvement of production scheduling in intelligent manufacturing.
| [1] |
J. Yang, H. Xu, J. Cheng, R. Li, Y. Gu, A decomposition-based memetic algorithm to solve the biobjective green flexible job shop scheduling problem with interval type-2 fuzzy processing time, Comput. Ind. Eng., 183 (2023), 109513, https://doi.org/10.1016/j.cie.2023.109513 doi: 10.1016/j.cie.2023.109513
|
| [2] |
J. Xie, X. Li, L. Gao, L. Gui, A hybrid algorithm with a new neighborhood structure for job shop scheduling problems, Comput. Ind. Eng., 169 (2022), 108205, https://doi.org/10.1016/j.cie.2022.108205 doi: 10.1016/j.cie.2022.108205
|
| [3] |
G. Zhang, J. Sun, X. Liu, G. Wang, Y. Yang, Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm, Math. Biosci. Eng., 16 (2019), 1334–1347. https://doi.org/10.3934/mbe.2019065 doi: 10.3934/mbe.2019065
|
| [4] |
E. Jiang, L. Wang, Z. Peng, Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition, Swarm Evol. Comput., 58 (2020), 100745. https://doi.org/10.1016/j.swevo.2020.100745 doi: 10.1016/j.swevo.2020.100745
|
| [5] |
C. Lu, J. Zheng, L. Yin, R. Wang, An improved iterated greedy algorithm for the distributed hybrid flowshop scheduling problem, Eng. Optim., (2023), 1–19. https://doi.org/10.1080/0305215X.2023.2198768 doi: 10.1080/0305215X.2023.2198768
|
| [6] |
J. Yang, H. Xu, Hybrid memetic algorithm to solve multiobjective distributed fuzzy flexible job shop scheduling problem with transfer, Processes, 10 (2022), 1517. https://doi.org/10.3390/pr10081517 doi: 10.3390/pr10081517
|
| [7] |
D. Lei, J. Cai, Multi-population meta-heuristics for production scheduling: A survey, Swarm Evol. Comput., 58 (2020), 100739. https://doi.org/10.1016/j.swevo.2020.100739 doi: 10.1016/j.swevo.2020.100739
|
| [8] |
Q. Liu, Q. Pan, L. Gao, X. Li, Multi-objective flexible job shop scheduling problem considering machine switching off-on operation, Procedia Manuf., 39 (2019), 1167–1176. https://doi.org/10.1016/j.promfg.2020.01.353 doi: 10.1016/j.promfg.2020.01.353
|
| [9] |
S. Lin, K. Ying, Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm, Comput. Oper. Res., 40 (2013), 1625–1647. https://doi.org/10.1016/j.cor.2011.08.009 doi: 10.1016/j.cor.2011.08.009
|
| [10] |
G. Zhang, J. Sun, X. Lu, H. Zhang, An improved memetic algorithm for the flexible job shop scheduling problem with transportation times, Meas. Control, 53 (2020), 1518–1528. https://doi.org/10.1177/0020294020948094 doi: 10.1177/0020294020948094
|
| [11] |
L. Asadzadeh, A local search genetic algorithm for the job shop scheduling problem with intelligent agents, Comput. Ind. Eng., 85 (2015), 376–383. https://doi.org/10.1016/j.cie.2015.04.006 doi: 10.1016/j.cie.2015.04.006
|
| [12] |
M. Kurdi, An effective new island model genetic algorithm for job shop scheduling problem, Comput. Oper. Res., 67 (2016), 132–142. https://doi.org/10.1016/j.cor.2015.10.005 doi: 10.1016/j.cor.2015.10.005
|
| [13] |
M. E. Aydin, T. C. Fogarty, A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems, J. Heuristics, 10 (2004), 269–292. https://doi.org/10.1023/B:HEUR.0000026896.44360.f9 doi: 10.1023/B:HEUR.0000026896.44360.f9
|
| [14] |
J. Zhang, W. Wang, X. Xu, A hybrid discrete particle swarm optimization for dual-resource constrained job shop scheduling with resource flexibility, J. Intell. Manuf., 28 (2017), 1961–1972. https://doi.org/10.1007/s10845-015-1082-0 doi: 10.1007/s10845-015-1082-0
|
| [15] |
I. Chaouch, O. B. Driss, K. Ghedira, A modified ant colony optimization algorithm for the distributed job shop scheduling problem, Proc. Comput. Sci., 112 (2017), 296–305. https://doi.org/10.1016/j.procs.2017.08.267 doi: 10.1016/j.procs.2017.08.267
|
| [16] |
S. Gopinath, C. Arumugam, T. Page, M. Chandrasekaran, Solving multi objective job shop scheduling problems using artificial immune system shifting bottleneck approach, Appl. Mech. Mater., 766 (2015), 1209–1213. https://doi.org/10.4028/www.scientific.net/AMM.766-767.1209 doi: 10.4028/www.scientific.net/AMM.766-767.1209
|
| [17] |
L. Asadzadeh, A parallel artificial bee colony algorithm for the job shop scheduling problem with a dynamic migration strategy, Comput. Ind. Eng., 102 (2016), 359–367. https://doi.org/10.1016/j.cie.2016.06.025 doi: 10.1016/j.cie.2016.06.025
|
| [18] | H. Piroozfard, K. Y. Wong, An imperialist competitive algorithm for the job shop scheduling problems, in 2014 IEEE International Conference on Industrial Engineering and Engineering Management, (2014), 69–73. https://doi.org/10.1109/IEEM.2014.7058602 |
| [19] | P. Moscato, Memetic Algorithms: A Short Introduction, McGraw-Hill, Maidenhead, 1999. |
| [20] |
A. Phu-ang, A. Thammano, Memetic algorithm based on marriage in honey bees optimization for flexible job shop scheduling problem, Memetic Comput., 9 (2017), 295–309. https://doi.org/10.1007/s12293-017-0230-9 doi: 10.1007/s12293-017-0230-9
|
| [21] |
C. Zhang, P. Li, Z. Guan, Y. Rao, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Comput. Oper. Res., 34 (2007), 3229–3242. https://doi.org/10.1016/j.cor.2005.12.002 doi: 10.1016/j.cor.2005.12.002
|
| [22] |
R. Li, L. Wang, W. Gong, Knowledge-driven memetic algorithm for distributed green flexible job shop scheduling problem, J. Huazhong Univ. Sci. Technol., Nat. Sci. Ed., 50 (2022), 55–60. https://doi.org/10.13245/j.hust.220606 doi: 10.13245/j.hust.220606
|
| [23] |
C. Lu, L. Gao, W. Gong, C. Hu, X. Yan, X. Li, Sustainable scheduling of distributed permutation flow-shop with non-identical factory using a knowledge-based multi-objective memetic optimization algorithm, Swarm Evol. Comput., 60 (2021), 100803. https://doi.org/10.1016/j.swevo.2020.100803 doi: 10.1016/j.swevo.2020.100803
|
| [24] |
Y. Pan, K. Gao, Z. Li, N. Wu, Solving biobjective distributed flow-shop scheduling problems with lot-streaming using an improved Jaya algorithm, IEEE Trans. Cybern., 53 (2023), 3818–3828. https://doi.org/10.1109/TCYB.2022.3164165 doi: 10.1109/TCYB.2022.3164165
|
| [25] |
R. Li, W. Gong, L. Wang, C. Lu, X. Zhuang, Surprisingly popular-based adaptive memetic algorithm for energy-efficient distributed flexible job shop scheduling, IEEE Trans. Cybern., 53 (2003), 8013–8023. https://doi.org/10.1109/TCYB.2023.3280175 doi: 10.1109/TCYB.2023.3280175
|
| [26] |
Q. Luo, Q. Deng, G. Gong, L. Zhang, W. Han, K. Li, An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers, Expert Syst. Appl., 160 (2020), 113721. https://doi.org/10.1016/j.eswa.2020.113721 doi: 10.1016/j.eswa.2020.113721
|
| [27] |
H. Chang, T. Liu, Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms, J. Intell. Manuf., 28 (2017), 1973–1986. https://doi.org/10.1007/s10845-015-1084-y doi: 10.1007/s10845-015-1084-y
|
| [28] |
K. Zhu, G. Gong, N. Peng, L. Zhang, D. Huang, Q. Luo, et al., Dynamic distributed flexible job-shop scheduling problem considering operation inspection, Expert Syst. Appl., 224 (2023), 119840. https://doi.org/10.1016/j.eswa.2023.119840 doi: 10.1016/j.eswa.2023.119840
|
| [29] |
B. Marzouki, O. B. Driss, K. Ghédira, Solving distributed and flexible job shop scheduling problem using a chemical reaction optimization metaheuristic, Procedia Comput. Sci., 126 (2018), 1424–1433. https://doi.org/10.1016/j.procs.2018.08.114 doi: 10.1016/j.procs.2018.08.114
|
| [30] |
C. Lu, B. Zhang, L. Gao, J. Yi, J. Mou, A knowledge-based multiobjective memetic algorithm for green job shop scheduling with variable machining speeds, IEEE Syst. J., 16 (2022), 844–855. https://doi.org/10.1109/JSYST.2021.3076481 doi: 10.1109/JSYST.2021.3076481
|
| [31] |
F. Zhao, S. Di, L. Wang, A hyperheuristic with Q-learning for the multiobjective energy-efficient distributed blocking flow shop scheduling problem, IEEE Trans. Cybern., 53 (2023), 3337–3350. https://doi.org/10.1109/TCYB.2022.3192112 doi: 10.1109/TCYB.2022.3192112
|
| [32] |
C. Lu, L. Gao, J. Yi, X. Li, Energy-efficient scheduling of distributed flow shop with heterogeneous factories: A real-world case from automobile industry in China, IEEE Trans. Ind. Inf., 17 (2021), 6687–6696. https://doi.org/10.1109/TII.2020.3043734 doi: 10.1109/TII.2020.3043734
|
| [33] |
X. Gong, T. De Pessemier, L. Martens, W. Joseph, Energy- and labor-aware flexible job shop scheduling under dynamic electricity pricing: A many-objective optimization investigation, J. Cleaner Prod., 209 (2019), 1078–1094. https://doi.org/10.1016/j.jclepro.2018.10.289 doi: 10.1016/j.jclepro.2018.10.289
|
| [34] |
X. Wu, Y. Sun, A green scheduling algorithm for flexible job shop with energy-saving measures, J. Cleaner Prod., 172 (2018), 3249–3264. https://doi.org/10.1016/j.jclepro.2017.10.342 doi: 10.1016/j.jclepro.2017.10.342
|
| [35] |
N. Rakovitis, D. Li, N. Zhang, J. Li, X. Xiao, Novel approach to energy-efficient flexible job-shop scheduling problems, Energy, 238 (2022), 121773. https://doi.org/10.1016/j.energy.2021.121773 doi: 10.1016/j.energy.2021.121773
|
| [36] |
E. Xu, Y. Li, Y. Liu, J. Du, X. Gao, Energy saving scheduling strategy for job shop under TOU and tiered electricity price, Alexandria Eng. J., 61 (2022), 459–467. https://doi.org/10.1016/j.aej.2021.06.008 doi: 10.1016/j.aej.2021.06.008
|
| [37] |
Y. Li, W. Huang, R. Wu, K. Guo, An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem, Appl. Soft Comput., 95 (2020), 106544. https://doi.org/10.1016/j.asoc.2020.106544 doi: 10.1016/j.asoc.2020.106544
|
| [38] |
L. Wang, D. Zheng A modified genetic algorithm for job shop scheduling, Int. J. Adv. Manuf. Technol., 20 (2002), 72–76. https://doi.org/10.1007/s001700200126 doi: 10.1007/s001700200126
|
| [39] |
K. Ying, S. Lin, Minimizing total completion time in the no-wait jobshop scheduling problem using a backtracking metaheuristic, Comput. Ind. Eng., 169 (2022), 108238. https://doi.org/10.1016/j.cie.2022.108238 doi: 10.1016/j.cie.2022.108238
|
| [40] |
G. Gong, R. Chiong, Q. Deng, Q. Luo, A memetic algorithm for multi-objective distributed production scheduling: minimizing the makespan and total energy consumption, J. Intell. Manuf., 31 (2020), 1443–1466. https://doi.org/10.1007/s10845-019-01521-9 doi: 10.1007/s10845-019-01521-9
|
| [41] |
K. Gao, Z. Cao, L. Zhang, Z. Chen, Y. Han, Q. Pan, A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems, IEEE/CAA J. Autom. Sin., 6 (2019), 904–916. https://doi.org/10.1109/JAS.2019.1911540 doi: 10.1109/JAS.2019.1911540
|
| [42] |
I. Chaouch, O. B. Driss, K. Ghedira, A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm, Appl. Intell., 49 (2019), 1903–1924. https://doi.org/10.1007/s10489-018-1343-7 doi: 10.1007/s10489-018-1343-7
|
Figures(23) / Tables(9)
Yifan Gu, Hua Xu, Jinfeng Yang, Rui Li. An improved memetic algorithm to solve the energy-efficient distributed flexible job shop scheduling problem with transportation and start-stop constraints[J]. Mathematical Biosciences and Engineering, 2023, 20(12): 21467-21498. doi: 10.3934/mbe.2023950
DownLoad: