一种新的解决资源约束的项目调度问题的高效模拟退火算法及它的多模式版本外文翻译资料

英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料

一种新的解决资源约束的项目调度问题的高效模拟退火算法及它的多模式版本

K. Bouleimen *, H. Lecocq

摘要：

本文描述了一种新的模拟退火算法，用于资源受限的项目调度问题（RCPSP）及其多模式版本（MCPSP）。考虑的目标函数是最大完工时间，传统的模拟退火搜索方法被一种新的设计所取代，这种设计考虑了项目调度问题解空间的特殊性。 RCPSP，搜索基于交替的活动和时间在对测试实例进行初步统计实验后，设置了递增过程和所有参数。为了MRCPSP，我们介绍了一种使用两个嵌入式搜索循环交替活动和模式邻域搜索的原始方法。文献中可用的基准实例进行的性能评估证明了目前最具竞争力的两种自适应算法的效率问题。

2002 Elsevier Science B.V. All rights reserved.

关键词：项目调度；资源约束；模拟退火

1. 介绍

本研究探讨资源受限的项目调度问题（RCPSP）及其对多模式资源受限项目调度问题（MRCPSP）的扩展。本文提出了一种基于模拟退火（SA）来解决这些问题。

当考虑最小化整个项目持续时间时，RCPSP和MRCPSP在文献中都很受欢迎，读者可以参考Herroelen等人的论文。[17，18]，布鲁克等。[8]和Kolisch和Padman[25]代表介绍和概述了项目进度问题的不同公式。

为了解决项目调度问题，文献中提供了很多方法，参考文献[18,25]详细描述了特性、表示和分类计划。建议的方法可以分为三类：精确方法[9–11,28,29]，优先级规则[4,12,20,22,27]和元启发式诸如tabu搜索[3,31]、遗传算法[2,14,19]或SA[6]等方法。要解决NP难题，最好的、精确方法要能够优化小型项目，通常少于60项活动。对于更大和更复杂的实例，启发式和元启发式方法对其他解决方案技术构成了一个真正的挑战，以在性能、可扩展性和易于实现之间提供最佳的权衡。最近的基准结果[2,16,24]表明，Alcaraz、Maroto[2]和Hartman[14]提出的遗传算法和我们的SA是目前可用于RCPSP的最佳执行方法，本文的第一部分详细描述了新的SA自适应。

对于MRCPSP，我们还发现文献中发表了一些研究，其中提出了一些精确的方法[15,30,32,33]、优先级规则[5,13,23]和元启发式方法[6,14]。作为RSPSP的概括，这个问题也是NP难题。最有效的精确程序无法用30个活动来优化解决一些基准实例。

对这个问题的元启发式适应仍在研究和改进，而且似乎是最有希望的。先前介绍的RCPSP的SA程序已扩展到MRCPSP，并且能够支持使用可再生和不可再生资源。这一新的程序使用原始的搜索策略在基准测试问题上进行了测试，结果证明非常有竞争力。本文的第二部分是对这一原始改编的描述。

本文的组织结构如下。在介绍和问题描述（第2节）之后，第3节介绍了SA方法。第4节描述了SA对所考虑的项目调度问题的新适应，并介绍了拟议程序的总体框架。在第5节中，我们通过初步实验解释了程序参数的设计，然后在第6节详细说明了性能评估中获得的结果。最后一部分给出了一般结论和评论。

2.问题描述和公式

2.1. RCPSP

RCPSP由一组集合按照源和优先约束来排列。如果集合中的任何一个前元素尚未完成排列，则优先约束将强制不启动任何步骤,对一组可再生资源定义的限制是每个资源R={1,hellip;,R}在每段时间内可用数量限制，每个动作j都是以非先发制人的方式处理的，并且在其持续时间期间使用资源r的单位。

计划项目包括为其所有活动分配开始日期，以便满足所有优先级和资源约束。优先级和资源可行性计划确定了总项目持续时间的最大值。

对于RCPSP公式，考虑的目标函数是最大限度地缩短执行时间。根据Herroelen等人提出的分类，这个问题用m，1/cpm/表示。[17]以及Brucker等人提出的用PS/Prec/表示[8]。

2.2. MRCPSP

在MRCPSP中，通过为每个行为j提供一组前置任务，在集合A上定义优先级约束。要处理这些活动，通常需要三类资源：集合r中的R类可再生资源，限制数量，集合中的不可更新资源，其中每个资源n在整个项目持续时间内受到有限数量的单位的限制，以及集合中的双重限制资源，对于这些资源d，每个资源d在总项目持续时间和时间段内都受到数量的限制。双重约束资源可以被视为前两个资源类别的一部分。每个活动j可以在个可能的模式中进行处理，其中每个模式m定义其资源需求与其持续时间之间的关系。因此，当在模式m中处理时，活动j将具有持续时间，在此期间，它使用可再生资源r的单位，并消耗不可再生资源n的单位。在MRCPSP中，目标是找到一个模式组合和一个最小化项目最大工期的时间表。Herroelen等人[17]将此问题表示为m，1T/cpm,mu/而在Brucker等人[8]表示为MPS/cpm/。

1. 模拟退火法

模拟退火法是一种局部搜索方法，它在统计力学研究的物理退火过程中得到了启发[1]，SA算法重复了迭代的邻域生成过程，并遵循改进目标函数值的搜索方向。在探索解空间的同时，模拟退火法方法提供了以受控方式接受更差邻域解的可能性，以避开局部极小值。更准确地说，在每次迭代中，对于以目标函数值为特征的当前解x，从表示的x的邻域中选择一个邻域，并将其定义为其所有邻域的集合。对于每一个动作，计算目标差异= -，对于最小化问题，每当le;0，则用代替x，否则，x也可以被概率P=所接受。将接受概率与随机生成的数字isin;[0,1]进行比较，并在P＞时接受x。

影响接受概率的因素是目标函数值退化程度（较小的退化会导致更大的接受概率）和参数T称为温度（T值越高，接受概率越高）。温度可以通过一个冷却方案来控制，该方案规定了如何逐步降低温度，以使程序在寻找良好解决方案的过程中更具选择性。存在保证渐近收敛到最优解的理论调度，它们需要无限的计算时间。在实践中，更简单和有限的计算安排是首选的，即使它们不能保证最优解。

模拟退火的一个典型的有限时间实现包括以S步降低温度T，从初始值开始，使用衰减系数alpha;（0＜alpha;＜1），初始温度应该足够高，以允许接受第一步中提出的任何新邻元素，在每个步骤s中，该过程生成固定数量的相邻解，并使用当前温度值=对其进行评估。整个过程通常称为“冷却链”或“马尔可夫链”。模拟退火对优化问题的适应包括定义其特定组件：问题的解决方案表示法目标函数值计算，解空间的邻域生成机制勘探和冷却方案，包括停止标准。下面描述了我们对RCPSP和MRCPSP模拟退火的新适应的这些适应步骤。

4.项目调度的模拟退火

4.1.介绍

当有效地适应优化问题时，模拟退火通常具有快速收敛和易于实现的特点。这些特性促使NP困难组合优化问题选择SA。

Boctor[6]首次将模拟退火技术应用于RCPSP。所提出的程序能够优于禁忌搜索算法和当时可用的一些最佳优先级规则[6]。然而，为了确认这一性能，必须对研究的主要问题进行进一步的调查和改进：模拟退火参数的具体设计，对更大和更复杂的实例的结果进行验证，并参考更具竞争力的方法进行性能评估。尽管我们选择了基于Boctor等人之前使用的活动列表的解决方案表示[24]。新的版本中，以原来的冷却方案为特点，大大提高了程序的效率，如第6节所示。

本文还提出了将模拟退火推广到多模式问题的方法。然而，他认为的构想不包括使用不可再生资源。因此，我们倾向于将我们的程序扩展到一个更通用的模型，并给出一个新的设计，用于邻近地区的勘探。

4.2.RCPSP解决方案程序

4.2.1.解决方案表示和计划生成方案

解的表示是模拟退火的一个重要组成部分。它必须设计成允许方便的邻居生成和快速计算。它还必须保证整个解决方案空间的可访问性。文献中提出了RCPSP的各种类型的解决方案表示，并在Kolisch和Hartmann[24]的论文中进行了综述。在本研究中，我们使用活动列表表示法，其中优先可行的解决方案由有序的活动列表表示。列表中的每个活动都显示在其所有前置任务之后的某个位置，图1a表示一个具有60个非虚拟活动的项目的可行活动列表示例。

作为一个调度过程，我们使用一个串行调度生成方案（SGS）[24]来适应活动列表的表示。此SGS交替执行“活动的开始时间分配”和“时间递增”两个操作，直到项目的所有活动包括虚拟完成活动都被计划好。通过固定=0处的时间来初始化过程。“开始时间分配”操作始终在时间固定时执行，并按照列表顺序一个接一个地连续测试未计划的活动。但是，在尚未计划其列表前置任务之前，不能测试任何活动。每当过程无法计划测试的当前活动时，“时间递增”操作都是必需的。

例如，当在固定时间=t，对活动j进行调度测试时，该过程首先检查j上的所有优先约束。然后，如果一系列的的所有活动都完成了，则检查可用资源量是否足以调度它。如果可以满足所有约束条件，则j被安排在时间t，在测试下一个活动之前，j所需的数量将从当前可用的资源量中检索出来。但是，如果调度j会导致任何约束冲突，“开始时间分配”操作会中断，尽管此时j的某些列表继承者可能是可调度的。然后执行“时间递增”操作，直到最早完成的活动将可行条件恢复到调度活动J。这些操作反复交替进行，直到所有项目活动都安排好。项目生成时间是虚拟完成活动的开始时间。完整的时间表是优先级列表和开始时间列表的关联（图1b）。我们注意到，正如在[21]中证明的那样，串行SGS只生成活动调度。我们的SGS还生成半主动计划[34]，因为它包括列表优先约束，同时搜索最早的优先权和资源可行时间来计划任何动作。

4.2.2邻代

邻代生成过程如下：在当前可行列表中，我们随机选择一个活动，并计算其最新的前一个和最早的后续活动的位置（图1c）。所选活动可以移动到这两个位置内的任何位置，以尊重优先约束。新位置也是随机选择的。如果可以移动，新列表将通过在新旧位置之间循环移动所有活动来获得（图1d）。

我们程序中使用的循环移位运算符对于半主动计划[34]中的最大跨度改进非常重要（图1e）。在某些情况下，列表上的循环移位会导致已移动活动在时间表上发生全局移位（图1f）。活动的全球转移对于半主动计划的改进和保持最佳计划的可达性至关重要。

4.2.3.冷却方案

本节描述了针对模拟退火适应提出的新冷却方案。我们的目标是通过引入一些与问题相关的参数，使用适合于RCPSP的搜索策略来提高过程的效率。我们首先介绍了新计划的主要特点，以便介绍该程序的总体框架。但是，所有的修改都是根据第5节中描述的初步实验的观察结果和结果进行的。冷却方案由以下部件构成：

bull;使用多冷却链（C）执行搜索，每次从不同的初始解决方案重新启动。在冷却链的每个步骤s中测试的溶液使用以下表达式=（1 h.s）逐渐增加。通过这种方式，该程序可以扩展其搜索范围，同时也可以扩展到具有良好解决方案的区间。参数h用于调节阶跃长度。

bull;在第一步中，初始降解被限制在20%的比例内（这是通过从表达式P（）=0.01中推导出初始温度值来实现的，该表达式将极低的接受概率分配给）。另一方面，对于大型项目，可以通过部分重新安排机制加快程序。

bull;在最后一步中，在生成个邻代（是平均邻域大小）后，该过程将强制保持解不变。在程序结束时，对找到的最佳解的邻域进行了全面的探讨。

模拟退火的有限时间实现意味着使用停止准则。它可以是总的处理时间、生成的邻代数量或目标值上的任何条件。根据我们对RCPSP模拟退火的适应，生成固定数量的解决方案所需的过程时间几乎与项目规模J成正比。因此，使用的主要停止标准是访问解决方案的总数。但是，只要程序满足与无约束问题相对应的关键路径值（在第一个初始化步骤中计算），程序就会停止。

4.2.4.程序的一般框架

图2给出了RCPSP新SA程序的一般框架。它建议使用多个冷却链执行搜索，其中每个链的设计允许有足够的时间对路径进行深度探索，然后执行该过程。每个链由几个步骤组成，其中访问的解决方案的数量随着温度的降低而逐渐增加。对于每一个实例，初始解都是通过最短的过程时间（SPT）启发式算法获得的。然后，使用允许的最大降解（）和初始目标函数值算初始温度。

4.3.MRCPSP解决方案

4.3.1.解决方案表示和计划生成方案

对于MRCPSP，使用两个列表表示可行的解决方案：与资源可行模式列表关联的优先可行活动列表。模式列表的可行性在于确保在调度过程中所需的每个不可再生资源n的总量不超过可用数量。

列表关联用于生成项目日程。首先，有必要使用模式列表来修正项目活动的所有与模式相关的需求。然后，对RCPSP执行相同的SGS，将开始日期分配给所有活动，从而确定制造时间。三个列表代表一个完整的时间表。MRCPSP的最大值取决于活动和模式列表。因此，可以生成一个邻居解决方案来修改列表中的任何一个或所有列表。

4.3.2. 邻代

在本研究中，我们建议使用“活动邻域”和“模式邻域”作为两阶段程序中的单独勘探技术。第一阶段是仅利用模式邻域探索寻找目标函数值改进。第二阶段在每次发现更好的价值时都会启动，包括对与第一阶段获得的新解决方案相对应的RCPSP子问题进行的活动邻域勘探。子问题是通过使用模式列表修复模式相关需求和从资源列表中删除不可再生资源而产生的。

为了生成模式邻代，优先级列表保持不变；对于随机活动，当前模式被另一个模式替换。如果新模式符合不可更新的资源约束，则接受该模式。当只有当前模式可行时，将选择另一个活动。第

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19025]，资料为PDF文档或Word文档，PDF文档可免费转换为Word