Hybrid Flow Shop Scheduling Problems with Unrelated Parallel Machine Solved by Improved Adaptive Genetic Algorithm(IAGA) with ITPX

doi:10.3969/j.issn.1004-132X.2023.14.002

Abstract

Abstract: Aiming at the hybrid flow-shop scheduling problems, an adaptive genetic algorithm with ITPX was proposed. Firstly, the solution performance of two-points crossover（TPX） was improved by exacting point taking method. Secondly, adaptive selection probability was demonstrated based on hormonal regulation guiding convergence trend of populations. Then, a pool of high-quality chromosomes and a memory factor were established to record the high-quality chromosomes during population evolution, and two different regional crossovers were implemented. Experimentsal results show that ITPX may save optimization time and improve solution performance; the adaptive probability may enhance convergence; ITPX-IAGA may reduce solution time by more than 40% and improve solution performance.

Key words: hybrid flow-shop scheduling problem, unrelated parallel machine, adaptive genetic algorithm(AGA), improved two-points crossover(ITPX), hormone regulation mechanism

摘要： 针对不相关并行机的混合流水车间调度问题，提出了改进两点交叉算子(ITPX)的自适应遗传算法。首先，利用精确取点方式提高两点交叉算子的求解性能；其次，论证了基于激素调节的自适应选择概率引导种群的收敛趋势；然后，建立优质染色体池和记忆因子来记录种群迭代的优质解，并实现两种不同区域的交叉。实验结果表明，ITPX可节省优化时间，提高求解性能；自适应概率可增强收敛性；改进两点交叉算子的改进自适应遗传算法（ITPX-IAGA）可缩短40%以上的求解时间，并提高求解性能。

关键词: 混合流水车间调度问题, 不相关并行机, 自适应遗传算法, 改进两点交叉算子, 激素调节机制

CLC Number:

TH18

ZHENG Kun, LIAN Zhiwei, GU Xinyan, ZHU Changjian, XU Hui, FENG Xueqing. Hybrid Flow Shop Scheduling Problems with Unrelated Parallel Machine Solved by Improved Adaptive Genetic Algorithm(IAGA) with ITPX[J]. China Mechanical Engineering, 2023, 34(14): 1647-1658，1671.

郑堃, 练志伟, 顾新艳, 朱长建, 徐慧, 冯雪晴. 采用改进两点交叉算子的改进自适应遗传算法求解不相关并行机混合流水车间调度问题[J]. 中国机械工程, 2023, 34(14): 1647-1658，1671.

References

［1］SALVADOR M S. A Solution to a Special Class of Flow Shop Scheduling Problems［J］. Lecture Notes in Economics and Mathematical Systems, 1973, 86: 83-91.
［2］李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述［J］. 中国机械工程, 2020, 31(23): 2798-2813.
LI Yingli, LI Xinyu, GAO Liang. Review on Hybrid Flow Shop Scheduling Problems［J］. China Mechanical Engineering, 2020, 31(23): 2798-2813.
［3］黄学文,陈绍芬,周阗玉,等.求解柔性作业车间调度的遗传算法综述［J］.计算机集成制造系统, 2022, 28(2): 536-551.
HUANG Xuewen, CHEN Shaofen, ZHOU Tianyu, et al. A Review of Genetic Algorithms for Solving Flexible Job Shop Scheduling［J］. Computer Integrated Manufacturing Systems, 2022, 28(2): 536-551.
［4］顾文斌, 李育鑫, 钱煜晖, 等. 基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题［J］. 计算机集成制造系统, 2021, 27(10): 2858-2871.
GU Wenbing, LI Yuxin, QIAN Yuhun, et al. The Same Parallel Machine Hybrid Flow Shop Scheduling Problem Based on IPSO Algorithm with Hormone Regulation Mechanism［J］. Computer Integrated Manufacturing Systems, 2021, 27(10): 2858-2871.
［5］周永强, 王翠雨, 李颖俐, 等. 改进果蝇算法求解混合流水车间调度问题［J］. 控制理论与应用, 2023, 40(4): 597-606.
ZHOU Yongqiang, WANG Cuiyu, LI Yinli,et al. Improved Fruit Fly Algorithm for Solving Hybrid Flow Shop Scheduling Problems［J］. Control Theory and Applications, 2023, 40(4): 597-606.
［6］王凌, 周刚, 许烨, 等. 求解不相关并行机混合流水线调度问题的人工蜂群算法［J］. 控制理论与应用, 2012, 29(12): 1551-1557.
WANG Ling, ZHOU Gang, XU Ye,et al. Artificial Bee Colony Algorithm for Uncorrelated Parallel Machine Hybrid Pipeline Scheduling Problem［J］. Control Theory and Applications, 2012, 29(12): 1551-1557.
［7］王圣尧, 王凌, 许烨, 等. 求解混合流水车间调度问题的分布估计算法［J］. 自动化学报, 2012, 38(3): 437-443.
WANG Shengyao, WANG Ling, XU Ye,et al. Distribution Estimation Algorithm for Solving Mixed Flow Shop Scheduling Problem［J］. Acta Automatica Sinica, 2012, 38(3): 437-443.
［8］孙树琪, 陈书宏. 基于蜻蜓算法求解柔性流水车间排产优化问题［J］. 计算机应用, 2020, 40(增刊1): 37-40.
SUN Shuqi, CHEN Shuhong. Solving Optimization Problem of Flexible Flow Shop Scheduling Based on Dragonfly Algorithm［J］. Journal of Computer Applications, 2020, 40(S1): 37-40.
［9］薛玲玲. 作业车间调度的块结构邻域搜索遗传算法［J］. 计算机集成制造系统, 2021, 27(10): 2848-2857.
XUE Lingling. Block-structured Neighborhood Search Genetic Algorithm for Job Shop Scheduling［J］. Computer Integrated Manufacturing Systems, 2021, 27(10): 2848-2857.
［10］吴树景, 游有鹏, 罗福源. 变邻域保优遗传算法求解柔性车间调度问题［J］. 计算机工程与应用, 2020, 56(22): 236-243.
WU Shujing, YOU Youpeng, LUO Fuyuan. Variable-neighborhood Preservation Genetic Algorithm for Solving Flexible Workshop Scheduling Problems［J］. Computer Engineering and Applications, 2020, 56(22): 236-243.
［11］轩华, 孙丙坤, 李冰. 混合遗传算法求解带不相关并行机的HFSSP［J］. 控制工程, 2022, 29(7): 1210-1219.
XUAN Hua, SUN Bingkun, LI Bing.Hybrid Genetic Algorithm for Solving HFSSP with Unrelated Parallel Machine［J］. Control Engineering, 2022, 29(7): 1210-1219.
［12］王鹏,王方.量子视角下的智能优化算法综述［J］.电子科技大学学报,2022,51(1):2-15.
WANG Peng, WANG Fang. A Review of Intelligent Optimization Algorithms in Quantum Perspective［J］. Journal of the University of Electronic Science and Technology, 2022, 51(1): 2-15.
［13］王雷, 唐敦兵, 万敏, 等. 激素调节机制IAGA在作业车间调度中的应用研究［J］. 农业机械学报, 2009, 40(10): 199-202.
WANG Lei, TANG Dunbing, WAN Min, et al. Application of Hormone Regulation Mechanism IAGA in Job Shop Scheduling［J］. Transactions of the Chinese Society of Agricultural Machinery, 2009, 40(10): 199-202.
［14］郑堃, 练志伟, 王玉国, 等. 改进激素算法求解置换流水车间调度问题［J］. 电子科技大学学报, 2022, 51(6): 890-903.
ZHENG Kun, LIAN Zhiwei, WANG Yuguo,et al. Improved Hormone Algorithm for Solving the Permutation Flow Shop Scheduling Problem［J］. Journal of University of Electronic Science and Technology of China, 2022, 51(6): 890-903.
［15］FARHY L S. Modeling of Oscillations in Endocrine with Feedback［J］. Methods in Enzymology, 2004, 384: 54-81.
［16］TIZHOOSH H R. Opposition-based Learning: a New Scheme for Machine Intelligence［C］∥Procee of International Conference on Computational Intelligence for Modelling Control and Automation. Vienna, 2005: 695-701.
［17］GOLDBERG D E, DEB K. A Comparative Analysis of Selection Schemes Used in Genetic Algorithms［J］. Foundations of Genetic Algorithms, 1991, 1: 69-93.
［18］ISHIBUCHI H, MURATA T. A Multi-objective Genetic Local Search Algorithm and Its Application to Flow-shop Scheduling［J］. IEEE Transactions on Systems, Man, and Cybernetics, Part C(Applications and Reviews), 1998, 28(3): 392-403.
［19］高岳林, 杨钦文, 王晓峰, 等. 新型群体智能优化算法综述［J］. 郑州大学学报(工学版), 2022, 43(3): 21-30.
GAO Yuelin, YANG Qinwen, WANG Xiaofeng,et al. A Review of Novel Population Intelligence Optimization Algorithms［J］. Journal of Zhengzhou University(Engineering Edition), 2022, 43(3): 21-30.［20］杜利珍, 王震, 柯善富, 等.混合流水车间调度问题的果蝇优化算法求解［J］. 中国机械工程, 2019, 30(12): 1480-1485.
DU Lizhen, WANG Zheng, KE Shanfu,et al. The Fruit Fly Optimization Algorithm to Solve the Scheduling Problem of Mixed Flow Shop［J］. China Mechanical Engineering, 2019, 30(12): 1480-1485.
［21］周辉仁, 唐万生, 魏颖辉. 柔性Flow-Shop调度的遗传算法优化［J］.计算机工程与应用, 2009, 45(30): 224-226.
ZHOU Huiren, TANG Wangsheng, WEI Yinghui. Genetic Algorithm Optimization for Flexible Flow-shop Scheduling［J］. Computer Engineering and Applications, 2009, 45(30): 224-226.
［22］YE X, LING W. Differential Evolution Algorithm for Hybrid Flow-shop Scheduling Problems［J］. Journal of Systems Engineering and Electronics, 2011, 22(5):794-798.
［23］张源,陶翼飞,王加冕.改进差分进化算法求解混合流水车间调度问题［J］.中国机械工程,2021,32(6):714-720.
ZHANG Yuan, TAO Yifei, WANG Jiamian. Improved Differential Evolution Algorithm to Solve Hybrid Flow Shop Scheduling Problem［J］. China Mechanical Engineering, 2021, 32(6): 714-720.
［24］王芳, 唐秋华, 饶运清, 等.求解柔性流水车间调度问题的高效分布估算算法［J］. 自动化学报, 2017, 43(2): 280-293.
WANG Fang, TANG Qiuhua, RAO Yunqing,et al. Efficient Distribution Estimation Algorithm for Flexible Flow Shop Scheduling Problem［J］. Acta Automatica Sinica, 2017, 43(2): 280-293.