Dynamic and Heterogeneous Identity-Based Cooperative Co-Evolution for Distributed Lot-Streaming Flowshop Scheduling Problem
), Abstract
In this research, a novel dynamic and heterogeneous identity based cooperative co-evolutionary algorithm (DHICCA) is proposed for addressing the distributed lot-streaming flowshop scheduling problem (DLSFSP) with the objective to minimize the makespan. A two-layer-vector representation is devised to bridge the solution space of DLSFSP and the search space of DHICCA. In the evolution of DHICCA, population individuals are endowed with heterogeneous identities according to their quality, including superior individuals, ordinary individuals, and inferior individuals, which serve local exploitation, global exploration, and diversified restart, respectively. Because individuals with different identities require different evolutionary mechanisms to fully unleash their respective potentials, identity-specific evolutionary operators are devised to evolve them in a cooperative co-evolutionary way. This is important to use limited population resources to solve complex optimization problems. Specifically, exploitation is carried out on superior individuals by devising three exploitative operators with different intensities based on techniques of variable neighborhood, destruction-construction, and gene targeting. Exploration is executed on ordinary individuals by a newly constructed discrete Jaya algorithm and a probability crossover strategy. In addition, restart is performed on inferior individuals to introduce new evolutionary individuals to the population. After the cooperative co-evolution, all individuals with different identities are merged as a population again, and their identities are dynamically adjusted by new evaluation. The influence of parameters on the algorithm is investigated based on design-of-experiment and comprehensive computational experiments are used to evaluate the performance of all algorithms. The results validate the effectiveness of special designs and show that DHICCA performs more efficient than the existing state-of-the-art algorithms in solving the DLSFSP.
Keywords
References
C. E. Okwudire and H. V. Madhyastha, Distributed manufacturing for and by the masses, Science, vol. 372, no. 6540, pp. 341–342, 2021.
B. Naderi and R. Ruiz, The distributed permutation flowshop scheduling problem, Comput. Oper. Res., vol. 37, no. 4, pp. 754–768, 2010
P. Perez-Gonzalez and J. M. Framinan, A review and classification on distributed permutation flowshop scheduling problems, Eur. J. Oper. Res., vol. 312, no. 1, pp. 1–21, 2024.
N. Bagheri Rad and J. Behnamian, Recent trends in distributed production network scheduling problem, Artif. Intell. Rev., vol. 55, no. 4, pp. 2945–2995, 2022
S. Wang, Y. Feng, X. Li, and G. Zhang, Memetic discrete differential evolution with domain knowledge for blocking scheduling distributed flow shop with lot-streaming constraints, Expert Syst. Appl., vol. 255, p. 124874, 2024.
Y. Pan, K. Gao, Z. Li, and N. Wu, Solving biobjective distributed flow-shop scheduling problems with lot-streaming using an improved jaya algorithm, IEEE Trans. Cybern., vol. 53, no. 6, pp. 3818–3828, 2023.
G. Zhang, K. Xing, and F. Cao, Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion, Eng. Appl. Artif. Intell., vol. 76, pp. 96–107, 2007.
R. Li, W. Gong, L. Wang, C. Lu, Z. Pan, and X. Zhuang, Double DQN-based coevolution for green distributed heterogeneous hybrid flowshop scheduling with multiple priorities of jobs, IEEE Trans. Autom. Sci. Eng., vol. 21, no. 4, pp. 6550–6562, 2024.
V. Fernandez-Viagas, P. Perez-Gonzalez, and J. M. Framinan, The distributed permutation flow shop to minimise the total flowtime, Comput. Ind. Eng., vol. 118, pp. 464–477, 2018.
C. Zhao, L. Wu, C. Zuo, and H. Zhang, An improved fruit fly optimization algorithm with Q-learning for solving distributed permutation flow shop scheduling problems, Complex Intell. Syst., vol. 10, no. 5, pp. 5965–5988, 2024.
D. Bai, T. Liu, Y. Zhang, F. Chu, H. Qin, L. Gao, Y. Su, and M. Huang, Scheduling a distributed permutation flowshop with uniform machines and release dates, IEEE Trans. Automat. Sci. Eng., vol. 22, pp. 215–227, 2025.
F. Zhao, G. Zhou, and L. Wang, A cooperative scatter search with reinforcement learning mechanism for the distributed permutation flowshop scheduling problem with sequence-dependent setup times, IEEE Trans. Syst. Man Cybern. Syst., vol. 53, no. 8, pp. 4899–4911, 2023.
W. Zhang, H. Geng, C. Li, M. Gen, G. Zhang, and M. Deng, Q-learning-based multi-objective particle swarm optimization with local search within factories for energy-efficient distributed flow-shop scheduling problem, J. Intell. Manuf., vol. 36, no. 1, pp. 185–208, 2025.
Q. Y. Li, Q. K. Pan, H. Y. Sang, X. L. Jing, J. M. Framiñán, and W. M. Li, Self-adaptive population-based iterated greedy algorithm for distributed permutation flowshop scheduling problem with part of jobs subject to a common deadline constraint, Expert Syst. Appl., vol. 248, p. 123278, 2024.
X. He, Q. K. Pan, L. Gao, J. S. Neufeld, and J. N. D. Gupta, Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times, Omega, vol. 123, p. 102997, 2024.
H. Li, X. Li, and L. Gao, An iterated greedy algorithm with acceleration of job allocation probability for distributed heterogeneous permutation flowshop scheduling problem, Swarm Evol. Comput., vol. 88, p. 101580, 2024.
J. J. Wang and L. Wang, A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop, IEEE Trans. Syst. Man Cybern. Syst., vol. 50, no. 5, pp. 1805–1819, 2020.
X. L. Jing, Q. K. Pan, L. Gao, and L. Wang, An effective iterated greedy algorithm for a robust distributed permutation flowshop problem with carryover sequence-dependent setup time, IEEE Trans. Syst. Man Cybern. Syst., vol. 52, no. 9, pp. 5783–5794, 2022.
G. Zhang, L. Wang, and K. Xing, Dual-space co-evolutionary memetic algorithm for scheduling hybrid differentiation flowshop with limited buffer constraints, IEEE Trans. Syst. Man Cybern. Syst., vol. 52, no. 11, pp. 6822–6836, 2022.
G. Zhang and K. Xing, Differential evolution metaheuristics for distributed limited-buffer flowshop scheduling with makespan criterion, Comput. Oper. Res., vol. 108, pp. 33–43, 2019.
G. Zhang, K. Xing, and F. Cao, Scheduling distributed flowshops with flexible assembly and set-up time to minimise makespan, Int. J. Prod. Res., vol. 56, no. 9, pp. 3226–3244, 2018.
G. Zhang and K. Xing, Memetic social spider optimization algorithm for scheduling two-stage assembly flowshop in a distributed environment, Comput. Ind. Eng., vol. 125, pp. 423–433, 2018.
C. T. Tseng and C. J. Liao, A discrete particle swarm optimization for lot-streaming flowshop scheduling problem, Eur. J. Oper. Res., vol. 191, no. 2, pp. 360–373, 2008.
Y. Han, J. Q. Li, D. Gong, and H. Sang, Multi-objective migrating birds optimization algorithm for stochastic lot-streaming flow shop scheduling with blocking, IEEE Access, vol. 7, pp. 5946–5962, 2018.
Q. K. Pan and R. Ruiz, An estimation of distribution algorithm for lot-streaming flow shop problems with setup times, Omega, vol. 40, no. 2, pp. 166–180, 2012.
Q. K. Pan, P. N. Suganthan, J. J. Liang, and M. F. Tasgetiren, A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem, Expert Syst. Appl., vol. 38, no. 4, pp. 3252–3259, 2011.
W. Wang, Z. Xu, and X. Gu, A two-stage discrete water wave optimization algorithm for the flowshop lot-streaming scheduling problem with intermingling and variable lot sizes, Knowl. Based Syst., vol. 238, p. 107874, 2022.
Y. Li, C. Liao, L. Wang, Y. Xiao, Y. Cao, and S. Guo, A reinforcement learning-artificial bee colony algorithm for flexible job-shop scheduling problem with lot streaming, Appl. Soft Comput., vol. 146, p. 110658, 2023.
C. Li, Y. Han, B. Zhang, Y. Wang, J. Li, and K. Gao, A novel collaborative iterative greedy algorithm for hybrid flowshop scheduling problem with batch processing machines and variable sublots, Int. J. Prod. Res., vol. 62, no. 11, pp. 4076–4096, 2024.
Y. Pan, K. Gao, Z. Li, and N. Wu, Improved meta-heuristics for solving distributed lot-streaming permutation flow shop scheduling problems, IEEE Trans. Autom. Sci. Eng., vol. 20, no. 1, pp. 361–371, 2023.
S. Chen, X. Wang, Y. Wang, and X. Gu, A modified adaptive switching-based many-objective evolutionary algorithm for distributed heterogeneous flowshop scheduling with lot-streaming, Swarm Evol. Comput., vol. 81, p. 101353, 2023.
X. Ma, X. Li, Q. Zhang, K. Tang, Z. Liang, and W. Xie, A survey on cooperative co-evolutionary algorithms, IEEE Transactions on Evolutionary Computation, vol. 23, no. 3, pp. 421–441, 2019.
M. A. Potter and K. A. D. Jong, Cooperative coevolution: An architecture for evolving coadapted subcomponents, Evol. Comput., vol. 8, no. 1, pp. 1–29, 2000.
M. Yang, J. Gao, A. Zhou, C. Li, and X. Yao, Contribution-based cooperative co-evolution with adaptive population diversity for large-scale global optimization [research frontier], IEEE Comput. Intell. Mag., vol. 18, no. 3, pp. 56–68, 2023.
S. Qin, D. Pi, Z. Shao, and Y. Xu, A cluster-based cooperative co-evolutionary algorithm for multiobjective workflow scheduling in a cloud environment, IEEE Trans. Autom. Sci. Eng., vol. 20, no. 3, pp. 1648–1662, 2023.
T. Guo, Y. Mei, K. Tang, and W. Du, Cooperative co-evolution for large-scale multiobjective air traffic flow management, IEEE Trans. Evol. Comput., vol. 28, no. 6, pp. 1644–1658, 2024.
W. N. Chen, Y. H. Jia, F. Zhao, X. N. Luo, X. D. Jia, and J. Zhang, A cooperative co-evolutionary approach to large-scale multisource water distribution network optimization, IEEE Trans. Evol. Comput., vol. 23, no. 5, pp. 842–857, 2019.
G. Zhang, B. Liu, L. Wang, and K. Xing, Distributed heterogeneous co-evolutionary algorithm for scheduling a multistage fine-manufacturing system with setup constraints, IEEE Trans. Cybern., vol. 54, no. 3, pp. 1497–1510, 2024.
X. He, Q. K. Pan, L. Gao, L. Wang, and P. N. Suganthan, A greedy cooperative co-evolutionary algorithm with problem-specific knowledge for multiobjective flowshop group scheduling problems, IEEE Trans. Evol. Comput., vol. 27, no. 3, pp. 430–444, 2023.
G. Zhang, X. Ma, L. Wang, and K. Xing, Elite archive-assisted adaptive memetic algorithm for a realistic hybrid differentiation flowshop scheduling problem, IEEE Trans. Evol. Comput., vol. 26, no. 1, pp. 100–114, 2022.
Q. K. Pan, L. Gao, and L. Wang, An effective cooperative co-evolutionary algorithm for distributed flowshop group scheduling problems, IEEE Trans. Cybern., vol. 52, no. 7, pp. 5999–6012, 2022.
K. Gao, F. Yang, M. Zhou, Q. Pan, and P. N. Suganthan, Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm, IEEE Trans. Cybern., vol. 49, no. 5, pp. 1944–1955, 2019.
Z. J. Wang, J. R. Jian, Z. H. Zhan, Y. Li, S. Kwong, and J. Zhang, Gene targeting differential evolution: A simple and efficient method for large-scale optimization, IEEE Trans. Evol. Comput., vol. 27, no. 4, pp. 964–979, 2023.
M. R. Capecchi, Gene targeting in mice: Functional analysis of the mammalian genome for the twenty-first century, Nat. Rev. Genet., vol. 6, no. 6, pp. 507–512, 2005.
G. Zhang, B. Liu, L. Wang, D. Yu, and K. Xing, Distributed co-evolutionary memetic algorithm for distributed hybrid differentiation flowshop scheduling problem, IEEE Trans. Evol. Comput., vol. 26, no. 5, pp. 1043–1057, 2022.
S. García, D. Molina, M. Lozano, and F. Herrera, A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: A case study on the CEC’ 2005 Special Session on Real Parameter Optimization, J. Heuristics, vol. 15, no. 6, pp. 617–644, 2009.
Z. Zhang, Y. Fu, K. Gao, Q. Pan, and M. Huang, A learning-driven multi-objective cooperative artificial bee colony algorithm for distributed flexible job shop scheduling problems with preventive maintenance and transportation operations, Comput. Ind. Eng., vol. 196, p. 110484, 2024.
Y. Fu, K. Gao, L. Wang, M. Huang, Y. C. Liang, and H. Dong, Scheduling stochastic distributed flexible job shops using an multi-objective evolutionary algorithm with simulation evaluation, Int. J. Prod. Res., vol. 63, no. 1, pp. 86–103, 2025.
X. Ma, Y. Fu, K. Gao, L. Zhu, and A. Sadollah, A multi-objective scheduling and routing problem for home health care services via brain storm optimization, Complex Systems Modelling and Simulation, vol. 3, no. 1, pp. 32–46, 2023.
京公网安备11010802044758号