Multi-Agent Job Shop Scheduling Strategy Based on Pheromone

Abstract

Abstract: Aiming at the disadvantages of traditional multi-Agent methods based on contractual network protocol,such as single target optimization,large communication volumes,and poor global performance optimization,a multi-Agent dynamic scheduling strategy was proposed based on pheromone.The strategy achieved indirect negotiation between Agents by pheromone, reduced traffic and realied global multi-objective optimization.In addition,the task allocation stages and buffer job selection stages were optimized at the same time.The independent setup time was taken into account,which was more practical and further improved the overall system optimization effectiveness.Finally,an example simulation was used to verifiy the efficiency of the strategy.

Key words: pheromone, multi-Agent system, multi-objective optimization, independent setup time

摘要： 针对基于合同网协议的传统多Agent方法优化目标单一、通信量大、全局性能优化效果差的缺点，提出了基于信息素的多Agent动态调度策略。该策略通过信息素实现了Agent间的间接协商，减少了通信量，实现了全局的多目标优化。此外，采用该策略同时对生产任务分配阶段和缓冲区工件选择阶段的调度进行了优化，并且考虑了独立的调整时间，更加符合实际且进一步提升了系统整体的优化效果。最后，通过实例仿真验证了上述策略的效率。

关键词: 信息素, 多Agent系统, 多目标优化, 独立调整时间

CLC Number:

TP182

CHEN Ming, ZHU Haihua, ZHANG Zequn, JIN Yongqiao, WANG Yingcong, TANG Dunbing. Multi-Agent Job Shop Scheduling Strategy Based on Pheromone[J]. China Mechanical Engineering.

陈鸣, 朱海华, 张泽群, 金永乔, 王盈聪, 唐敦兵. [车间调度]基于信息素的多Agent车间调度策略[J]. 中国机械工程.

References

[1]钱晓龙，唐立新，刘文新.动态调度的研究方法综述[J].控制与决策，2001，16(2)：142-143.
QIAN Xiaolong,TANG Lixin,LIU Wenxin.Dynamic Scheduling: a Survey of Research Methods [J].Control and Decision,2001,16(2): 142-143.
[2]张超勇，邵新宇.作业车间调度理论与算法[M].武汉：华中科技大学出版社，2014：11-12.
ZHANG Chaoyong,SHAO Xinyu.Theory and Algorithm of Job Shop Scheduling[M].Wuhan: Huazhong University of Science & Technology Press，2014:11-12.
[3]朱云飞.基于物联网的车间智能调度技术研究[D].南京：南京航空航天大学，2017.
ZHU Yunfei.Research on Intelligent Shop Scheduling Based on Internet of Things[D].Nanjing: Nanjing University of Aeronautics & Astronautics,2017.
[4]CALLS B,BULKAN S.A Research Survey: Review of AI Solution Strategies of Job Shop Scheduling Problem[J].Journal of Intelligent Manufacturing,2015,26(5): 961-973.
[5]黄腾霄，唐敦兵，张海涛，等.基于Agent的智能制造系统实时动态调度机制研究[J].机械制造与自动化，2017(6): 164-168.
HUANG Tengxiao,TANG Dunbing,ZHANG Haitao,et al.Research on Real-time and Dynamic Scheduling Mechanism of Intelligent Manufacturing System Based on Agent[J].Machine Building and Automation,2017(6): 164-168.
[6]桑泽磊，唐敦兵，郑堃，等.节拍合同网协议及其在作业车间AGV调度的应用[J].南京航空航天大学学报，2016,48(6):896-900.
SANG Zelei,TANG Dunbing,ZHENG Kun,et al.Improved Contract Net Protocol Based on Cycle Period and Its Application in Job Shop AGV Scheduling[J].Journal of Nanjing University of Aeronautics & Astronautics,2016,48(6):896-900.
[7]潘颖，孙伟，马跃，等.基于多Agent的柔性作业车间调度研究[J].大连理工大学学报，2011,51(5):667-674.
PAN Ying,SUN Wei,MA Yue,et al.Research on Flexible Job Shop Scheduling Based on Multi-agent[J].Journal of Dalian University of Technology,2011,51(5):667-674.
[8]赵良辉.无拍卖的动态Agent调度模型[J].计算机集成制造系统，2013,19(11):2893-2899.
ZHAO Lianghui.Dynamic Agent Scheduling Model without Contract Net Protocol [J].Computer Integrated Manufacturing Systems,2013,19(11):2893-2899.
[9]李峥峰.多时间因素作业车间调度问题的研究与工程应用[D].武汉：华中科技大学，2010.
LI Zhengfeng.Research on Job Shop Scheduling Problems with Multi-time and Its Engineering Application[D].Wuhan: Huazhong University of Science and Technology,2010.
[10]ALLAHVERDI A.The Third Comprehensive Survey on Scheduling Problems with Setup Times/Costs[J].European Journal of Operational Research,2015,246(2):345-378.
[11]GUCDEMIR H,SELIM H.Dynamic Dispatching Priority Setting in Customer-oriented Manufacturing Environments[J].International Journal of Advanced Manufacturing Technology,2017,92(5/8): 1861-1874.

[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]	WENG Jian, ZHUANG Kejia, PU Donglin, DING Han, . Plunge Milling of Titanium Alloys Based on Machine Learning and Multi-objective Optimization [J]. China Mechanical Engineering, 2021, 32(07): 771-777.
[3]	NI Hengxin, YAN Chunping, CHEN Jianlin, HOU Yuehui, CHEN Liang. Multi-objective Optimization and Decision-making Method of High Speed Dry Gear Hobbing Processing Parameters [J]. China Mechanical Engineering, 2021, 32(07): 832-838.
[4]	LIU Feng, , LI Jiquan, PENG Xiang, JIANG Shaofei. Optimization of RHCM Mould Electric Heating Systems for Constrainted Heating Pipe Layout [J]. China Mechanical Engineering, 2020, 31(22): 2699-2707.
[5]	JIAO Dongfeng;LIU Zhifeng. Precision Optimization of Driving Axle Parts for Low Cost and Low Noise [J]. China Mechanical Engineering, 2020, 31(20): 2505-2511.
[6]	TONG Zheming1；CHEN Yao1；TONG Shuiguang1；YU Yue1；LI Jinfu2；HAO Guoshuai3. Multi-objective Optimization Design of Low Specific Speed Centrifugal Pumps Based on NSGA-Ⅲ Algorithm [J]. China Mechanical Engineering, 2020, 31(18): 2239-2246.
[7]	LIU Shihao, LIN Mao. Research on Status and Prospects of Optimization Design Method of High-speed CNC Turntables [J]. China Mechanical Engineering, 2020, 31(13): 1629-1637.
[8]	LI Yibing1,2;HUANG Weixing1;WU Rui1. Research on Multi-objective Green Flexible Job-shop Scheduling Based on Improved ABC Algorithm [J]. China Mechanical Engineering, 2020, 31(11): 1344-1350,1385.
[9]	DING Xiaohong;ZHANG Jun;ZHANG Heng. Multi-objective Design Optimization of Pad-iron Positions for Three-point Supporting T-shaped Bed Machine Tools [J]. China Mechanical Engineering, 2019, 30(21): 2615-2621.
[10]	YING Fuqiang;MA Liangliang;WANG Neili. Design and Optimization of Forklift Steering Mechanisms with Horizontal Hydro-cylinder [J]. China Mechanical Engineering, 2019, 30(19): 2329-2334,2341.
[11]	CAI Ning;ZHANG Zeqiang;ZHANG Ying;ZHU Lixia. Modeling and Improved SFLA for Disassembly Line Balancing under Resource Constraints [J]. China Mechanical Engineering, 2019, 30(17): 2091-2099.
[12]	XIE Miao;LI Xiaojing. Multi-objective Optimization Design of Support Cylinders for Excavation and Anchor Combined Units [J]. China Mechanical Engineering, 2019, 30(16): 1976-1981.
[13]	LUO Ju;GUO Fushui. Study on Multi-disciplinary Design Optimization on Civil Turbofan Engines [J]. China Mechanical Engineering, 2019, 30(15): 1813-1820.
[14]	ZHANG Lei;ZHAO Xikun;JIANG Shixin;SONG Haoda. Optimization Method of Process Routes for Housing Parts under Low-carbon and Low-cost Constraints [J]. China Mechanical Engineering, 2018, 29(23): 2836-2844.
[15]	TIAN Qihua, MING Wenhao, WEN Xiaoyong, DU Yixian, ZHOU Xiangman. Multi-objective Optimization Method of Product Development Task Scheduling Based on NSGA-Ⅱ [J]. China Mechanical Engineering, 2018, 29(22): 2758-2766.