项目鲁棒调度资源分配方案优化算法研究

叶博童

摘 要：由于活动间的资源争抢会使调度计划在执行过程中失效，因此合理的资源分配方案对于调度计划至关重要。基于现有研究成果提出了SCAS（Superior Chain Allocation Scheme）算法，在资源分配时优先选择优质资源链为重要活动提供资源，同时尽可能减少附加约束数量，保证资源按时传递给重要活动，降低资源冲突对进度计划鲁棒性的影响。

关键词：鲁棒调度；资源分配；优化算法

中图分类号：TB 文献标识码：A doi：10.19311/j.cnki.16723198.2019.32.099

0 引言

在项目调度过程中，由于施工环境等各种变化可能使实际执行情况与预期计划发生偏离，造成项目成本过高和延期完工，所以在计划阶段需要制定具有较高鲁棒性的项目调度计划来指导实际工作。

自从Artigues等首次提出资源流网络的概念，并将其引入到项目调度研究后，很多学者都对资源约束项目调度问题进行了深入的研究。Leus R等基于资源流网络设计了一个动态资源分配模型。Artigues等通过随机选择活动对进行资源分配得到可行的资源流网络。虽然该算法较为简单，但在资源分配时随机性较大。Policella等在资源分配过程中提出了链的概念，通过为活动分配一定数量的链来完成资源配置。Nalan等通过估计活动的边际效用来确定资源分配的顺序，但是这种算法的计算时间较长，不利于大规模项目的求解。

考虑到现有研究中的不足，本文提出了SCAS算法，SCAS算法以资源链的方式进行资源分配，并定义优质资源链和活动位置系数，通过位置系数来判断活动的重要程度，优先分配优质资源链为重要活动提供资源，尽可能保证了项目调度按计划进行。同时，在分配时充分利用优先关系传递资源，减少附加约束数量，得到了鲁棒性最好的资源分配方案。

1 问题描述与数学模型

1.1 问题描述

本文采用单代号网络图描述项目，项目网络图G（N，A）由节点活动1到节点活动n一共n个活动组成，N表示节点集，A表示逻辑关系约束形成的弧集。活动j（j=0，1，…，n）的开始时间为sj，活动工期为dj，第kk∈K种资源的初始需求量为rjk，第k种资源的资源限量为Rk。fijk表示活动i传递给活动j第k种资源的资源量，并生成资源约束（i，j）。

1.2 问题提出

在项目实施过程中，各种环境因素的影响最终会导致项目活动不能按计划执行。本文将活动的实际开始时间与预期开始时间进行比较，以各活动的时间差值与相应权重的乘积来衡量计划的鲁棒性，目标函数是惩罚成本最小化，min∑j∈NωjE（sj-sj）。

2 SCAS算法

资源分配产生的附加约束会影响活动间的依赖性，降低方案的松弛性。本文将资源以资源链的方式进行分配，通过识别对项目影响较大的活动并优先满足其资源要求，尽可能降低重要活动因资源延迟对项目整体调度的影响，提高调度计划鲁棒性。

2.1 算法原理

本算法按阶段一次性分配资源。在资源分配时，通过活动在项目调度中的位置判断活动被延误的可能性，当活动的实现路径较复杂且前项活动较多时，活动被延误的可能性较大，因此，优先分配延误可能性较大的活动。在选择资源链时，优先选择紧前活动占用的资源链为其提供资源，若资源需求未被满足时，区分优质资源链，选择优质资源链占有量较多的优质活动为其提供资源，降低附加约束对活动的不利影响。

2.2 链式调度

Policella用一组资源链表示资源，通过选择资源链为活动提供资源。而链式调度在选择资源链时只考虑了优先关系，忽略了资源链间的差异。当资源链流经活动数较多时，因其他活动延误造成资源链占用时间过长的可能性越大，资源链按时流入后序活动的可能性越小。本文将资源链根据其流经活动数进行比较，并将流经的活动数少的资源链称为优质资源链。

2.3 阶段路径图

在一个调度计划中，各个活动对整个调度计划的影响是不同的。假设每条路线阻塞的概率是一样的，那么活动前向约束数量越少，延迟的几率会减少。同理，整个项目的约束数量越少，项目的延期几率就会越少。因此，在进行资源分配时应优先分配延误可能性较大的活动。为了描述活动实现的难度，本文通过识别活动的实现路径图计算活动的位置系数，以此判断活动延误可能性大小。

阶段路径图描述了实现该活动所需进行的全部过程，由开始节点到该活动节点之间所有需要经历的活动节点和路线组成。本文定义位置系数为前向活动数（所有实现路径上的活动总数）与路径条数的乘积。

2.4 算法步骤

本算法按阶段一次性分配资源，首先将活动按照开始时间排序生成活动顺序表，以活动开始时间为阶段

开始点。在每个阶段生成前向活动表和后向活动表，后向活动按照位置系数由大到小排序，按順序对后向活动分配资源链。分配时优先选择有逻辑关系的紧前活动占用的优质资源链提供资源；若仍不能满足资源需求，根据附加约束数最少的原则，优先选择资源链占用量不少于需求量的前向活动提供资源，若符合条件的前向活动不止一个，选择优质资源链较多的活动提供资源，以降低其他活动的延迟对后向活动产生影响的概率。

2.5 算例结果

本文算法采用MATLAB 2014a实现，根据图1所示的项目算例，本文算法生成的资源分配方案如图2所示。以第三阶段为例，初始后向活动排序表为（6，7，5，8），初始前项活动顺序表为（1，4，2，3）。为活动6选择资源链时，因为活动2和活动4是活动6的紧前活动，而活动2占用的优质资源链较多，所以选择活动2的第1～4条资源链和活动4的第5条资源链为活动6提供资源；活动5无紧前活动，优先选择优质资源链较多的活动1提供第13、14条资源链。本算法生成的资源分配方案中附加约束仅为2条。本算法在资源分配中考虑了最小化资源分配对项目调度的影响，有效提高了项目调度计划的鲁棒性。

3 結语

由于资源在活动间传递可能使活动间依赖关系变得更加复杂，从而降低项目调度计划的鲁棒性，因此，合理的资源分配方案对项目按时完成有重要的影响。本文在生成资源分配方案的过程中充分考虑资源分配对活动的影响，提出了SCAS算法，通过阶段重要活动的识别及优质资源链的分配，实现了局部最优分配，保证关键活动按计划进行，继而提高了项目调度计划的鲁棒性。

参考文献

[1]Artigues C，Roubellat F.A polynomial activity insertion algorithm in a multiresource schedule with cumulative constraints and multiple modes[J].European Journal of Operational Research，2000，127（2）：297316.

[2]Leus R，Herroelen W.The complexity of machine scheduling for stability with a single disrupted job.Operations Research Letters，2005，33（1）：151156.

[3]张沙清，陈新度，陈庆新.基于优化资源流约束的模具多项目反应调度算法[J].系统工程理论与实践，2011，31（8）：15711580.

[4]Policella N.Solve-and-Robustify Synthesizing Partial Order Schedules by Chaining[J].Journal of Scheduling，2009，12（3）：299314.

[5]Nalan Gülpnar，Ethem anakoglu，Juergen Branke.Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities[J].European Journal of Operational Research，2017，23（8）：3441.

[6]Hazir¨ O，Haouari M，Erel E.Robust scheduling and robustness measures for the discrete time/cost trade-off problem[J].European Journal of Operational Research，2010，207（2）：633643.