• CN:11-2187/TH
  • ISSN:0577-6686

机械工程学报 ›› 2022, Vol. 58 ›› Issue (9): 210-217.doi: 10.3901/JME.2022.09.210

• 数字化设计与制造 • 上一篇    下一篇

扫码分享

含私有信息的多代理作业车间协商调度算法

孙树栋1,2, 周新民1,2, 常昇博1,2   

  1. 1. 西北工业大学机电学院 西安 710072;
    2. 西北工业大学工业工程与智能制造工业和信息化部重点实验室 西安 710072
  • 收稿日期:2021-05-24 修回日期:2021-09-05 出版日期:2022-05-05 发布日期:2022-06-23
  • 通讯作者: 孙树栋(通信作者),男,1963年出生,教授,博士研究生导师。主要研究方向为数字化制造技术。E-mail:sdsun@nwpu.edu.cn E-mail:sdsun@nwpu.edu.cn
  • 作者简介:周新民,男,1969年生,博士研究生。主要研究方向为制造业信息化技术。E-mail:siem@nwpu.edu.cn;常昇博,男,1998年生,硕士研究生。主要研究方向为制造系统建模与优化技术。E-mail:shenbo1998@qq.com
  • 基金资助:
    国家自然科学基金资助项目(51975482)

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

SUN Shudong1,2, ZHOU Xinmin1,2, CHANG Shengbo1,2   

  1. 1. School of Mechanical Engineering, Northwestern Polytechnical University, Xi'an 710072;
    2. Key Lab of Industrial Engineering and Intelligent Manufacturing, Northwestern Polytechnical University, Xi'an 710072
  • Received:2021-05-24 Revised:2021-09-05 Online:2022-05-05 Published:2022-06-23

摘要: 在考虑用户互为竞争对手、不愿共享其目标的情况下,用户与车间共同组成调度决策群体,形成代理目标为私有信息的多代理作业车间调度问题。以最大化群体社会福利为优化目标,构建了多代理作业车间调度问题的数学模型。设计了遗传进化-评分决策两阶段协商调度机制,并提出了相应的两阶段协商调度算法。在不披露代理目标的前提下,遗传进化阶段采用帕累托优化排序算法,生成非支配调度方案集;评分决策阶段采用基于效用的线性转换评分算法,实现从非支配方案集中选出社会福利较优的调度方案。大量仿真研究表明,所提遗传进化-评分决策两阶段协商调度算法,其整体性能优于现有协商调度算法,能够产生社会福利更高的调度方案。

关键词: 多代理调度, 作业车间, 协商机制, 帕累托优化, 遗传算法

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

中图分类号: