Journal Home > Volume 29 , Issue 2
Tsinghua Science and Technology 2024, 29(2): 285-304 https://doi.org/10.26599/TST.2023.9010015
Open Access | Issue | Published: 22 September 2023

Mathematical Modeling and a Multiswarm Collaborative Optimization Algorithm for Fuzzy Integrated Process Planning and Scheduling Problem

Show Author's Information Qihao Liu1,  Cuiyu Wang1,  Xinyu Li1( ),  Liang Gao1
State Key Laboratory of Intelligent Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China
Keywords:
fuzzy processing time, Integrated Process Planning and Scheduling (IPPS), fuzzy completion time, MultiSwarm Collaborative Optimization Algorithm (MSCOA)
Cite this article:
Liu Q, Wang C, Li X, et al. Mathematical Modeling and a Multiswarm Collaborative Optimization Algorithm for Fuzzy Integrated Process Planning and Scheduling Problem. Tsinghua Science and Technology, 2024, 29(2): 285-304. https://doi.org/10.26599/TST.2023.9010015
Download citation
EndNote(RIS)
BibTeX

88

Views

29

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

Considering both process planning and shop scheduling in manufacturing can fully utilize their complementarities, resulting in improved rationality of process routes and high-quality and efficient production. Hence, the study of Integrated Process Planning and Scheduling (IPPS) has become a hot topic in the current production field. However, when performing this integrated optimization, the uncertainty of processing time is a realistic key point that cannot be neglected. Thus, this paper investigates a Fuzzy IPPS (FIPPS) problem to minimize the maximum fuzzy completion time. Compared with the conventional IPPS problem, FIPPS considers the fuzzy process time in the uncertain production environment, which is more practical and realistic. However, it is difficult to solve the FIPPS problem due to the complicated fuzzy calculating rules. To solve this problem, this paper formulates a novel fuzzy mathematical model based on the process network graph and proposes a MultiSwarm Collaborative Optimization Algorithm (MSCOA) with an integrated encoding method to improve the optimization. Different swarms evolve in various directions and collaborate in a certain number of iterations. Moreover, the critical path searching method is introduced according to the triangular fuzzy number, allowing for the calculation of rules to enhance the local searching ability of MSCOA. The numerical experiments extended from the well-known Kim benchmark are conducted to test the performance of the proposed MSCOA. Compared with other competitive algorithms, the results obtained by MSCOA show significant advantages, thus proving its effectiveness in solving the FIPPS problem.


menu
Abstract
Full text
Outline
About this article

Mathematical Modeling and a Multiswarm Collaborative Optimization Algorithm for Fuzzy Integrated Process Planning and Scheduling Problem

Show Author's information Qihao Liu1, Cuiyu Wang1, Xinyu Li1( ), Liang Gao1
State Key Laboratory of Intelligent Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China

Abstract

Considering both process planning and shop scheduling in manufacturing can fully utilize their complementarities, resulting in improved rationality of process routes and high-quality and efficient production. Hence, the study of Integrated Process Planning and Scheduling (IPPS) has become a hot topic in the current production field. However, when performing this integrated optimization, the uncertainty of processing time is a realistic key point that cannot be neglected. Thus, this paper investigates a Fuzzy IPPS (FIPPS) problem to minimize the maximum fuzzy completion time. Compared with the conventional IPPS problem, FIPPS considers the fuzzy process time in the uncertain production environment, which is more practical and realistic. However, it is difficult to solve the FIPPS problem due to the complicated fuzzy calculating rules. To solve this problem, this paper formulates a novel fuzzy mathematical model based on the process network graph and proposes a MultiSwarm Collaborative Optimization Algorithm (MSCOA) with an integrated encoding method to improve the optimization. Different swarms evolve in various directions and collaborate in a certain number of iterations. Moreover, the critical path searching method is introduced according to the triangular fuzzy number, allowing for the calculation of rules to enhance the local searching ability of MSCOA. The numerical experiments extended from the well-known Kim benchmark are conducted to test the performance of the proposed MSCOA. Compared with other competitive algorithms, the results obtained by MSCOA show significant advantages, thus proving its effectiveness in solving the FIPPS problem.

Keywords: fuzzy processing time, Integrated Process Planning and Scheduling (IPPS), fuzzy completion time, MultiSwarm Collaborative Optimization Algorithm (MSCOA)

References(51)

[1]
Y. Fu, Y. Hou, Z. Wang, X. Wu, K. Gao, and L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsinghua Science and Technology, vol. 26, no. 5, pp. 625–645, 2021.
DOI Google Scholar
[2]
L. Wang and D. Z. Zheng, An effective hybrid optimization strategy for job-shop scheduling problems, Comput. Oper. Res., vol. 28, no. 6, pp. 585–596, 2001.
DOI Google Scholar
[3]
X. Wu, Z. Cao, and S. Wu, Real-time hybrid flow shop scheduling approach in smart manufacturing environment, Complex Syst. Model. Simul., vol. 1, no. 4, pp. 335–350, 2021.
DOI Google Scholar
[4]
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.
DOI Google Scholar
[5]
L. Wang, Z. Pan, and J. Wang, A review of reinforcement learning based intelligent optimization for manufacturing scheduling, Complex Syst. Model. Simul., vol. 1, no. 4, pp. 257–270, 2021.
DOI Google Scholar
[6]
B. Khoshnevis and Q. M. Chen, Integration of process planning and scheduling functions, J. Intell. Manuf., vol. 2, no. 3, pp. 165–175, 1991.
DOI Google Scholar
[7]
A. Jain, P. K. Jain, and I. P. Singh, An integrated scheme for process planning and scheduling in FMS, Int. J. Adv. Manuf. Technol., vol. 30, nos. 11&12, pp. 1111–1118, 2006.
DOI Google Scholar
[8]
F. T. S. Chan, S. H. Chung, and L. Y. Chan, An introduction of dominant genes in genetic algorithm for FMS, Int. J. Prod. Res., vol. 46, no. 16, pp. 4369–4389, 2008.
DOI Google Scholar
[9]
X. Li, X. Shao, L. Gao, and W. Qian, An effective hybrid algorithm for integrated process planning and scheduling, Int. J. Prod. Econ., vol. 126, no. 2, pp. 289–298, 2010.
DOI Google Scholar
[10]
S. Zhang and T. N. Wong, Integrated process planning and scheduling: An enhanced ant colony optimization heuristic with parameter tuning, J. Intell. Manuf., vol. 29, no. 3, pp. 585–601, 2018.
DOI Google Scholar
[11]
X. Li, L. Gao, Q. Pan, L. Wan, and K. M. Chao, An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop, IEEE Trans. Syst. Man Cybern.: Syst., vol. 49, no. 10, pp. 1933–1945, 2019.
DOI Google Scholar
[12]
Q. Liu, X. Li, L. Gao, and J. Fan, A multi-MILP model collaborative optimization method for integrated process planning and scheduling problem, IEEE Trans. Eng. Manage., .
DOI Google Scholar
[13]
E. Jiang, L. Wang, and J. Wang, Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Science and Technology, vol. 26, no. 5, pp. 646–663, 2021.
DOI Google Scholar
[14]
L. Wang, Q. K. Pan, P. N. Suganthan, W. H. Wang, and Y. M. Wang, A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems, Comput. Oper. Res., vol. 37, no. 3, pp. 509–520, 2010.
DOI Google Scholar
[15]
L. Wang, S. Wang, Y. Xu, G. Zhou, and M. Liu, A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem, Comput. Ind. Eng., vol. 62, no. 4, pp. 917–926, 2012.
DOI Google Scholar
[16]
H. Li, K. Gao, P. Y. Duan, J. Q. Li, and L. Zhang, An improved artificial bee colony algorithm with Q-learning for solving permutation flow-shop scheduling problems, IEEE Trans. Syst. Man Cybern.: Syst., vol. 53, no. 5, pp. 2684–2693, 2023.
DOI Google Scholar
[17]
X. Han, Y. Han, Q. Chen, J. Li, H. Sang, Y. Liu, Q. Pan, and Y. Nojima, Distributed flow shop scheduling with sequence-dependent setup times using an improved iterated greedy algorithm, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 198–217, 2021.
DOI Google Scholar
[18]
Z. X. Pan, L. Wang, J. F. Chen, and Y. T. Wu, A novel evolutionary algorithm with adaptation mechanism for fuzzy permutation flow-shop scheduling, in Proc. IEEE Congress on Evolutionary Computation, Kraków, Poland, 2021, pp. 367–374.
DOI Google Scholar
[19]
S. Wang, L. Wang, Y. Xu, and M. Liu, An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time, Int. J. Prod. Res., vol. 51, no. 12, pp. 3778–3793, 2013.
DOI Google Scholar
[20]
W. Zhang, W. Hou, C. Li, W. Yang, and M. Gen, Multidirection update-based multiobjective particle swarm optimization for mixed no-idle flow-shop scheduling problem, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 176–197, 2021.
DOI Google Scholar
[21]
K. Z. Gao, P. N. Suganthan, Q. K. Pan, and M. F. Tasgetiren, An effective discrete harmony search algorithm for flexible job shop scheduling problem with fuzzy processing time, Int. J. Prod. Res., vol. 53, no. 19, pp. 5896–5911, 2015.
DOI Google Scholar
[22]
Y. Xu, L. Wang, S. Y. Wang, and M. Liu, An effective teaching-learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time, Neurocomputing, vol. 148, pp. 260–268, 2015.
DOI Google Scholar
[23]
R. Li, W. Gong, L. Wang, C. Lu, and S. Jiang, Two-stage knowledge-driven evolutionary algorithm for distributed green flexible job shop scheduling with type-2 fuzzy processing time, Swarm Evol. Comput., vol. 74, p. 101139, 2022.
DOI Google Scholar
[24]
R. Li and W. Y. Gong, An improved multi-objective evolutionary algorithm based on decomposition for bi-objective fuzzy flexible job-shop scheduling problem, (in Chinese), Control Theory Appl., vol. 39, no. 1, pp. 31–40, 2022.
Google Scholar
[25]
J. Behnamian, Survey on fuzzy shop scheduling, Fuzzy Optim. Decis. Making, vol. 15, no. 3, pp. 331–366, 2016.
DOI Google Scholar
[26]
S. Abdullah and M. Abdolrazzagh-Nezhad, Fuzzy job-shop scheduling problems: A review, Inf. Sci., vol. 278, pp. 380–407, 2014.
DOI Google Scholar
[27]
L. Wang, G. Zhou, Y. Xu, and M. Liu, A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem, Int. J. Prod. Res., vol. 51, no. 12, pp. 3593–3608, 2013.
DOI Google Scholar
[28]
G. G. Wang, D. Gao, and W. Pedrycz, Solving multiobjective fuzzy job-shop scheduling problem by a hybrid adaptive differential evolution algorithm, IEEE Trans. Ind. Inform., vol. 18, no. 12, pp. 8519–8528, 2022.
DOI Google Scholar
[29]
D. Gao, G. G. Wang, and W. Pedrycz, Solving fuzzy job-shop scheduling problem using de algorithm improved by a selection mechanism, IEEE Trans. Fuzzy Syst., vol. 28, no. 12, pp. 3265–3275, 2020.
DOI Google Scholar
[30]
J. Cai and D. Lei, A cooperated shuffled frog-leaping algorithm for distributed energy-efficient hybrid flow shop scheduling with fuzzy processing time, Complex Intell. Syst., vol. 7, no. 5, pp. 2235–2253, 2021.
DOI Google Scholar
[31]
J. Q. Li, Z. M. Liu, C. Li, and Z. X. Zheng, Improved artificial immune system algorithm for type-2 fuzzy flexible job shop scheduling problem, IEEE Trans. Fuzzy Syst., vol. 29, no. 11, pp. 3234–3248, 2021.
DOI Google Scholar
[32]
R. Li, W. Gong, and C. Lu, Self-adaptive multi-objective evolutionary algorithm for flexible job shop scheduling with fuzzy processing time, Comput. Ind. Eng., vol. 168, p. 108099, 2022.
DOI Google Scholar
[33]
W. Gong, Z. Liao, X. Mi, L. Wang, and Y. Guo, Nonlinear equations solving with intelligent optimization algorithms: A survey, Complex System Modeling and Simulation, vol. 1, no. 1, pp. 15–32, 2021.
DOI Google Scholar
[34]
X. Wen, X. Li, L. Gao, L. Wan, and W. Wang, Multi-objective genetic algorithm for integrated process planning and scheduling with fuzzy processing time, in Proc. 6th Int. Conf. Advanced Computational Intelligence, Hangzhou, China, 2013, pp. 293–298.
DOI Google Scholar
[35]
S. Zhang, Z. Yu, W. Zhang, D. Yu, and Y. Xu, An extended genetic algorithm for distributed integration of fuzzy process planning and scheduling, Math. Probl. Eng., vol. 2016, p. 3763512, 2016.
DOI Google Scholar
[36]
X. Wen, X. Lian, K. Wang, H. Li, and G. Luo, Multi-layer collaborative optimization method for solving fuzzy multi-objective integrated process planning and scheduling, Meas. Control, vol. 53, nos. 9&10, pp. 1883–1901, 2020.
DOI Google Scholar
[37]
H. Zhang, J. Xie, J. Ge, J. Shi, and Z. Zhang, Hybrid particle swarm optimization algorithm based on entropy theory for solving DAR scheduling problem, Tsinghua Science and Technology, vol. 24, no. 3, pp. 282–290, 2019.
DOI Google Scholar
[38]
L. Wang, G. Zhou, Y. Xu, S. Wang, and M. Liu, An effective artificial bee colony algorithm for the flexible job-shop scheduling problem, Int. J. Adv. Manuf. Technol., vol. 60, nos. 1–4, pp. 303–315, 2012.
DOI Google Scholar
[39]
R. Wang, W. Ma, M. Tan, G. Wu, L. Wang, D. Gong, and J. Xiong, Preference-inspired coevolutionary algorithm with active diversity strategy for multi-objective multi-modal optimization, Inf. Sci., vol. 546, pp. 1148–1165, 2021.
DOI Google Scholar
[40]
R. Wang, Q. Zhang, and T. Zhang, Decomposition-based algorithms using Pareto adaptive scalarizing methods, IEEE Trans. Evol. Comput., vol. 20, no. 6, pp. 821–837, 2016.
DOI Google Scholar
[41]
F. Zhao, S. Di, J. Cao, J. Tang, and Jonrinaldi, A novel cooperative multi-stage hyper-heuristic for combination optimization problems, Complex Syst. Model. Simul., vol. 1, no. 2, pp. 91–108, 2021.
DOI Google Scholar
[42]
E. D. Jiang, L. Wang, and Z. P. Peng, Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition, Swarm Evol. Comput., vol. 58, p. 100745, 2020.
DOI Google Scholar
[43]
Z. Pan, D. Lei, and L. Wang, A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling, IEEE Trans. Cybern., vol. 52, no. 6, pp. 5051–5063, 2022.
DOI Google Scholar
[44]
Q. Liu, X. Li, and L. Gao, A novel MILP model based on the topology of a network graph for process planning in an intelligent manufacturing system, Engineering, vol. 7, no. 6, pp. 807–817, 2021.
DOI Google Scholar
[45]
Q. Liu, X. Li, and L. Gao, Mathematical modeling and a hybrid evolutionary algorithm for process planning, J. Intell. Manuf., vol. 32, no. 3, pp. 781–797, 2021.
DOI Google Scholar
[46]
J. Xie, X. Li, L. Gao, and L. Gui, A new neighbourhood structure for job shop scheduling problems, Int. J. Prod. Res., vol. 61, no. 7, pp. 2147–2161, 2023.
DOI Google Scholar
[47]
Q. Liu, X. Li, L. Gao, and Y. Li, A modified genetic algorithm with new encoding and decoding methods for integrated process planning and scheduling problem, IEEE Trans. Cybern., vol. 51, no. 9, pp. 4429–4438, 2021.
DOI Google Scholar
[48]
C. Zhang, P. Li, Z. Guan, and Y. Rao, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Comput. Oper. Res., vol. 34, no. 11, pp. 3229–3242, 2007.
DOI Google Scholar
[49]
Y. Li, X. Li, and L. Gao, An effective solution space clipping-based algorithm for large-scale permutation flow shop scheduling problem, IEEE Trans. Syst. Man Cybern.: Syst., vol. 53, no. 1, pp. 635–646, 2023.
DOI Google Scholar
[50]
J. Fan, Y. Li, J. Xie, C. Zhang, W. Shen, and L. Gao, A hybrid evolutionary algorithm using two solution representations for hybrid flow-shop scheduling problem, IEEE Trans. Cybern., vol. 53, no. 3, pp. 1752–1764, 2023.
DOI Google Scholar
[51]
Y. K. Kim, K. Park, and J. Ko, A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Comput. Oper. Res., vol. 30, no. 8, pp. 1151–1171, 2003.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 29 January 2023
Revised: 16 February 2023
Accepted: 07 March 2023
Published: 22 September 2023
Issue date: April 2024

Copyright

© The author(s) 2024.

Acknowledgements

This work was supported by the National Key R&D Program of China (No. 2022YFB3302700), the National Natural Science Foundation of China (Nos. U21B2029 and 52188102), and the Key R&D Program of Hubei Province (No. 2021AAB001).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return