结合组织模型的多Agent分布式调度研究

摘要

许多工程领域中的调度和规划问题都相当地困难，尤其是大规模调度和规划优化问题。飞机地面作业调度(AGSS)就是这样的一个问题。 本文在回顾了飞机地面作业调度相关领域的研究后，首先对飞机地面作业调度问题在约束满足问题框架下进行了形式化。并证明了该问题是NP-完全(在某些情况下是PSPACE-完全)的困难问题。 随后提出了一个面向飞机地面作业调度问题的动态分布式调度模型、一个动态动态收集并融合飞机地面作业相关的数据的调度环境run-and-schedule和一个多Agent算法DSAFO(Dynamic Scheduling Agents with Federation Organization，具有联邦结构的动态调度Agent)。DSAFO算法引入了两种策略来满足飞机地面作业调度中的约束：局部启发式和基于Agent角色和联邦组织实现的全局协作。 DSAFO进行飞机地面作业调度的主要步骤是：实时地从run-and-schedule接收航班数据，将航班需求分解为许多子作业；利用多Agent动态地将每套子作业的解空间分割为合理的划分；在每个划分(Agent)内进行局部启发式求解；利用划分间的协作进行全局解的优化；并同时将结果分发到飞机服务资源上。 DSAFO算法具有不错的时间复杂度：介于平方和三次方之间。虽然实验证实DSAFO是不稳定算法，而且受到几个参数的影响，但是该算法能够很好地满足全部约束、跳出局部极小值、寻找资源耗费和人力分配的近优解。在对参数造成的影响进行了深入的实验和理论分析后，文章将DSAFO算法同MMAS蚂蚁算法和传统启发式算法进行了实验对比。 最后给出了DSAFO的研究总结和飞机地面作业调度问题的未来研究方向。

目录

文摘

英文文摘

论文说明：专业缩写索引

中国民航大学学位论文独创性声明及使用授权声明

第一章绪论

1.1什么是飞机地面作业调度?

1.2研究意义

1.2.1经济上的重要性

1.2.2存在的管理问题

1.2.3高效飞机地面作业调度的优点

1.3论文主要工作

1.4论文组织

第二章研究现状和相关工作

2.1飞机地面作业调度研究现状

2.2 Job-Shop调度问题

2.3分布式约束满足问题

2.4协作多Agent系统

2.4.1多Agent系统

2.4.2协作多Agent系统

2.4.3 Agent组织模型

2.5多价π-演算

第三章飞机地面作业调度：形式化和特性

3.1假设

3.2形式化

3.2.1飞机地面作业

3.2.2飞机地面作业调度满足

3.2.3飞机地面作业调度问题

3.2.4不确定性飞机地面作业调度满足

3.2.5不确定性飞机地面作业调度问题

3.3实际飞机地面作业调度编程

3.4特性

第四章分布式动态调度模型

4.1必要性

4.2模型概览

4.3 Run-and-scheduling

第五章DSAFO：概述、设计和实现

5.1概述

5.2 DSAFO中的策略

5.2.1局部启发式

5.2.2全局协作

5.3 DSAFO中的Agent角色

5.3.1 Blackboard

5.3.2ResourceAdmin

5.3.3 Member

5.3.4 Coordinator

5.4一个形式化的小结

5.4.1Blackboard

5.4.2 ResourceAdmin

5.4.3Member

5.4.4 Coordinator

5.5复杂度

5.5.1 UC的复杂度

5.5.2 DSAFO的复杂度

5.6实现

第六章实验和参数分析

6.1实验设置

6.2算法参数

6.2.1 Member Agent数量和Reqcycle

6.2.2 Blockfactor

6.2.3 Delayfactor

6.2.4 Syncycle

6.3实验小结

第七章算法对比

7.1三种对比算法

7.1.1 MMAS

7.1.2 EDD*和ERT*

7.2优化对比

第八章结论和未来研究方向

8.1结论

8.2未来研究方向

致谢

附录A：DSAFO算法中的Agent通信语法

参考文献

攻读硕士学位期间所发表的论文

简历