Fruit Fly Optimization Algorithm for Solving Hybrid Flow-shop Scheduling Problems

Abstract

Abstract: To deal with hybrid flow-shop scheduling problems with unrelated parallel machines, weighted encoding was used for coding operations, according to the characteristics of population update method of fruit fly optimization algorithm. Weighting coefficients were added to improve random search ability of the algorithm. The algorithm parameters were analyzed, and the optimal parameter combination was obtained. Benchmarking examples were used for simulation verification, and the effectiveness of the fruit fly optimization algorithm was verified by comparison with classical algorithms.

Key words: uncorrelated parallel machine, hybrid flow-shop scheduling problem, fruit fly optimization algorithm, weight coefficient

摘要： 针对不相关并行机混合流水车间调度问题，根据果蝇优化算法种群更新方式的特点，采用基于权重的编码方式进行编码操作，通过增加权重系数来提高算法的随机搜索能力。对算法参数的设置进行了分析，得到了最优参数组合。采用标杆实例进行仿真验证并与经典算法进行对比，验证了果蝇优化算法的有效性。

关键词: 不相关并行机, 混合流水车间调度, 果蝇优化算法, 权重系数

CLC Number:

DU Lizhen1;WANG Zhen1;KE Shanfu1;XIONG Zixue1;LI Xinyu2. Fruit Fly Optimization Algorithm for Solving Hybrid Flow-shop Scheduling Problems[J]. China Mechanical Engineering.

杜利珍1;王震1;柯善富1;熊子雪1;李新宇2 . 混合流水车间调度问题的果蝇优化算法求解[J]. 中国机械工程.

References

[1]CASTRO P M, MOSTAFAEI H. Product-centric Continuous-time Formulation for Pipeline Scheduling[J]. Computers & Chemical Engineering, 2017, 104(2): 283-295.
[2]何倩男. 面向离散生产线的相同并行机混合流水车间调度问题研究[D]. 天津：天津理工大学, 2017.
HE Qiannan. Research on the Same Parallel Machine Hybrid Flow Shop Scheduling Problem for Discrete Production Lines[D]. Tianjin: Tianjin University of Technology, 2017.
[3]韩忠华, 董晓婷, 史海波,等. 改进DE算法求解混合流水车间负荷平衡问题[J].计算机集成制造系统, 2016, 22(2): 547-557.
HAN Zhonghua, DONG Xiaoting, SHI Haibo, et al. Improved DE Algorithm for Load Balancing in Hybrid Flow Shops[J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 547-557.
[4]明廷堂.二叉树的遍历算法[J]. 电脑编程技巧与维护，2014(5):16-22.
MING Tingtang. Binary Tree Traversal Algorithm[J]. Computer Programming Techniques and Maintenance, 2014(5):16-22.
[5]姚丽丽, 史海波, 刘昶,等. 基于遗传算法的混合流水线车间调度多目标求解[J]. 计算机应用研究, 2011, 28(9): 3265-3266.
YAO Lili, SHI Haibo, LIU Chang, et al. Multi-objective Solution of Hybrid Assembly Shop Scheduling Based on Genetic Algorithm[J]. Journal of Computer Applications, 2011, 28(9): 3265-3266.
[6]黄华, 肖菁, 张军. 改进并行蚁群算法求解置换流水线调度问题[J]. 计算机工程与设计, 2010, 31(3): 583-585.
HUANG Hua, XIAO Jing, ZHANG Jun. Improved Parallel Ant Colony Algorithm for Permutation Pipeline Scheduling Problem[J]. Computer Engineering and Design, 2010, 31(3): 583-585.
[7]赵敏, 殷欢, 孙棣华,等. 基于改进人工鱼群算法的柔性作业车间调度[J]. 中国机械工程, 2016, 27(8): 1059-1065.
ZHAO Min, YIN Huan, SUN Dihua, et al. Flexible Job Shop Scheduling Based on Improved Artificial Fish Swarm Algorithm[J]. China Mechanical Engineering, 2016, 27(8): 1059-1065.
[8]桑红燕,高亮,李新宇.求解批量流水线调度问题的离散蜂群算法[J].中国机械工程, 2011, 22(18): 2195-2202.
SANG Hongyan, GAO Liang, LI Xinyu. A Discrete Bee Colony Algorithm for Solving Batch Pipeline Scheduling Problem[J]. China Mechanical Engineering, 2011, 22(18): 2195-2202.
[9]裴小兵, 赵衡. 基于二元分布估计算法的置换流水车间调度方法[J]. 中国机械工程, 2017, 28(22): 2752-2755.
PEI Xiaobing, ZHAO Heng. Displacement Flow Shop Scheduling Method Based on Binary Distribution Estimation Algorithm[J]. China Mechanical Engineering, 2017, 28(22): 2752-2755.
[10]PAN Q K, TASGETIREN M F, SUGANTHAN P N, et al. A Discrete Artificial Bee Colony Algorithm for the Lotstreaming Flow Shop Scheduling Problem[J]. Information Sciences, 2011,181(12): 2455-2468.
[11]王凌, 周刚, 许烨,等. 求解不相关并行机混合流水线调度问题的人工蜂群算法[J].控制理论与应用, 2012, 29(12): 1551-1557.
WANG Ling, ZHOU Gang, XU Ye, et al. Artificial Bee Colony Algorithm for Solving Hybrid Pipeline Scheduling Problem of Uncorrelated Parallel Machines[J]. Control Theory & Applications, 2012, 29(12): 1551-1557 .
[12]王凌, 郑晓龙. 果蝇优化算法研究进展[J].控制理论与应用, 2017, 34(5):557-563.
WANG Ling, ZHENG Xiaolong. Research Progress of Fruit Fly Optimization Algorithm[J]. Control Theory & Applications, 2017, 34(5): 557-563.
[13]胡能发. 演化式果蝇优化算法及其应用研究[J].计算机技术与发展, 2013,23(7):131-133.
HU Nengfa. Evolutionary Fruit Algorithm and Its Application[J]. Computer Technology and Development, 2013, 23(7):131-133.
[14]吴楚格, 王凌, 郑晓龙. 求解不相关并行机调度的一种自适应分布估计算法[J]. 控制与决策, 2016, 31(12): 2177-2182.
WU Chuge, WANG Ling, ZHENG Xiaolong. An Adaptive Estimation Algorithm for Solving Uncorrelated Parallel Machine Scheduling[J]. Control and Decision, 2016, 31(12): 2177-2182.
[15]WANG Ling. Differential Evolution Algorithm for Hybrid Flow-shop Scheduling Problems[J].System Engineering and Electronics, 2011, 22(5):794-798.
[16]周辉仁, 唐万生, 魏颖辉. 柔性Flow-shop调度的遗传算法优化[J]. 计算机工程与应用, 2009, 45(30):224-226.
ZHOU Huiren, TANG Wansheng, WEI Yinghui. Genetic Algorithm Optimization for Flexible Flow-shop Scheduling[J]. Computer Engineering and Applications,2009, 45(30): 224-226.
[17]张凤超. 改进的分布估计算法求解混合流水车间调度问题研究[J]. 软件导刊, 2014(8):23-26.
ZHANG Fengchao. Improved Distribution Estimation Algorithm for Solving Mixed-flow Shop Scheduling Problem[J]. Software Guide, 2014(8):23-26.
[18]崔建双, 李铁克, 张文新. 混合流水车间调度模型及其遗传算法[J]. 工程科学学报, 2005, 27(5): 623-626.
CUI Jianshuang, LI Tieke, ZHANG Wenxin. Mixed Flow Shop Scheduling Model and Its Genetic Algorithm[J]. Journal of Engineering Science, 2005, 27(5): 623-626.
[19]XU Y, WANG L. Differential Evolution Algorithm for Hybrid Flow-shop Scheduling Problems[J]. Journal of Systems Engineering and Electronics, 2011, 22(5): 794-798.