Negotiation Scheduling Algorithm for Multi-agent Job Shop with Private Information

doi:10.3901/JME.2022.09.210

Abstract

Abstract: This research focuses on the multi-agent job shop scheduling problem with private information, where the users are competitors and unwilling to share their objectives, and the users and the job shop make up a decision group. Firstly, a multi-agent job shop scheduling model intending to maximize social welfare is set up. Then, a two-stage negotiation scheduling algorithm is proposed which is composed of genetic evolution and scoring decision stages. In order to avoid revealing private information, a ranking vote-based Pareto sorting algorithm is proposed for the genetic evolution stage, and a score algorithm with linear conversion based on utility is used in the decision stage. Finally, a large number of multi-agent job shop scheduling instances are constructed based on the job shop scheduling benchmark problems to analyze the performance of the proposed algorithm. The simulation results have shown that the overall performance of the proposed two-stage negotiation scheduling algorithm is better than the existing scheduling algorithms, and can get a schedule with higher social welfare.

Key words: multi-agent scheduling, job shop, negotiation mechanism, Pareto optimization, genetic algorithm

CLC Number:

TP278

SUN Shudong, ZHOU Xinmin, CHANG Shengbo. Negotiation Scheduling Algorithm for Multi-agent Job Shop with Private Information[J]. Journal of Mechanical Engineering, 2022, 58(9): 210-217.

References

[1] LANG F, FINK A, BRANDT T. Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling[J]. European Journal of Operational Research, 2016, 248(1): 192-203.
[2] HOMBERGER J, FINK A. Generic negotiation mechanisms with side payments – design, analysis and application for decentralized resource-constrained multi-project scheduling problems[J]. European Journal of Operational Research, 2017, 261(3): 1001-1012.
[3] HOMBERGER J. A (μ, λ)-coordination mechanism for agent-based multi-project scheduling[J]. OR Spectrum, 2012, 34(1): 107-132.
[4] FINK A, HOMBERGER J. An ant-based coordination mechanism for resource-constrained project scheduling with multiple agents and cash flow objectives[J]. Flexible Services and Manufacturing Journal, 2013, 25(1-2): 94-121.
[5] LANG F, FINK A. Learning from the metaheuristics: Protocols for automated negotiations[J]. Group Decision and Negotiation, 2015, 24(2): 299-332.
[6] ZHANG Jie, SHENG Xia, ZHANG Peng, et al. Two-stage unsupervised feature selection method oriented to manufacturing procedural data[J]. Journal of Mechanical Engineering, 2019, 55(17): 133-144. 张洁, 盛夏, 张朋, 等. 面向制造过程数据的两阶段无监督特征选择方法[J]. 机械工程学报, 2019, 55(17): 133-144.
[7] EBRAHIMI A, JEON H W, LEE S, et al. Minimizing total energy cost and tardiness penalty for a scheduling-layout problem in a flexible job shop system: A comparison of four metaheuristic algorithms[J]. Computers & Industrial Engineering, 2020, 141: 106295.
[8] LIU Qiong, MEI Zhen. Integrated optimization of process planning and shop scheduling for reducing manufacturing carbon emissions[J]. Journal of Mechanical Engineering, 2017, 53(11): 164-174. 刘琼, 梅侦. 面向低碳的工艺规划与车间调度集成优化[J]. 机械工程学报, 2017, 53(11): 164-174.
[9] LI Congbo, SHEN Huan, LI Lingling, et al. A batch splitting flexible job shop scheduling model for energy savingunder alternative process plans[J]. Journal of Mechanical Engineering, 2017, 53(5): 12-23. 李聪波, 沈欢, 李玲玲, 等. 面向能耗的多工艺路线柔性作业车间分批优化调度模型[J]. 机械工程学报, 2017, 53(5): 12-23
[10] WU Xiuli, SUN Yangjun. Flexible job shop green scheduling problem with multi-speed machine[J]. Computer Integrated Manufacturing Systems, 2018, 24(4): 862-875. 吴秀丽, 孙阳君. 机器多转速的柔性作业车间绿色调度问题[J]. 计算机集成制造系统, 2018, 24(4): 862-875
[11] WU Xiaoqiang, TIAN Songling, ZHENG Shuxian, et al. Real-time scheduling method of intelligent manufacturing shop floor based on multi-agent[J]. Computer Integrated Manufacturing Systems, 2020, 26(10): 2703-2713. 吴晓强, 田松龄, 郑淑贤, 等. 面向开放式结构产品的智能制造车间实时调度方法[J]. 计算机集成制造系统, 2020, 26(10): 2703-2713
[12] LEI Deming, SU Bin. Multi-class teaching-learning-based optimization for multi-objective distributed hybrid flow shop scheduling[J]. Control and Decision, 2021, 36(2): 303-313. 雷德明, 苏斌. 基于多班教学优化的多目标分布式混合流水车间调度[J]. 控制与决策, 2021, 36(2): 303-313
[13] WU Zigao, SUN Shudong. Risk cost estimation of job shop scheduling with random machine breakdowns[C]// 11th CIRP Conference on Industrial Product-Service Systems, Zhuhai, 29-31 May 2019, Procedia CIRP 2019, 83: 404-409.
[14] LI Xinyu, GAO Liang. An effective hybrid genetic algorithm and tabu search for flexible jobshop scheduling problem[J]. International Journal of Production Economics, 2016, 174: 93-110.
[15] ZHOU Min, SUN Shudong. Genetic algorithm: Theory and applications[M]. Beijing: National Defense Industry Press, 1999. 周明, 孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版社, 1999.
[16] PIVATO M. Formal utilitarianism and range voting[J]. Mathematical Social Sciences, 2014, 67: 50-56.
[17] WIBOWO Y, MAHARDIKA N S, AFRIZAL R, et al. Design of the expert system for Edamamegrading using forward chaining method[J]. Sustainable Environment Agricultural Science, 2020, 4(1): 26-37.
[18] GONCALVES J F, DE MAGALHAES MENDES J J, RESENDE M G C. A hybrid genetic algorithm for the job shop scheduling problem[J]. European Journal of Operational Research, 2005, 167(1): 77-95.
[19] TANG D, DAI M. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2015, 28: 1048-1055.
[20] HILLINGER C. The case for utilitarian voting[J]. Discussion Papers in Economics, 2005, 23(3): 295-321.
[21] SEN A. Majority decision and Condorcet winners[J]. Social Choice and Welfare, 2020, 54(1): 1-7.
[22] NITISIRI K, GEN M, OHWADA H. A parallel multi-objective genetic algorithm with learning-based mutation for railway scheduling[J]. Computers & Industrial Engineering, 2019, 130: 381-394.
[23] WANG J Q, FAN G Q, ZHANG Y Q, et al. Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes[J]. European Journal of Operational Research, 2017, 258(2): 478-490.
[24] ZHANG Y F, ZHANG G, WANG J Q, et al. Real-time information capturing and integration framework of the internet of manufacturing things[J]. International Journal of Computer Integrated Manufacturing, 2015, 28(8): 811-822.
[25] NIU G G, SUN S D, LAFON P, et al. A decomposition approach to job-shop scheduling problem with discretely controllable processing times[J]. Science China: Technological Sciences, 2011, 54(5): 1240-1248.