| 【中文题名】 | 结合组织模型的多Agent分布式调度研究 |
| 【英文题名】 | Coordinate Multi-agent with Organization in Distributed Scheduling System |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-5 |
| 【中关键词】 | 多Agent算法,飞机地面作业,NP-完全,分布式约束满足问题,多价pi-演算,分布式调度 |
| 【英关键词】 | Airport ground service,Distributed constraint satisfaction problem,Distributed scheduling system,Multi-agent algorithm,NP-complete,Polyadic pi-calculus, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
许多工程领域中的调度和规划问题都相当地困难,尤其是大规模调度和规划优化问题。飞机地面作业调度(AGSS)就是这样的一个问题。
本文在回顾了飞机地面作业调度相关领域的研究后,首先对飞机地面作业调度问题在约束满足问题框架下进行了形式化。并证明了该问题是NP-完全(在某些情况下是PSPACE-完全)的困难问题。
随后提出了一个面向飞机地面作业调度问题的动态分布式调度模型、一个动态动态收集并融合飞机地面作业相关的数据的调度环境run-and-schedule和一个多Agent算法DSAFO(Dynamic Scheduling Agents with Federation Organization,具有联邦结构的动态调度Agent)。DSAFO算法引入了两种策略来满足飞机地面作业调度中的约束:局部启发式和基于Agent角色和联邦组织实现的全局协作。
DSAFO进行飞机地面作业调度的主要步骤是:实时地从run-and-schedule接收航班数据,将航班需求分解为许多子作业;利用多Agent动态地将每套子作业的解空间分割为合理的划分;在每个划分(Agent)内进行局部启发式求解;利用划... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
ABSTRACT |
6-15 |
|
第一章 绪论 |
15-22 |
|
1.1 什么是飞机地面作业调度？ |
15-18 |
|
1.2 研究意义 |
18-20 |
|
1.2.1 经济上的重要性 |
18-19 |
|
1.2.2 存在的管理问题 |
19 |
|
1.2.3 高效飞机地面作业调度的优点 |
19-20 |
|
1.3 论文主要工作 |
20 |
|
1.4 论文组织 |
20-22 |
|
第二章 研究现状和相关工作 |
22-37 |
|
2.1 飞机地面作业调度研究现状 |
22-23 |
|
2.2 JOB-SHOP 调度问题 |
23-24 |
|
2.3 分布式约束满足问题 |
24-26 |
|
2.4 协作多AGENT 系统 |
26-34 |
|
2.4.1 多Agent 系统 |
26-27 |
|
2.4.2 协作多Agent 系统 |
27-31 |
|
2.4.3 Agent 组织模型 |
31-34 |
|
2.5 多价PI-演算 |
34-37 |
|
第三章 飞机地面作业调度：形式化和特性 |
37-46 |
|
3.1 假设 |
37 |
|
3.2 形式化 |
37-44 |
|
3.2.1 飞机地面作业 |
38-39 |
|
3.2.2 飞机地面作业调度满足 |
39-42 |
|
3.2.3 飞机地面作业调度问题 |
42-43 |
|
3.2.4 不确定性飞机地面作业调度满足 |
43 |
|
3.2.5 不确定性飞机地面作业调度问题 |
43-44 |
|
3.3 实际飞机地面作业调度编程 |
44 |
|
3.4 特性 |
44-46 |
|
第四章 分布式动态调度模型 |
46-50 |
|
4.1 必要性 |
46 |
|
4.2 模型概览 |
46-47 |
|
4.3 RUN-AND-SCHEDULING |
47-50 |
|
第五章 DSAFO：概述、设计和实现 |
50-71 |
|
5.1 概述 |
50-52 |
|
5.2 DSAFO 中的策略 |
52-53 |
|
5.2.1 局部启发式 |
52 |
|
5.2.2 全局协作 |
52-53 |
|
5.3 DSAFO 中的 AGENT 角色 |
53-60 |
|
5.3.1 Blackboard |
54-55 |
|
5.3.2 ResourceAdmin |
55-56 |
|
5.3.3 Member |
56-59 |
|
5.3.4 Coordinator |
59-60 |
|
5.4 一个形式化的小结 |
60-64 |
|
5.4.1 Blackboard |
61-62 |
|
5.4.2 ResourceAdmin |
62 |
|
5.4.3 Member |
62-63 |
|
5.4.4 Coordinator |
63-64 |
|
5.5 复杂度 |
64-67 |
|
5.5.1 UC 的复杂度 |
64-67 |
|
5.5.2 DSAFO 的复杂度 |
67 |
|
5.6 实现 |
67-71 |
|
第六章 实验和参数分析 |
71-85 |
|
6.1 实验设置 |
71 |
|
6.2 算法参数 |
71-84 |
|
6.2.1 Member Agent 数量和Reqcycle |
72-76 |
|
6.2.2 Blockfactor |
76-79 |
|
6.2.3 Delayfactor |
79 |
|
6.2.4 Syncycle |
79-84 |
|
6.3 实验小结 |
84-85 |
|
第七章 算法对比 |
85-89 |
|
7.1 三种对比算法 |
85-87 |
|
7.1.1 MMAS |
85-87 |
|
7.1.2 EDD* 和ERT* |
87 |
|
7.2 优化对比 |
87-89 |
|
第八章 结论和未来研究方向 |
89-90 |
|
8.1 结论 |
89 |
|
8.2 未来研究方向 |
89-90 |
|
致谢 |
90-91 |
|
附录 A：DSAFO 算法中的 AGENT 通信语法 |
91-92 |
|
参考文献 |
92-106 |
|
攻读硕士学位期间所发表的论文 |
106-107 |
|
简历 |
107 |
|
| 【DOI】 | LunWen.ID:2.2008.388600 |
