Research on Flexible Job-shop Dynamic Scheduling Based on Game Theory

doi:10.16182/j.issn1004731x.joss.21-FZ0704

Abstract

Abstract: To quickly and effectively respond to the machine fault disturbance events in Flexible Job-shop Scheduling Problem (FJSP), a flexible job-shop dynamic scheduling based on game theory is established. A pre-scheduling scheme is generated under Non-Dominated Sort Genetic Algorithm-Ⅱ (NSGA-Ⅱ) algorithm which introduces self-adapted crossover operators to improve the population diversity. For FJSP dynamic scheduling with machine fault, a multi-stage complete information game model is built to better balance the stability and robustness indicators and respond quickly to the machine fault, in which the stability and robustness indicators are mapped to the game players, and a hybrid Nash Equilibrium which combines Nash Equilibrium and Pareto optimum is presented to get the dynamic scheduling scheme. The simulation experiment proves the effectiveness of the presented strategy in solving flexible job-shop dynamic scheduling problem.

Key words: flexible job-shop, machine fault, Non-Dominated Sort Genetic Algorithm-Ⅱ (NSGA-Ⅱ), robustness, stability, hybrid Nash Equilibrium

CLC Number:

TP278

You Yichen, Wang Yan, Ji Zhicheng. Research on Flexible Job-shop Dynamic Scheduling Based on Game Theory[J]. Journal of System Simulation, 2021, 33(11): 2579-2588.

References

[1] Turkyilmaz A, Senvar O, Unal I, et al.A Research Survey: Heuristic Approaches for Solving Multi Objective Flexible Job Shop Problems[J]. Journal of Intelligent Manufacturing (S0956-5515), 2020, 31(8): 1949-1983.
[2] Ghasemi M, Farzan A.A Pareto-front Generation by Classical and Meta Heuristic Methods in Flexible Job Shop Scheduling with Multiple Objectives[J]. International Journal of Computer Applications (S0975-8887), 2017, 165(1): 15-21.
[3] Yang T Y, Li J Z, Chen H.Multi-objective Flexible Job-shop Scheduling Problems with Limited Resource Constraints Using Nondominated Sorting Genetic Algorithm II[C]// 2018 IEEE International Conference on Information and Automation. China: IEEE, 2018: 1127-1131.
[4] Zhang Y F, Wang J, Liu Y.Game Theory based Real-time Multi-objective Flexible Job Shop Scheduling Considering Environmental Impact[J]. Journal of Cleaner Production (S0959-6526), 2017, 167(20): 665-679.
[5] Ahmadia E, Zandieh M, Farrokhbs M, et al.A Multi Objective Optimization Approach for Flexible Job Shop Scheduling Problem Under Random Machine Breakdown by Evolutionary Algorithms[J]. Computers & Operations Research (S0305-0548), 2016, 73: 56-66.
[6] Sun D H, He W, Zheng L J, et al.Scheduling Flexible Job Shop Problem Subject to Machine Breakdown with Game Theory[J]. International Journal of Production Research (S0020-7543), 2013, 52(13): 3858-3876.
[7] 陈保安. 离散型制造车间生产调度优化研究[D]. 成都: 电子科技大学, 2020.
Chen Baoan.Research on Production Scheduling Optimization of Discrete Manufacturing Workshop [D]. Chengdu: University of Electronic Science and Technology of China, 2020.
[8] Zadeh M S, Katebi Y, Doniavi A.A Heuristic Model for Dynamic Flexible Job Shop Scheduling Problem Considering Variable Processing Times[J]. International Journal of Production Research (S0020-7543), 2019, 57(10): 3020-3025.
[9] Deb K, Pratap A, Agarwal S, et al.A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2002, 6(2): 182-197.
[10] 曹海涛. 基于改进NSGA-Ⅱ的多目标柔性作业车间调度问题研究[D]. 杭州: 浙江工业大学, 2019.
Cao Haitao.Research on Multi-objective Flexible Job Shop Scheduling Problem Based on Improved NSGA-II [D]. Hangzhou: Zhejiang University of Technology, 2019.
[11] Wang J, Zhang Y F.Multiagent and Bargaining-Game- Based Real-Time Scheduling for Internet of Things-Enabled Flexible Job Shop[J]. IEEE Internet of Things Journal (S2327-4662), 2019, 6(2): 2518-2531.

[1]	Zhiwei Wang, Jizong Hu, Fengjie Wang, Jie Huang. Simulation of Navigation Process Based on Nonlinear Observer [J]. Journal of System Simulation, 2022, 34(5): 1127-1139.
[2]	Lu Hongguang, Zhao Shuen. Research on Intelligent Vehicle Trajectory Tracking Control Based on Robust Model Prediction [J]. Journal of System Simulation, 2022, 34(1): 153-162.
[3]	Yan Yong, Zeng Jing, Xu Kun, Zhao Feiyan. Relationship between Suspension Damping and Stability of Vehicle Hunting Motion [J]. Journal of System Simulation, 2021, 33(8): 1784-1790.
[4]	Luo Guilan, Hao Hongjun, Wang Xiao, Zhang Mei. Study on Universal Characteristics of Insect Population Ecological Network [J]. Journal of System Simulation, 2021, 33(7): 1542-1553.
[5]	Liu Xiazhen, Yuan Wu, Li Qi, Zhao Rui, Zhang Jian, Lu Zhonghua. Simulation and Optimization of Supersonic Drag Characteristics of Blunt Cone Ascender [J]. Journal of System Simulation, 2021, 33(7): 1582-1590.
[6]	Wang Tong, Gao Shan, Dai Tianshu. High Adaptability Vehicle Network Communication Protocol Based on AODV [J]. Journal of System Simulation, 2021, 33(7): 1661-1669.
[7]	Leng Yao, Zhao Shuen. Explicit Model Predictive Control for Intelligent Vehicle Lateral Trajectory Tracking [J]. Journal of System Simulation, 2021, 33(5): 1177-1187.
[8]	Wang Qingyun, Jiao Dezhong, Shi Shuo, Peng Genyan, Sun Junhua, Duan Yuxin. Improved Ant Colony Optimization Algorithm for Jamming Resource Allocation [J]. Journal of System Simulation, 2021, 33(12): 2967-2974.
[9]	Dong Weijie, Huang Min, He Guoqing, Bao Wei, Wang Yilong, Liu Quan. An Electromechanical-electromagnetic Transient Stability Simulation System for AC/DC Hybrid Power System [J]. Journal of System Simulation, 2021, 33(11): 2711-2719.
[10]	Xiong Yong, Liang Xuanzhuo, Zhang Jia. Multi-tank Adaptive Scheduling Algorithm and Simulation for Ship Stability Realization [J]. Journal of System Simulation, 2020, 32(6): 1060-1070.
[11]	Wang Zhe, Li Jianhua, Kang Dong. Research on Recovering of Complex Networks Based on Boundary Nodes of Giant Connected Component [J]. Journal of System Simulation, 2020, 32(12): 2306-2316.
[12]	Fan Dawei, Tong Jiahui. One Turbulent Modeling Method Based on Environmental Forecast Data [J]. Journal of System Simulation, 2020, 32(12): 2409-2414.
[13]	Wu Jingbing, Tang Hanqing, Xu Jun. Analysis and Optimization of Combustion Characteristics of Cement Kiln Cooperatively Disposing Domestic Refuse [J]. Journal of System Simulation, 2020, 32(1): 35-43.
[14]	Zhao Dan, Man Ji, Ni Yunling, Liu Dengxin, Wang Weidong. Research on the Strategy of Adaptive UVLS Based on RTDS Simulation [J]. Journal of System Simulation, 2020, 32(1): 61-68.
[15]	Dong Shuai, Li Shuang, Ye Xuemin. Flow Stability of Hunt Flow under Low-intensity Magnetic Field [J]. Journal of System Simulation, 2019, 31(8): 1605-1616.