基于多Agent的敏捷生产调度中的协商策略

• 论文 •

基于多Agent的敏捷生产调度中的协商策略

吕赐兴，朱云龙，尹朝万，于海斌

1.中国科学院沈阳自动化研究所，辽宁沈阳 110016;2.中国科学院研究生院，北京 100039

收稿日期:2005-02-22 修回日期:2005-03-10 出版日期:2006-04-15 发布日期:2006-04-25
基金资助:
国家重点基础研究规划资助项目(2002CB312204-03)；国家自然科学基金资助项目(70431003)。

Negotiation policy for multi-Agent based agile production scheduling

LV Ci-xing,ZHU Yun-long,YIN Chao-wan,YU Hai-bin

1.Shenyang Inst. of Automation, Chinese Academy of Sciences, Shenyang 110016, China;2.Graduate Sch. of the Chinese Academy of Sciences, Beijing 100039, China

Received:2005-02-22 Revised:2005-03-10 Online:2006-04-15 Published:2006-04-25
Supported by:
Project supported by the National Basic Research Program,China(No.112002CB32204-03)and the National Natural Science Foundation,China(No.7043003).

摘要/Abstract

摘要： 为了解决基于多智能体的敏捷生产调度中资源分配的协商策略问题，提出了实现组合拍卖的协商策略的解决方法。在描述资源分配问题的基础上，基于组合拍卖解法，利用对偶理论与组合拍卖设计之间的联系，给出了组合拍卖的设计和拍卖的过程。根据设计结果和拍卖过程，采用分布规则，描述和构建实现组合拍卖的协商策略，并存储在相关智能体的规则库内。运行时，通过这些策略使资源分配问题以组合拍卖的方式得到了解决，同时对协商策略的计算复杂性和通信瓶颈进行了分析。计算实验表明，提出的协商策略是可行和有效的。

关键词: 生产调度, 分布规则, 协商策略, 组合拍卖, 多智能体

Abstract: To solve the problem of resource allocation in the multi-Agent-based agile production scheduling, combinatorial auction based negotiation policy was proposed. With the description of the resource allocation problem, the design and the process of the combinatorial auction were provided based on combinatorial auction solution by utilizing the relationship between dual theory and combinatorial auction. With reference to the design result and auction process, the negotiation policy to realize the combinatorial auction was depicted and constructed by adoption of distributed rules, which would be saved in the rule base of corresponding Agents. The resource allocation problem was solved by the combinatorial auction in the distributed manner. Furthermore, the computational complexity and communication bottleneck of the negotiation policy were analyzed. Computational experiments suggested that the policy was feasible and effective.

Key words: production scheduling, distributed rule, negotiation policy, combinatorial auction, multi-Agent

中图分类号:

TH166

吕赐兴,，朱云龙，尹朝万，于海斌. 基于多Agent的敏捷生产调度中的协商策略[J]. .

LV Ci-xing,,ZHU Yun-long,YIN Chao-wan,YU Hai-bin. Negotiation policy for multi-Agent based agile production scheduling[J]. .

参考文献

［1］ RABELO R J, CAMARINHA-MATOS L M, AFSARMANESH H. Multi-Agent-based agile scheduling［J］. Robotic and Autonomous System, 1999, 27(1-2):15-28.

[2] WANG Yanhong, YIN Chaowan，ZHANG Y. A multi-Agent and distributed ruler based approach to production scheduling of agile manufacturing systems［J］.International Journal Computer Integrated Manufacturing, 2003, 16(2): 81-92.

[3] WANG Yanhong, YIN Chaowan. Multi-Agent and distributed-rules based agile production scheduling approach［J］. Control Theory & Application, 2004, 21(4):526-530(in Chinese).［王艳红，尹朝万. 一类基于多Agent和分布式规则的敏捷调度［J］. 控制理论与应用，2004，21(4)：526-530.］

[4] SHEN W. Distributed manufacturing scheduling using intelligent Agents［J］. IEEE Intelligent Systems,2002, 17(1): 88-94.

[5] SANDHOLM T, LESSER V. Leveled commitment contracting: a backtracking instrument for multi-Agent systems［J］.AI Magazine, 2002, 23(3): 89-100.

[6] SHEN W, DOUGLAS H N. Agent-based systems for intelligent manufacturing: a state-of-the-art survey［J］. Knowledge and Information Systems, 1999, 1(2):129-156.

[7] KUTANOGLU E, WU S D. On combinatorial auction and Lagrangian relaxation for distributed resource scheduling［J］. IIE Transactions, 1999, 31(9):813 -826.

[8] DEWAN P, JOSH S.Auction-based distributed scheduling in a dynamic job shop environment［J］. International Journal of Production Research, 2002, 40(5): 1173-1191.

[9] VRIES S D, VOHRA R V. Combinatorial auctions: a survey［J］.INFORMS Journal of Computing, 2003, 15(3): 284-309.

[10] CHEN H, CHU C,PROTH J M. An improvement of the Lagrangian relaxation approach for job shop scheduling: a dynamic programming method［J］.IEEE Transactions on Robotics and Automation, 1998, 14(5): 786-795.

[11] DEBRA J H, PETER B L,KRISHNA R P. A practical approach to job-shop scheduling problems［J］. IEEE Transactions on Robotics and Automation, 1993, 9(1): 1-13.

[12] KASKAVELIS C,CARAMANIS M. A Lagrangian relaxation based algorithm for scheduling multiple-part-production-systems:industrial implementation experience［A］. Proceedings of the 1994 Japan-U.S.A. Symposium on Flexible Automation［C］.New York,NY,USA:American Society of Mechanical Engineers,1994.173-180.

[13] BELLIFEMINE F,CAIRE G,RIMASSA G,et al.Java Agent development framework is an open source platform for peer-to-peer Agent based applications［EB/OL］. http://jade.cselt.it/, 2004-12.

[14] CORTESE E. Benchmark on jade message transport system［EB/OL］. http://jade.cselt.it/doc/tutorials/benchmark/JADERTTBenchmark.htm, 2003-12.

[1]	秦旋,房子涵,张赵鑫. 考虑资源约束的预制构件多目标生产调度优化[J]. 计算机集成制造系统, 2021, 27(8): 2248-2259.
[2]	马丽萌,乔非,马玉敏,刘鹃. 基于SO-GP的智能车间组合调度规则挖掘[J]. 计算机集成制造系统, 2021, 27(5): 1351-1360.
[3]	魏莹,刘冠,李锋. 基于社交网络效应的产品设计研究[J]. 计算机集成制造系统, 2021, 27(12): 3591-3603.
[4]	张文杰,王国新,阎艳,褚厚斌,王晶,曹志松. 基于数字孪生和多智能体的航天器智能试验[J]. 计算机集成制造系统, 2021, 27(1): 17-34.
[5]	吴晓强,田松龄,郑淑贤,项忠霞. 面向开放式结构产品的智能制造车间实时调度方法[J]. 计算机集成制造系统, 2020, 26(10): 2703-2713.
[6]	庄存波,刘检华,熊辉. 分布式自主协同制造——一种智能车间运行新模式[J]. 计算机集成制造系统, 2019, 25(第8): 1865-1874.
[7]	吴秀丽,张志强,赵宁,李俊青. 超启发式文化基因算法优化生产与预维修集成调度问题[J]. 计算机集成制造系统, 2019, 25(第8): 1885-1896.
[8]	王旭亮,柴旭东,张程,赵晓芳. 云制造环境下跨企业协同生产调度算法[J]. 计算机集成制造系统, 2019, 25(第2): 412-420.
[9]	费杨阳,马慧民. 批—离散机重入车间调度与设备维护联合优化[J]. 计算机集成制造系统, 2019, 25(第1): 44-52.
[10]	袁帅鹏,李铁克,王柏琳. 多目标炼钢—连铸生产调度的改进带精英策略的快速非支配排序遗传算法[J]. 计算机集成制造系统, 2019, 25(第1): 115-124.
[11]	张燕华,陈伟达,孟祥虎. 基于PBIL算法的炼钢生产低碳调度问题[J]. 计算机集成制造系统, 2018, 24(第10): 2407-2414.
[12]	姜天华. 基于灰狼优化算法的低碳车间调度问题[J]. 计算机集成制造系统, 2018, 24(第10): 2428-2435.
[13]	杨宏兵,沈露,成明,陶来发. 带退化效应多态生产系统调度与维护集成优化[J]. 计算机集成制造系统, 2018, 24(第1): 80-88.
[14]	韩端锋,周青骅,李敬花,李盟,杨博歆. 船舶建造物资追溯实体单元信息模型及追溯管理系统[J]. 计算机集成制造系统, 2017, 23(第9期): 1983-1991.
[15]	赵婷婷,曹政才,邱明辉. 面向半导体生产线基于MAS模糊协同的成品率预测方法[J]. 计算机集成制造系统, 2017, 23(第4期): 852-859.