引入除冰效率参数的非等同并行机调度问题——以飞机除冰为例

摘要

冬季或受冰雪天气影响，飞机在机场起飞前往往要进行除冰工作，即在除冰坪喷洒除冰液，一种由丙二醇合成的液体，旨在融化飞机表面的积冰，并保持飞机在短时间内不再结冰。否则，机体的积冰会破坏空气动力、增大飞行阻力，是飞机飞行的潜在威胁。尽管已经采取较为先进的集中式除冰方式（即在跑道特定位置设置专用除冰坪，所有需要除冰的飞机在起飞前都要进入除冰坪进行统一除冰），飞机却源源不断地到达机场的矛盾，面对除冰服务资源有限的局面，应该如何调度飞机的除冰顺序，对于改善机场的旅客滞留情况、提高机场的服务水平有着至关重要的作用。因此，本论文以机场除冰资源调度为研究重点，分析在除冰坪数量有限的情况下，应该如何调度飞机到除冰坪上，保证在有限时间内此顺序下得到的除冰飞机载客总人数最大，也就可以最大程度地减少旅客滞留比率。在这个问题中，由于除冰坪的除冰能力不一，存在容量限制，即较大型号的飞机不能在较小型号的除冰坪完成除冰工作。具有这一特性的飞机除冰问题显然是一个非等同并行机调度问题。
　　于是，本文首先梳理国内外在飞机除冰领域和并行机调度领域的文献资料，发现视飞机为并行机，以非等同并行机调度的思路来解决飞机除冰资源调度的文献并不多，研究问题上有一定的新颖性。针对这样一个寻求固定时间窗内最大化载客总人数的问题，本文特引入除冰效率参数，即飞机的载客人数同除冰时间的比值，比值大小反映该效率高低，建立除冰效率高的飞机优先除冰的数学模型。
　　在模型求解部分，鉴于本文问题同背包问题的特性有一定相似度，本文拟采用动态规划求解本问题，在算法设计中加入除冰效率参数，设计效率高的飞机排在除冰序列队首。由于蚁群算法在解决并行机调度问题上十分常用，本文以此算法为参照组，将除冰坪视作蚂蚁，寻找飞机序列的过程即为蚂蚁寻找最短路径的过程。仿真实例部分采用MATLAB随机产生的多组数据（包含飞机的载客人数、除冰时间等），证实了动态规划能够更好地解决固定时间窗内的非等同并行机资源调度问题，无论是载客总人数还是算法运行时间，动态规划的表现都优于蚁群算法，且表现差距随着问题规模的扩大而扩大。

目录

声明

摘要

第1章 引言

1．1．1 选题背景

1．1．2 研究意义

1．3 研究内容与创新点

1．3．1 研究问题

1．3．2 创新点

1．4 研究方法与技术路线

1．5 论文的结构安排

第2章 文献综述

2．1 飞机地面除冰调度的文献综述

2．2 并行机调度问题的文献综述

2．3 启发式算法的文献综述

第3章 蚁群算法和动态规划理论概述

3．1 动态规划理论

3．1．1 动态规划的基本思想

3．2．2 动态规划的求解步骤

3．2 蚁群算法理论

3．2．1 蚁群算法的基本思想

3．2．2 蚁群算法的求解步骤

第4章 滞留旅客人数最少的飞机除冰调度模型

4．1 问题描述

4．2 变量定义

4．3 数学模型

第5章 求解算法

5．1 引入除冰效率参数的动态规划算法设计

5．1．1 单台除冰坪的背包模型设计

5．1．2 引入效率参数的动态规划算法

5．2 改进蚁群算法设计

第6章 实例与结果分析

6．1．1 两种动态规划比较

6．1．2 蚁群算法及敏感性分析

6．1．3 算法结果的比较

6．2 多实例比较

第7章 总结与展望

参考文献

附录

致谢

个人简历