英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
基于排队网络的分布式航母甲板调度方法
Rajarshi Ghosh Dastidar
Massacusetts Institute of Technology, Cambridge, MA, 02139, USA
Emilio Frazzoli
Massacusetts Institute of Technology, Cambridge, MA, 02139, USA
摘要
在本文中，我们基于航母甲板作业的排队网络模型，提出了一种用于航空母舰随机调度的新方法。网络由为飞机服务的不同站点组成，如加油站、弹射器和着陆带。网络中的每个服务站点都遵循确定的飞机服务方案，然后决定飞机下一步将访问哪个相邻节点。解决这个问题的关键是构造生成好的调度方案与路由方案的方法。
我们从所有方案总集合的有限制条件的子集中找到最优调度方案，即基于线性指标的方案。选择那些最能区分飞机的参数来计算指标，并且依此组建易被人员实施的线性方案结构。然后通过基于仿真的优化找到最优方案。我们最终会获得可在每个节点由决策者实施的方案，从某种意义上说，这是一个分布式方案。此外，我们展示了该方案结构如何能够稳健可靠地处理系统故障，例如系统中发生意外停机或任务执行故障。它的一个有趣的特点是可以应用于各种问题，如车间调度和工厂生产。
术语
节点处特征值i的加权因子
特征x的值
第i类节点处由指标评定得出的方案
1引言
调度问题是一个重要的问题，有着悠久的历史和丰富的文献。我们都制定计划来记录我们工作的担保期限和最后期限。事实上，制定和遵守计划是所有工业活动的重要组成部分。一个关键的难点是找到一个最佳的调度方案。很长时间以来，调度工作都是由人们使用启发式常识性方案来完成的。直到20世纪末，人们才开始认真地通过学术研究来分析这个问题。也许这一领域最著名的工作是Graham[1]在1965年对车间调度的分析，这是第一个进行竞争分析的问题。很多论文从那时起被发表，这些论文考虑了许多不同场景的调度问题。在本文中，我们将研究这个问题的一个应用，即在航空母舰上的作业调度。
航母的甲板是一个非常动态的环境。飞机在起飞和精确执行任务之前，通常需要维修、加油和重新装弹。为了确保这些操作顺利进行，每天都需要手动确定主计划。然而，主计划几乎从未被完全遵循。这是因为任务有随机的处理时间，不同类型的故障在操作过程中不断发生，打乱了整个计划。每次出现故障或延迟时，操作人员都会重新人工临场处理。迄今为止，已经提出如反应式调度、鲁棒调度和随机调度等许多调度技术来处理调度过程中的干扰因素。其中，随机调度很有吸引力，相较于静态调度，它离线生成一个具有针对所有可能故障的措施的方案。
目前，航空母舰作业的人工调度启发式算法使用某种形式的排序。在加油站和武器装载站，通常采用先到先服务的方案。在弹射器处，使用最高优先级优先方案。最后，在着陆时，低燃油水平的飞机会被优先考虑。所有这些都只是基于评定指标的方案类型，通过使用不同的特征值来计算指标。这种基于指标的方案很容易被人类应用。在本文中，我们将限定于寻找一个基于指标的航空母舰调度方案。此外，正如以下研究表明，通过将我们自己限制在所有可能方案的子集中，我们可以简化寻找最优方案的工作。
研究的另一个目标是找到一个易于扩展的方案。随着飞机数量的增加，或者一些弹射器和加油站出现故障或加入工作，一个好的调度方案不应该因此受到太多影响。在日常运营过程中，航母上的某个站点有时会出现故障。如果故障很小并且可以快速修复，飞机将留在站点，当站点再次工作时，飞机的维修就可以完成了。这相当于延迟了进度。另一方面，如果维修站发生重大故障，那么在该站等待的所有飞机都需要改航到其他地方，并且在维修站修复之前，不能向其派发新的飞机。这可能会导致调度进程的中断，但这可以通过路由方案轻松处理，该方案只需要将飞机定位到在线的站点。这是使用弹性方案相对于固定计划的另一个优势，因为固定的计划无法处理这些变化。因此，在航空母舰上的日常操作中，飞机、加油站和弹射器的数量可以保持变化，并且该方案必须相应地弹性化，以便处理这些意外情况。
本文中，我们将提出一种利用排队网络进行随机调度的新方法。在排队网络框架内，我们将在一类容易被人类实现的方案中找到一个最优调度方案。该方案之后在麻省理工学院开发的仿真环境中实施。仿真环境的目标是使操作人员能够对不同的调度方案进行可视化实验。此外，调度任务制定的自动化减少了人力计划员的工作量，并允许他尝试变通和选择最适应他当前需求的方案。Ryan等人[2]在2011年所做的工作中表明，在低复杂度环境中，启发式算法的性能往往与调度方案一样好甚至更好；然而，随着工作负荷和复杂性的增加，调度方案的性能比启发式算法更好。
2调度的前期工作
给定一组任务、给定它们的工期和它们的时间窗逻辑约束，以此求出一个调度方案只是一个简单的问题。此外，给定一个目标函数，将每一个可行的调度都映射到一个值， 我们可以努力去找到最优的调度方案。有大量的文献说明如何优化调度，以满足这些约束。Karaman[3]在2009年就有这样一个例子，用进程代数来寻找一个最佳的调度。然而，如果任务的持续时间发生变化，那么先前找到的最优时间表可能很快变得不可行或次优。我们可以用下面的例子更好地演示这一点。假设我们有两架战斗机需要在加油站加油，如图1所示。
图1 调度的示例场景
换料的服务时间服从均匀分布U(5，15)。由于换料操作的预计时间为10分钟，如果我们根据预计时间进行计划，我们将得到表1:
然而，如果战斗机1的实际时间是12分钟，而战斗机2的时间是7分钟，那么计划表就变得不可行，因为当战斗机2应该开始加油时，战斗机1仍在服务中。另一方面，如果服务时间颠倒，即战斗机1需要7分钟，战斗机2需要12分钟加油，那么时间表保持可行。然而，它变得不太理想，因为最佳计划表如表2所示。
表1 基于预期服务时间的计划
|
计划表 |
战斗机1 |
战斗机2 |
|
服务时间 |
0（最小） |
10（分钟） |
表2 基于新服务时间的最佳计划
|
计划表 |
战斗机1 |
战斗机2 |
|
服务时间 |
0（最小） |
7（分钟） |
然而，先进先出(FIFO)方案对于这两种情况都是最佳的。根据这一政策，飞机1将首先得到服务，然后飞机2在飞机1完成后立即得到补给。正是因为这个原因，在1997年Goldratt[4]强烈反对静态调度技术。
处理工期的可变性问题有三种主要方法。最简单的方法是，只要任务工期与预期有所不同，就简单地重新计划。这种方法被称为反应式调度，可以简单修改调度，也可以完全重新调度。1993年Sadeh等人[5]开发的右移规则是一个优雅的算法，稍微调整现有的时间表，使其再次可行。该算法实质上是通过延长给定任务的工期来将调度向后移动。在前面给出的示例场景中，右移位规则足以确保反应式调度与先进先出方案相同。然而，一般来说，由右移位规则生成的可行调度可能不再是最优的，因为该算法不重新排列任务的顺序。为了保证最优化，一些专家主张全部重新调度。另一方面，在2000年像EI Sakkout和Wallace[6]这样的作者主张使用修复最小扰动的调度方案。但是，每次调度出现延迟或中断时，反应式调度都需要进行一定量的重新计算。使用调度策略可以避免重新计算。
另一种用于确保调度不中断的方法是使用鲁棒调度，本质上是对最坏情况的调度。例如，为了确保调度对于前面介绍的场景中的任何服务时间都是可行的，调度应该如表3所示。
表3 示例场景的最坏情况调度
|
计划表 |
战斗机1 |
战斗机2 |
|
服务时间 |
0（最小） |
15（分钟） |
如果调度每个任务都考虑最坏情况，那么这个调度方案肯定是不理想的。这是因为如果服务时间是从一个连续的有界分布中随机抽取的，那么最坏的情况几乎不会发生。为了提高性能，专家通常试图在稳定性和性能之间取得平衡。1995年Daniels和Kouvelis[7]遵循一种极小极大值补正技术，该技术将稳定性和最佳性能的偏差考虑到成本函数中。类似地，2004年Sim和Bertsimas[8]和2002年Christiansen等人[9]在优化调度时也在成本函数中加入了风险因子。1995年Gao[10]的研究和2001年Davenport[11]的研究分析基于松弛的调度技术。然而，总的来说，最优调度的性能优于鲁棒调度。
第三种方法是可以生成调度策略的随机调度。随机调度最早是由Mohring等人在1984[12]年和1985[13]年的系列论文中提出的。1994年Rabelo[14]在使用Q学习生成调度方案方面做了一些工作。然而，总体上关于随机调度的研究工作还很少。本文提出的基于排队网络的调度方法属于随机调度的范畴。生成这种调度方案的关键特征是它的计算时间要长得多。这是因为在方案中，必须明确所有可能情况对应的操作。另一方面，一旦找到了最优方案，就不需要重新调度，并且性能与完全重新调度等同。本质上，该方案离线进行所有可能的调度计算，而在反应式调度中，重新调度是在线进行的。与使用带有重新调度的静态调度相比，使用调度方案可以在运行时节省时间，但代价是额外的离线计算。在下一节中，我们将详细讨论使用排队网络的调度方法。
3排队网络模型
在本节中，我们将详细描述航空母舰操作的排队网络模型。在日常操作中，飞机有固定的任务顺序。它首先被补充燃料并重新武装，然后从弹射器上起飞，从那里开始执行任务。完成任务后，飞机返回航母，在马歇尔堆栈中等待着陆。一旦放行，它会降落在着陆跑道上，然后滑行到一个停机位置。通常，这个循环每天重复两次，总共两架次。因此，飞机的行动可以被建模为图形上的运动。图中的节点是加油站、武装站、弹射器、任务和着陆跑道等服务站。另一方面，连线表示滑行和飞行操作。如图2所示
图2 排队网络图
当飞机从这个图的一个节点移动到另一个节点时，它们会在每个服务站的队列中等待服务。该网络中的每个服务站都遵循特定的飞机服务方案，然后决定飞机下一次将访问哪个相邻节点。每个节点的服务时间从正态分布中得出，正态分布取决于节点的类型和飞机的类型。这些分布的均值和方差是从过去的统计数据中获得的。因此，航空母舰的调度问题就是为排队网络寻找调度方案的问题。此外，问题可细分为寻找所有节点的调度、路由和故障处理方案。
当前使用的路由方案是指派飞机到队列最小的相邻节点。但是，为了提高性能，可以将路由方案更改为指派到具有最短的预期等待时间的相邻节点。另一方面，故障处理方案取决于所处理的故障类型。如果弹射器或加油站发生故障，故障节点处的所有飞机都将被重新指派到附近的同类型服务节点。另一方面，如果出现燃油泄漏或液压泄漏等故障，这只会压缩飞机的着陆时间，从而需要根据着陆跑道方案去改善着陆位置。因此，由于路由方案和故障处理方案是已知的，剩下的就是找到加油站、弹射器和着陆跑道的调度方案。
通过对经验丰富的驾驶舱操作计划员的采访，我们发现目前在实践中遵循的基本方案可以很好地模拟为如下情形。在所有的服务器中，除了弹射器和着陆跑道，都使用先来先服务的方案。在弹射器上，遵循最高优先级优先方案，而在着陆跑道上，使用最早截止时间优先的方案。因此，一个基本目标是找到一个性能优于基本方案的方案。理想情况下，最好能找到一个最佳方案。由于寻找排队网络的最优方案已被Papadimitriou和Tsitsiklis[15]在1999年证明是一个EXP-Complete问题(即难以解决的问题)，我们试图使用近似方法来寻找一个近似最优的方案。以下部分描述了如何找到这样一个方案。
4调度方案生成
如前一节所述，航母作战可以按照排队网络建模。总体调度可以从网络每个节点遵循的调度子方案、路由和故障处理方案中生成。路由和故障处理方案在之前已有描述，本节将重点介绍如何在服务站点上找到调度方案。因为为排队网络找到一个最优调度方案是一个EXP-Complete问题，如果我们想更快找到新方案，最好的办法是使用近似技术。
此外，正如我们在前面几节中提到的，甲板操作人员已经使用了线性的、基于指标的方案；因此，从该集合中选择一个方案将确保该方案易于实现。因此，我们在基于线性指标的方案集内进行优化。
基于指标的方案是指任务的执行顺序由每个任务 “指标”的计算来确定。然后，任务按该指标的降序排列。因此，一旦一架飞机被服务，下一架要服务的飞机是在节点等待的飞机中权重指标最高的一架。该权重指标是由与该任务相关联的某些特征的值来计算的。在这个问题中，选择最能区分飞机的特征来计算权重指标。
因此，飞机类型、任务优先级、截止时间和到达节点的顺序被选为用于计算指标的
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239289]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
