基于多Agent的多任务协作时间调度算法研究

摘要/Abstract

摘要： 为了合理安排多任务合作中的时间，设计了基于多Agent通信的多任务协作时间调度算法，实现了额外代价最小化和窗口时间内完成任务最大化。其中，算法的求解过程利用了0-1背包问题的最优值和最优解；对0-1背包问题的求解利用了改进的编码和进化的遗传算法，提高了运算的准确性。多任务协作时间调度算法的应用，有效地最小化了系统的额外代价，实现了多Agent系统的优化。

关键词: 多代理系统, 任务调度, 遗传算法

Abstract: In order to effectively schedule for cooperating among multi-tasks, the scheduling algorithm based on multi-agent was designed. With application of this scheduling algorithm, the extra cost of system was minimized and the most tasks were completed in due window. The process of finding the solution made use of the best value and the best solution of 0-1 knapsack problem. The solution to the 0-1 knapsack problem utilized improved genetic algorithm in coding and evolution to increase correctness. Application of the proposed algorithm has implemented the optimization of multi-agent system.

Key words: multi-agent system, task scheduling, genetic algorithm

中图分类号:

TP301.6

胡晶晶，曹元大，焦德朝，徐丽. 基于多Agent的多任务协作时间调度算法研究[J]. .

HU Jing-jing, CAO Yuan-da, JIAO De-chao, XU Li. Research on collaborating times scheduling algorithm of tasks based on multi-agent[J]. .

参考文献

［1］ GENG Zhaoqiang, ZOU Yiren. Study on job shop fuzzy scheduling problem based on genetic algorithm ［J］.Computer Integrated Manufacturing Systems,2002,8(8):616-620(in Chinese). ［耿兆强,邹益仁.基于遗传算法的作业车间模糊调度问题的研究［J］.计算机集成制造系统,2002,8(8):616-620.］

[2] HUANG Decai ,GUO Haidong.Hybrid genetic algorithm for solving job scheduling problem on non - identical parallel machines based on JIT technique ［J］.Computer Integrated Manufacturing Systems,2004,10(3):298-302(in Chinese). ［黄德才,郭海东. 基于JIT 的非等同并行多机调度问题的混合遗传算法［J］. 计算机集成制造系统，2004, 10(3):298-302.］

[3] ZHAO Bo, FAN Yushun. Multi-agent based integration of scheduling algorithm［A］. Proceedings of the IASTED International Conference-Intelligent Systems and Control［C］.2001.55-59.

[4] SOUSA P, RAMOS C. A distributed architecture and negotiation protocol for scheduling in manufacturing systems ［J］ . Computers in Industry, 1999,38 (2):103-113.

[5] SUN J,XUE D. A dynamic reactive scheduling mechanismfor responding to changes of production orders and manufacturing resources ［J］. Computers in Industry,2001，46（2）：189-207.

[6] WOOLDRIDGE M,SHI Chunyi,ZHANG Wei,et al. An introduction to multi-agent systems ［M］. Beijing:Publishing House of Electronic Industry, 2003(in Chinese). ［WOOLDRIDGE M,石纯一,张伟，等.多Agent系统引论［M］.北京:电子工业出版社,2003.］

[7] CHEN Quanle, SUN Shijie. An earliness and tardinessproblem in single machine scheduling with a common due window ［J］. Application Mathematics Journal of China University,2000，15（4）:440-448（in Chinese）. ［陈全乐，孙世杰.一个宽容交货超前延误单机排序问题［J］.高校应用数学学报,2000，15（4）:440-448.］

[8] WANG Ling.Intelligent optimization algorithms with applications ［M］. Beijing:Tsinghua University Press,2001(in Chinese). ［王凌.智能优化及其化算法［M］.北京:清华大学出版社,2001.］

[9] ZHU Jianying. Non-classical for intelligent system ［M］. Wuhan:Huazhong University of Science and Technology Press,2001(in Chinese). ［朱剑英.智能系统的非经典数学方法［M］.武汉：华中科技大学出版社,2001.］

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	周博文,黄海军,徐怡,李学俊,高寒,陈天翔,刘晓,徐佳. 无人机配送系统中端边协同的并行任务调度算法[J]. 计算机集成制造系统, 2021, 27(9): 2575-2582.
[3]	满君丰,赵龙乾,彭成,李倩倩. 云边协同计算架构下大规模工厂接入的任务调度[J]. 计算机集成制造系统, 2021, 27(8): 2282-2294.
[4]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[5]	黄晓冬,端木帅飞,毕敬,苑海涛. 服务延迟保障的混合绿色云数据中心成本最小化方法[J]. 计算机集成制造系统, 2021, 27(8): 2416-2425.
[6]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[7]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[8]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[9]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[10]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[11]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
[12]	李从东,章志伟,曹策俊,张帆顺. 复杂产品设计变更传播路径的多目标优选[J]. 计算机集成制造系统, 2021, 27(3): 842-856.
[13]	杨小明,徐子奇,金雯,舒帆. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.
[14]	阴艳超,张万达,廖伟智,牛红伟. 分布式科技资源多服务任务优化调度[J]. 计算机集成制造系统, 2021, 27(11): 3209-3218.
[15]	李丽丽,陈琨,高建民,李辉,冯增行,张建. 采用优化概率神经网络的质量异常识别方法[J]. 计算机集成制造系统, 2021, 27(10): 2813-2821.