Scheduling of Flexible Job Shop Based on High-dimension and Multi-objective Migrating Bird Optimization Algorithm

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

Abstract

Abstract: Aiming at the problems in flexible job shop scheduling， an improved multi-objective migrating bird optimization（MOMBO）algorithm was proposed to solve the high-dimensional multi-objective scheduling problem with the consideration of maximum completion time， total delay period， total load of machine， and total energy consumption. On the basis of migrating bird optimization algorithm， MOMBO algorithm introduced a selection operator based on Pareto domination and reference point to give bird population selection pressure， and the combined weight method based on attribute hierarchical mode and gray relation analysis was used to select the most suitable solution from the optimal solution sets. The effectiveness and practicability of MOMBO were verified by test instances and case study.

Key words: flexible job shop, migrating bird optimization algorithm, multi-objective optimization, energy conservation

摘要： 针对柔性作业车间调度问题，提出一种改进的多目标候鸟优化算法来求解考虑完工时间、总拖期、机器总负荷以及总能耗的高维多目标问题。多目标候鸟优化算法在候鸟优化算法的基础上引入基于Pareto支配和参考点的选择算子来给予鸟群选择压力，并用基于属性层次模型和灰色关联分析法的组合权重法从最优解集中选择一个最合适的方案。算例和实例验证了算法的有效性和实用性。

关键词: 柔性作业车间, 候鸟优化算法, 多目标优化, 节能

CLC Number:

TH186

WANG Qiulian, DUAN Xinghao. Scheduling of Flexible Job Shop Based on High-dimension and Multi-objective Migrating Bird Optimization Algorithm[J]. China Mechanical Engineering, 2022, 33(21): 2601-2612.

王秋莲, 段星皓. 基于高维多目标候鸟优化算法的柔性作业车间调度[J]. 中国机械工程, 2022, 33(21): 2601-2612.

References

［1］BRUCKER P. Schlie R. Job-shop Scheduling with Multi-purpose Machines［J］. Computing， 1991， 45（4）， 369-375.
［2］孙丽珍，毕利. 多约束条件下的动态柔性作业车间调度研究［J］. 控制工程， 2020， 27（11）：1921-1929.
SUN Lizhen， BI Li. Dynamic Flexible Workshop Scheduling under Multi-constraint Conditions［J］. Control Engineering， 2020， 27（11）：1921-1929.
［3］孟冠军，杨大春，陶细佩. 基于混合人工蜂群算法的多目标柔性作业车间调度问题研究［J］. 计算机应用研究， 2019， 36（4）：972-974.
MENG Guanjun， YANG Dachun， TAO Xipei. A Study on Multi-target Flexible Workshop Scheduling Based on Mixed Artificial Bee Colony Algorithm［J］. Computer Application Research， 2019， 36（4）：972-974.
［4］李进宇，王秋莲，张炎. 基于递归分析的混流生产模式机械加工过程能效分析和状态监测［J］. 计算机集成制造系统， 2021， 27（5）：1341-1350.
LI Jinyu， WANG Qiulian， ZHANG Yan. Energy Efficiency Analysis and Condition Monitoring of Mixed Flow Production Mode Machining Process Based on Recursive Analysis［J］. Computer Integrated Manufacturing System， 2021， 27（5）：1341-1350.
［5］李明，雷德明. 基于新型帝国竞争算法的高维多目标柔性作业车间调度［J］. 控制理论与应用， 2019， 36（6）：893-901.
LI Ming， LEI Deming. High-dimensional multi-target Flexible Workshop Scheduling Based on New Imperial Competition Algorithm［J］. Control Theory and Application， 2019， 36（6）：893-901.
［6］黄夏宝，魏淑玲. 考虑低碳的高维多目标柔性作业车间调度［J］. 武汉理工大学学报（信息与管理工程版）， 2019， 41（6）：592-598.
HUANG Xiabao， WEI Shuling. Consider Low Carbon High-dimensional Multi-target Flexible Work-shop Scheduling［J］. Journal of Wuhan University of Technology（Information and Management Engineering Edition）， 2019， 41（6）：592-598.
［7］王凌，王晶晶，吴楚格. 绿色车间调度优化研究进展［J］. 控制与决策， 2018， 33（3）：385-391.
WANG Ling， WANG Jingjing， WUChuge. Green Workshop Scheduling Optimization Research Progress［J］. Control and Decision-making， 2018， 33（3）：385-391.
［8］DUMAN E， UYSAL M， ALKAYA A F. Migrating Birds Optimization：a New Metaheuristic Approach and Its Performance on Quadratic Assignment Problem［J］. Information Sciences， 2012， 217：65-77.
［9］QUAN K P， YAN D. An Improved Migrating Birds Optimization for a Hybrid Flowshop Scheduling with Total Flowtime Minimisation［J］. Information Sciences， 2014， 277：643-655.
［10］任彩乐，张超勇，孟磊磊，等. 基于改进候鸟优化算法的混合流水车间调度问题［J］. 计算机集成制造系统， 2019， 25（3）：643-653.
REN Caile， ZHANGChaoyong， MENG Leilei， et al. The Scheduling Problem of Mixed Flow Workshop Based on Improving Migratory Bird Optimization Algorithm［J］. Computer Integrated Manufacturing System， 2019， 25（3）：643-653.
［11］姚妮. 混合候鸟迁徙优化算法求解柔性作业车间调度问题［J］. 华中师范大学学报（自然科学版）， 2016， 50（1）：38-42.
YAO Ni. The Hybrid Migratory Bird Migration Optimization Algorithm Solves the Flexible Workshop Scheduling Problem［J］. Journal of Central China Normal University（Natural Science Edition）， 2016， 50（01）：38-42.
［12］刘雪红，段程，王磊. 基于改进候鸟算法的柔性作业车间分批调度问题［J］. 计算机集成制造系统， 2021， 27（11）：3185-3195.
LIU Xuehong， DUAN Cheng， WANG Lei. Based on the Flexible Work Shop Batch Scheduling Problem Based on Improving Migratory Bird Algorithm［J］. Computer Integrated Manufacturing System， 2021， 27（11）：3185-3195.
［13］DAS B I， DENNIS J E. Normal Boundary Intersection：a New Method for Generating Pareto Optimal Points in Multicriteria Optimization Problems［J］. SIAM Journal on Optimization， 1998， 8（3）：631-657.
［14］张国辉，高亮，李培根，等. 改进遗传算法求解柔性作业车间调度问题［J］. 机械工程学报， 2009， 45（7）：145-151.
ZHANG Guohui， GAO Liang， LI Peigen， et al. Improve Genetic Algorithm to Solve Flexible Work Shop Scheduling Problems［J］. Journal of Mechanical Engineering， 2009， 45（7）：145-151.
［15］ZHANG G H， GAO L， SHI Y. An Effective Genetic Algorithm for the Flexible Job-shop Scheduling Problem［J］. Expert Systems with Applications， 2011， 38（4）：3563-3573.
［16］赵诗奎，方水良，顾新建. 基于极限调度完工时间最小化的机器选择及FJSP求解［J］. 计算机集成制造系统， 2014， 20（4）：854-865.
ZHAO Shikui， FANG Shuiliang， GU Xinjian. Machine Selection and FJSP Solution Based on Limit Scheduling Completion Time Minimization［J］. Computer Integrated Manufacturing System， 2014， 20（4）：854-865.
［17］PEZZELLA F， MORGANTI G， CIASCHETTI G. A Genetic Algorithm for the Flexible Job-shop Scheduling Problem［J］. Computers and Operations Research， 2007， 35（10）：3202-3212.
［18］GAO K Z， SUGANTHAN P N， PAN Q K， et al. Pareto-based Grouping Discrete Harmony Search Algorithm for Multi-objective Flexible Job Shop Scheduling［J］. Information Sciences， 2014， 289（1）：76-90.
［19］王春. 多目标柔性作业车间调度模型及其进化算法研究［D］. 无锡：江南大学， 2018.
WANG Chun. Multi-target Flexible Workshop Scheduling Model and Its Evolutionary Algorithm［D］. Wuxi：Jiangnan University， 2018.
［20］BRANDIMARTE P. Routing and Scheduling in a Flexible Job Shop by Tabu Search［J］. Annals of Operations Research， 1993， 41（3）：157-183.
［21］ZITZLER E， THIELE L， LAUMANNS M， et al. Performance Assessment of Multiobjective Optimizers：an Analysis and Review［J］. IEEE Transactions on Evolutionary Computation， 2003， 7（2）：117-132.
［22］ZITZLER E， THIELE L. Multiobjective Evolutionary Algorithms：a Comparative Case Study and the Strength Pareto Approach［J］. IEEE Transactions on Evolutionary Computation， 1999， 3（4）：257-271.
［23］BADER J， ZITZLER E， HYP E. An Algorithm for Fast Hypervolume-based Many-objective Optimization［J］. Evolutionary Computation， 2011， 19（1）：45-76.

[1]	LI Meng-Lei, GU Yo-Qin, ZHANG Hua-Liang, LIU Li-Qin, DU Juan, WEN Chu-Hua, LAN Guo-Sheng. Parallel Mechanism Structure Optimization Design Based on Multi-objective Differential Evolution Algorithm [J]. J4, 201016, 21(16): 1915-1920.
[2]	TIAN Ying, SHAO Wenting, WANG Taiyong. Energy Footprint Modeling and Parameter Optimization in Workshop Manufacturing Processes [J]. China Mechanical Engineering, 2022, 33(21): 2547-2553.
[3]	ZHANG Hongliang, XU Gongjie, BAO Qiang, PAN Ruilin. Distributed Flexible Job Shop Green Scheduling with Transportation Time [J]. China Mechanical Engineering, 2022, 33(21): 2554-2563,2645.
[4]	SUN Aihong, SONG Yuchuan, YANG Yunfan, LEI Qi. Dual Resource-constrained Flexible Job Shop Scheduling Algorithm Considering Machining Quality of Key Jobs [J]. China Mechanical Engineering, 2022, 33(21): 2590-2600.
[5]	BAO Hong, YANG Jing, KE Qingdi, LI Hongzhen, YAO Yongzheng, . An Energy Efficiency Optimization Model of Fused Filament Fabrication 3D Printing Based on Support Vector Regression [J]. China Mechanical Engineering, 2022, 33(18): 2215-2226.
[6]	RONG Yu, DOU Tianci, ZHANG Xingchao, ZHANG LeiZ, HAO Jingyu. A Real-time Control Method for Optimal Overall Performances of Planar Redundant Robots [J]. China Mechanical Engineering, 2022, 33(16): 1928-1939.
[7]	LI Hao, XU Zhiling, XU Yong, ZHAO Youwei. Grouping Selective Assembly Method for Mechanical Products Based on Local Search Strategy for NSGA-Ⅱ [J]. China Mechanical Engineering, 2022, 33(09): 1127-1133.
[8]	SHANG Zuen, ZHAO Lijuan, LIU Xionghao, JIN Xin. Deployable Waterbomb Wheel Structure Analysis and Optimization of Mine Rescue Robots [J]. China Mechanical Engineering, 2021, 32(24): 2924-2933.
[9]	WU Xing, ZHAI Jingjing, LOU Peihuang, HU Ya, XIAO Haining. Deadlock-free Task Scheduling with Task Traveling Time for a Multi-load AGV System [J]. China Mechanical Engineering, 2021, 32(23): 2840-2849.
[10]	DONG Chenglin, LIU Haitao, YANG Junhao. Dimensional Synthesis of a Novel Asymmetric 5-DOF Hybrid Robot [J]. China Mechanical Engineering, 2021, 32(20): 2418-2426.
[11]	WANG Dengfeng, LI Shenhua. Lightweight Optimization Design of Side Collision Safety Parts for BIW Based on Pareto Mining#br# [J]. China Mechanical Engineering, 2021, 32(13): 1584-1590,1637.
[12]	YI Qian, HE Shuang, NING Qing, LI Congbo, YI Shuping. An Multi-objective Optimized Production Scheduling for Automobile Prototype Workshops Considering Employee Work Ability#br# [J]. China Mechanical Engineering, 2021, 32(13): 1617-1629.
[13]	CHEN Haojie, DING Guofu, ZHANG Jian, YAN Kaiyin. Improved Genetic Programming Algorithm for RCMPSP [J]. China Mechanical Engineering, 2021, 32(10): 1213-1221.
[14]	LI Yi, TANG Qian, LIULianchao, PENG Xiaogang, YAN Xianhong. An Improved ACO Algorithm for Automobile Mixed-flow Assembly Scheduling Problems#br# [J]. China Mechanical Engineering, 2021, 32(09): 1126-1133.
[15]	LI Xixing, YANG Daoming, LI Xin, WU Rui, . Flexible Job Shop AGV Fusion Scheduling Method Based on HGWOA [J]. China Mechanical Engineering, 2021, 32(08): 938-950，986.