A Game-theory Based Optimization Approach for Job Scheduling in Virtual Manufacturing Networks

Abstract

Abstract: A non-cooperative game model was put forward herein for job scheduling problems in virtual manufacturing networks, which transferred the problems into a game. The concept of D-minimum Nash equilibrium was proposed based on the analysis of the existence of ideal Nash equilibrium in game scheduling model. A Nash equilibrium solving method was proposed based on genetic algorithm in order to search the D-minimum Nash equilibrium of the game. In the genetic algorithm, a chromosome coding and decoding scheme and fitness function were designed according to the characteristics of job scheduling problems in virtual manufacturing networks. Efficiency of the proposed approach was validated on several benchmark instances.

Key words: network cooperative strategy, job scheduling, game-theory, Nash equilibrium, genetic algorithm

摘要： 针对虚拟制造网络中的车间调度问题，提出了一个非合作博弈调度优化模型，将车间调度问题转化为一场博弈。在分析该博弈调度模型的理想纳什均衡存在性的基础上，提出了D最小纳什均衡的概念。结合虚拟制造网络中车间调度问题的特点，设计了染色体编码与解码方案以及适应度函数，提出了一种基于遗传算法的博弈调度求解算法来求得该博弈调度模型的D最小纳什均衡。在若干基准实例上验证了该方法的有效性。

关键词: 网络联盟, 作业调度, 博弈论, 纳什均衡, 遗传算法

CLC Number:

TP181

NIE Li1;ZHANG Guohui2;WANG Xiaogang1;BAI Yuewei1. A Game-theory Based Optimization Approach for Job Scheduling in Virtual Manufacturing Networks[J]. China Mechanical Engineering.

聂黎1;张国辉2;王小刚1;白跃伟1. 基于博弈论的虚拟制造网络车间调度优化方法[J]. 中国机械工程.

References

[1]白俊杰. 虚拟单元制造车间的规划与调度关键技术研究[D]. 南京：南京航空航天大学, 2010.
BAI Junjie. Research on the Key Technologies of Workshop Planning and Scheduling in Virtual Cellular Shop-floor [D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2010.
[2]TAYEB F B, BENATCHBA K, MESSIAID A. Game Theory-based Integration of Scheduling with Flexible and Periodic Maintenance Planning in the Permutation Flowshop Sequencing Problem[J]. Operational Research, 2018, 18(1): 221-255.
[3]LI Xinyu, GAO Liang, LI Weidong. Application of Game Theory Based Hybrid Algorithm for Multi-objective Integrated Process Planning and Scheduling [J]. Expert Systems with Applications, 2012, 39(1): 288-297.
[4]ZHOU G H, JIANG P Y, HUANG G Q. A Game-theory Approach for Job Scheduling in Networked Manufacturing [J]. International Journal of Advanced Manufacturing Technology, 2009, 41(9/10): 972-985.
[5]周光辉, 程元森, 肖忠东, 等. 服务型制造车间关键任务调度的Stackelberg博弈研究[J]. 中国机械工程, 2014, 25(3)： 341-345.
ZHOU Guanghui, CHENG Yuansen, XIAO Zhongdong, et al. Stackelberg Game for Critical Job Scheduling in Service-oriented Manufacturing Plants [J]. China Mechanical Engineering, 2014, 25(3)：341-345.
[6]周光辉, 程元森, 朱家凯. 面向 SOMS 外包任务分配决策的一对一Stackelberg 博弈模型研究[J]. 应用科技, 2015, 42(2): 53-57.
ZHOU Guanghui, CHENG Yuansen, ZHU Jiakai. Research on the One-to-one Stackelberg Game Model Facing the Allocation Decision of SOMS Outsourcing Tasks[J]. Applied Science and Technology, 2015, 42(2): 53-57.
[7]SUN Dihua, HE Wei, ZHENG Linjiang, et al. Scheduling Flexible Job Shop Problem Subject to Machine Breakdown with Game Theory [J]. International Journal of Production Research, 2013, 52(13): 3858-3876.
[8]ZHANG Yingfeng, WANG Jin, LIU Sichao , et al. Game Theory Based Real-time Shop Floor Scheduling Strategy and Method for Cloud Manufacturing[J]. International Journal of Intelligent Systems, 2017, 32(4): 437-463.
[9]FATTAHI P, MEHRABAD M S, JOLAI F. Mathematical Modeling and Heuristic Approaches to Flexible Job Shop Scheduling Problems [J]. Journal of Intelligent Manufacturing, 2007, 18(3): 331-342.

[1]	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.
[2]	ZHAO Lijuan, WANG Yadong , WANG Bin. Analysis and Prediction of Working Performance of Shearer Spiral Drums under Coal Seam with Gangue#br# [J]. China Mechanical Engineering, 2021, 32(08): 976-986.
[3]	LIU Xuemei；LIU Tao；GUO Huan. Optimization of Buffer Allocations in Hybrid Production Lines Based on Availability Evaluation [J]. China Mechanical Engineering, 2020, 31(18): 2220-2230.
[4]	YUE Caixu;LIU Xin;LIU Zhibo;XIE Na;WANG Yanwu. Tool Optimization for Splicing Die Milling Processes Based on Finite Element Simulation [J]. China Mechanical Engineering, 2020, 31(17): 2085-2094.
[5]	LIU Xuemei1;WANG Xiao1;LIU Yuelei2. Optimization of Assembly Line Material Distribution Planning under Fuzzy Time Window Constraints [J]. China Mechanical Engineering, 2020, 31(17): 2095-2103.
[6]	LYU Youlong;XU Hongwei;ZHENG Cheng;ZHANG Jie;ZHENG Peng. #br# Wafer Acceptance Test Key Parameter Identification Based on Hybrid Feature Selection Method [J]. China Mechanical Engineering, 2020, 31(16): 1978-1984,1997.
[7]	YANG Jie, HU Qi, XIAO Ting, ZHANG Wenying, ZHANG Chaoyong. Energy Efficiency Modeling, Process Parameter Optimization and Sequencing Modeling Optimization of Cold Rolling Continuous Annealing Units Based on Energy Consumptions [J]. China Mechanical Engineering, 2020, 31(14): 1724-1732.
[8]	LIU Jiansheng;LEI Zhaofa;NIE Weihao;TU Haining. An Optimization Method of Picking Routes for Warehouses with Fishbone Layout [J]. China Mechanical Engineering, 2020, 31(10): 1225-1232.
[9]	LYU Fengpeng;LI Chaoyang;HUANG Jian;CHEN Bingkui . Optimization Design of RV Reducer Turning Arm Bearings [J]. China Mechanical Engineering, 2020, 31(09): 1043-1048.
[10]	GUO Xiangyu;WANG Lin;ZHANG Yongjian. Machining Process Planning Based on Immune Genetic Algorithm under Rule Constraints [J]. China Mechanical Engineering, 2020, 31(04): 482-488.
[11]	ZHANG Heng;LI Aiping;FU Xiang;SHAO Huan;LIU Xuemei. An Integrated Optimization Method for Setups Planning and Line Balancing of Mixed Model Transfer Lines [J]. China Mechanical Engineering, 2019, 30(20): 2497-2504.
[12]	SHENG Jixin1;ZHANG Bangji1;ZHU Bo2;WANG Ming1;JIN Qiutan1. Parameter Optimization and Experimental Comparison of Two-speed Pure Electric Vehicle Transmission Systems [J]. China Mechanical Engineering, 2019, 30(07): 763-770,776.
[13]	HE Changzheng1;SONG Yuchuan1;LEI Qi1;LYU Xiangfei1;LIU Ruanxiang1;CHEN Jin2. Integrated Scheduling of Multiple AGVs and Machines in Flexible Job Shops [J]. China Mechanical Engineering, 2019, 30(04): 438-447.
[14]	ZHANG Lei1,2;LENG Jiewu1,2;GONG Yue1,2. Storage Position Intelligent Optimization for Cantilever Rack Stereoscopic Warehouses [J]. China Mechanical Engineering, 2019, 30(04): 467-471,479.
[15]	DU Gang;GUAN Jinliang;XIONG Yixuan;MA Yujie. Leader-follower Joint Optimization of Product Family Architecting Design and Supplier Selection [J]. China Mechanical Engineering, 2019, 30(01): 9-17.