考虑主/被动资源约束的随机MDP项目调度优化*

杨建卫，任晓莉，李乃乾

宝鸡文理学院，陕西 宝鸡 721016

1 引言

资源约束调度问题最早于1998年提出，开始于一个海军合作项目，干船坞是主要的资源约束项。其中空间是在制造业中普遍存在的资源约束问题，对企业产能的提升具有制约性，因此研究制造业中的资源约束问题具有非常重要的工程意义[1]。但是空间资源约束问题的最大难点在于问题处理的不确定性。在以往的研究中，对调度和项目调度的研究主要是考虑固定资源容量和确定工期问题。然而，在现实环境中，只获取确定性信息是不现实的。因此，不确定性已成为近几十年来项目调度的一个不可避免的问题。在过去的几十年中，很多作者探讨了许多处理不确定性项目调度问题[2]。

第一个研究重点主要是考虑资源受限项目调度的随机项目最小化完工时间的问题。策略是一组决策规则，它决定特定决策时刻的某些动作，这些是项目执行的完成时间。考虑资源受限项目调度的随机项目最小化完工时间问题已经提出了很长时间，文献[3]提出了一种针对考虑资源受限项目调度的随机项目最小化完工时间问题寻找全局最优的调度策略，实现了资源调度过程的优化。文献[4]提出一种基于资源约束的项目调度模型，该算法也是基于最小化完工时间的资源约束的项目调度优化过程，其根据项目调度过程特点设计了一种单目标形式的项目调度优化方法；文献[5]基于半正定规划建立项目调度优化算法，实现了资源约束的项目调度完工时间的最小化，这种半正定方法一定程度上可实现项目调度过程的简化。总体上，考虑资源受限项目调度的随机项目最小化完工时间的问题的研究成果不多，原因可能是找到这样一个最优策略似乎是难以计算的，因此大多数作者集中于在预定义的策略类中找到最优或接近最优的策略。例如，优先级策略类、早期启动策略类、（线性）预选策略类、基于活动的策略类和预处理器策略类。

第二个研究重点是主动和被动的项目调度问题研究。第一阶段是建立时间调度表，这就是所谓的基准调度，对某些类型的不确定性具有最大的鲁棒性。第二阶段是对正在进行的项目计划中发生冲突时合理地进行重新调度安排（冲突响应）。当前已有很多文献对这个问题进行了研究，例如，文献[6]研究了人员不确定性对于项目调度问题的影响，并设计了针对人员不确定性的目标优化函数，实现了对项目调度过程的优化分析；文献[7]提出一种考虑学习/遗忘因子的项目调度优化框架，实现了项目调度优化模型的自适应学习，其本质上是一种多目标项目调度优化方法。文献[8]指出即使在单机环境下，具有单一冲突和优先约束的调度也是强NP-难的。文献[9]提出精确的方法来构造一个只有一个冲突情况下的鲁棒基线时间表解决方案。文献[10]主要研究目的是寻求理想质量和解决方案健壮性之间的权衡。文献[11]提出了针对资源流依赖的浮动因子鲁棒调度启发式方法等。

上述文献在研究中存在的主要问题有两方面：（1）忽略了反应性调度策略的选择对基线调度最优性的影响。该过程不仅提供了基于仿真的启发式解决方案，而且还从一类早期启动策略中选择了被动策略，这极大地限制了过程的灵活性。（2）只是简单地假设这些项目执行响应对于基准调度以及调度策略的制定不存在影响。事实上，这种假设是不准确的，因此激发了基线调度的必要性。

对此，本文提出一种考虑主动/被动资源约束的随机图马尔可夫决策过程（Markov decision process,MDP）的项目调度优化方法，引入一种新的应对冲突的方法，并将主动和被动项目调度问题作为一个单一的综合问题来制定，然后利用Markov过程对上述项目调度优化问题进行建模。实验结果验证了所提方法的有效性。

2 问题模型描述

2.1 问题定义

首先介绍主动和被动资源约束的项目调度问题。给出了每个问题实例表达所需参数定义[12-13]：

（2）资源约束集合R，在处理时间内，每个项目i需要rik单位的资源类型k∈R。资源类型k的资源的可用性可表示为Rk。

2.2 解集的项目执行链表示

前人的研究一般将主动调度和被动调度作为两个独立的问题，因此，这两个问题的解决方案表示也不同。对此，这里提出一种综合主动和被动资源约束的解决策略（PR-策略）。在PR-策略调度中，对于每个项目pl，如果该项目执行，则其会产生vΠ,i的响应序列，该响应序列为ΦΠ,l：

只有在项目执行结束时，PR-策略的调度才知道项目的发生及其相关联的连锁反应。解集的项目执行链中，如果存在死路节点，则称该项目执行链为死链，引入参数γΠ,l对死链情形进行区分，如果ΦΠ,l为项目执行的死链，则γΠ,l=1，否则γΠ,l=0。对于PR-策略Π的每个项目调度执行顺序链ΦΠ,l计算其综合成本费用f(Π,l)，形式为：

其中，ωb≥0表示基准调度的完成时间成本。ωr≥0是每个项目执行响应产生的固定成本。ωi,k≥0表示在第k次响应中，项目i的启动时间偏离所造成的单位时间成本增加。M表示项目执行链路中存在死路的惩罚因子。

成本函数由三部分组成：（1）从管理的角度来看，基准调度过程的成本，是违反最初商定的项目交付时间的成本。（2）序列项目反应的成本，其中ωi,k可以看作是项目进行重新规划的成本。ωi,k可以被认为是处理项目响应的行政（固定）成本。（3）死链所造成的惩罚成本。

参数ωb、ωr和M可用于确定各部分在合并成本中的权重份额。PR-策略Π由一组决策规则描述，也可以由其相关联的一组执行顺序链来描述：

PR-策略Π的预期合并成本：

类似于执行链的合并成本，PR-策略Π的预期合并成本也由三部分组成：基准调度过程的成本、序列项目反应的成本以及死链所造成的惩罚成本。

2.3 优化目标模型

解集的项目执行链表示，可将问题表示为相对紧凑的形式。具体可由以下定理进行表示：

定理1基于项目执行链表示的PR-策略规模是有界的，其上界为，其中mi表示不同项目的离散持续时间。

证明假定每个PR-策略包含|β|个执行顺序链，这个数量可能非常大。首先，证明对于PR-策略Π的每个执行顺序链最多具有个响应。同时，考虑可以从S中选择的一个任意的调度表如果调度表对于pl是可行的，则PR-策略Π不产生任何的响应，执行顺序链ΦΠ,l的大小为1；否则，PR-策略Π在时刻t1上执行调度策略的有关响应。假定存在一个项目i1会导致调度表对于p′是不可行的，则有：

其中，α(s,p,i)是使得调度表s对于p是可行的的最大取值。同时，注意到项目i1可能会引起执行顺序链ΦΠ,l的另一个调度策略不可行，类似的，则可定义：

通过上述定义可得到α(s,pl,i)的不同取值，其中s是任意的调度方案，最大规模为mi，由项目i8所造成的不可行项目执行链的最大数量及其所需要解决的响应数量等于mi。类似的论点对任何其余项目i∈N{i1}都是成立的，因此可以得到非常直接的结论，即每个链包括最多的响应。由此可得，基于项目执行链表示的PR-策略规模是有界的，其上界为

这里定义所有可能PR-策略集Π，即PR-策略集可利用S进行构造，对P进行简化：

式中，P是一个非常难解决的问题，即使对于非常小的实例也是如此。这里将P的求解问题简化为P1的求解问题，其包含较小的策略集：在上述优化模型中，Π1是所有的PR-策略中只包括在S内的调度表。

3 解决方法

问题P可以被建模为马尔可夫决策过程（MDP）。本文的模型描述如下：（1）给定模型的状态描述；（2）引入状态之间的转换；（3）递归系统描述；（4）通过例子介绍图表示方法；（5）提出调度表生成算法。

3.1 状态描述

组合(s,t,O,v)表示模型的状态，其中s表示当前调度，t是当前时刻，O表示在时刻t中正在进行的项目集，v表示项目执行响应总数。状态可被标记为可行的或不可行的。令J(s,t)是s中所有应该在t时间启动的项目集合。

定义1（可行与不可行状态）如果状态(s,t,O,v)可以并行执行J(s,t)⋃O中所有的项目，则称其为可行的，否则为不可行。

3.2 状态转换过程

状态转换过程中，进入状态(s,t,O,v)意味着调度方案s被认为是执行的，当前时刻是t,O中的项目正在执行，冲突次数为v。取决于是否面临冲突，也取决于所选择实现和PR-策略，可进入不同状态。当且仅当两个状态之间存在弧线时，两个状态间转换是可能的。如果状态(s,t,O,v)是可行的，这意味着没有冲突发生，在这个决定时刻不需任何反应。

在这种情况下，需要对新状态(s,t′,O′,v)进行转换，其中，t′是在时刻t之后的s的决策时刻，O′⊆O⋃J(s,t)。s之后下一个决策时刻是最小t′＞t，满足∃i∈N，st=t′。集合O′可能取决于项目执行过程的不同，在离开可行状态时，可以从左侧状态进入有机会弧存在状态。连接 (s,t,O,v)和 (s,t′,O′,v)机会弧为：(s,t→t′,O→O′,v)。当状态转换从 (s,t,O,v)到(s,t′,O′,v)过程中，每个活跃项目O⋃J(s,t)都具有以下可能中的一种：（1）活跃项目i从时刻t不间断地持续到t′，因此存在i∈O⋂O′；（2）活跃项目i从时刻t开始不间断执行，并在时刻t′前结束，因此存在i∈OO′；（3）活跃项目i从时刻t启动，并且不间断持续到t′，因此存在i∈J(s,t)⋂O′；（4）活跃项目i从时刻t启动，并在时刻t′前结束，因此存在i∈J(s,t)O′。可利用活跃概率的乘积计算在某个机会弧下的跃迁(s,t→t′,O→O′,v)几率：

离开可行状态的机会弧的概率之和必须等于1。如果O=∅ 且有J(s,t)={n+1}，则项目的执行已经完成，没有机会弧离开(s,t,O,v)，在此情形下，(s,t,O,v)是终结状态。

离开不可行状态后，决定转移到可行状态。然而，并非所有的转换都是有效的。当且仅当U(s,t)=U(s′,t)以及si=si′(i∈NU(s,t))，则在不可行状态(s,t,O,v)到可行状态(s′,t,O,v+1)之间确实存在一个决策弧。图1描述了状态(s,t,O,v)的甘特图形式。

Fig.1 State conversion Gantt diagram图1 状态转换甘特图

图1中F代表了项目的完成时间，O表示在时刻t启动的项目，U(s,t)表示在时间t之前没有开始执行的调度表s中的活动。F和O中项目的开始时间应该完全相同，在时刻t从状态s到s′的转换意味着管理团队根据调度表s′可决定项目是否执行，这些转换称为正常转换。

对于每个不可行状态(s,t,O,v)，引入Γ1(s,t,O)代表所有调度集，均存在可从(s,t,O,v)转换得到的有效状态。如果s′∈Γ1(s,t,O),则存在从状态(s,t,O,v)到(s′,t,O,v+1)的状态转换。集合Γ1(s,t,O)的规模越大，则调度过程的响应越灵活。如果S是有限集合，则集合Γ1(s,t,O)可能是s、t和O的一些组合的空集。如果状态(s,t,O,v)是不可行的，且有Γ1(s,t,O)=∅ ，则其不存在项目响应的可能，可将这种状态标记为“deadstate”。

3.3 动态规划算法

这里引入d1(s→s′,t,O,v→v+1)作为直到执行结束前决定从状态(s,t,O,v)向(s′,t,O,v+1)转换的期望成本。同时，引入c1(s,t,O,v)作为直到执行结束时，离开可行状态(s,t,O,v)的预期成本。首先，计算每个决策弧直到执行结束的预期成本：

然后，最佳决策及其相关的预期成本为：

令F1是所有可行状态的集合，I1是所有不可行状态的集合。同样，所有终止状态“endstates”和“deadstate”分别表示为E1和D1。函数c1(s,t,O,v)可计算为：

式中，t′是时刻t后做出第一个决策时刻，O′是满足O′∈O⋃J(s,t)的任意集合。需要选择S中调度表作为基准调度表。为此，可在解决模型的过程中使用所提供的信息。基准调度表选择成本是c1(s,0,∅,0)+ωbsn+1。因此选取基准调度表如下：

很直观地可以看出式（9）～（13）可实现对P1最优化求解，最优目标值等于令Omax是具有最大时间复杂度基数的活跃项目集，则总的状态数量为，离开状态的最大弧数（机会弧或决策弧）等于max{n2|Omax|,|S|}。则上述模型算法的计算复杂度为对比算法中，文献[14]算法的计算复杂度为文献[15]算法的计算复杂度为，单纯从算法计算复杂度上看，本文算法与文献[14]和文献[15]两种算法处于相同的数量级上，具体算法执行效率情况将在后续实验中进行验证。

3.4 基于随机模型图的调度优化

每个状态由一个节点表示：右侧节点代表可行的状态，左侧节点代表不可行的状态，中间节点代表“deadstates”，见图2所示。

Fig.2 Graph model representation of state transformation图2 状态变换的图模型表示

图2中，每个状态(s,t,O,v)上面显示的数字表示直到执行结束时所需的预期成本，对于可行状态其等于c1(s,t,O,v)，对于不可行状态其等于对于“deadstates”状态其等于M。每个状态的跃迁可用弧线表示：左侧弧线是决定弧，右侧弧线是机会弧。在每个机会弧上显示的数字是穿越机会弧的概率。在每个决策弧上显示的数字要么是基准调度的成本（离开起始节点的弧），要么是相关联的项目响应的成本（离开除起始节点以外的任何不可行状态的弧）。

在算法1中提出了基于池生成的项目调度优化程序，其对于给定的一组初始调度集输出一组优化的调度集。

算法1池生成程序

输入：初始调度的集合sinit。

输出：S。

在上述程序中，k1是要生成的调度表的确切数量。为了降低所提方法的计算复杂度，将参数k1限制在k1≤2 000。生成的调度表的数量过大会导致算法的计算复杂度过高，大量的运算浪费在调度表的生成和计算过程中，而调度表的生成数量过低，会导致算法在调度精度上出现下降，本文通过实验发现k1≤2 000是较为合适的参数选取方式。池生成程序中所使用的其他子程序为：rndSchedule(S)返回一个从所有已生成的调度表的集合S中随机选择的方案，rndRealization(β)返回一个随机实现。如果调度方案s在决策时刻t对于实现pl而变为不可行，则infeas(s,pl,t)返回true，否则infeas(s,pl,t)返回false。nextDM(s,t)返回调度表J(s,t)中s时刻后的下一决策时刻。子程序react(s,pl,t)对于决策时刻t的冲突反应，是一个强大的并行调度方案，详细计算过程及有关参数说明可见文献[10]所示，具体过程见算法2所示。

算法2react(s,pl,t)

输入：算法参数s,pl,t。

1.fort=0,1,…,Tdo

2.检查新的调度信息。

3.if不存在新的调度信息thenst=st-1并跳转t+1

4.else跳转过程6。

5.end for

6.forl=1,2,…,Ldo

8.存储可使得Δ(s0,st)最小化的调度策略st

9.end for

4 实验分析

4.1 算例分析

本节通过设定的算例对上述项目调度优化方案的选取过程进行描述。图3描述了项目活动的优先关系和资源需求。每个节点代表一个项目，每个弧代表一个优先关系，每个节点上面的数字显示该项目的资源需求。

Fig.3 Priority network of sample project图3 示例项目的优先级网络

Table 1 Duration distribution of project表1 项目持续时间分布

考虑上述设计的PR-策略Π可得如下解集的项目执行链表示：

式中，β1⋃β2⋃β3⋃β4⋃β5=β。在上述描述中每个执行链表示一组相同的链。例如，表示与所有实现pl∈β1相关联的链集。PR-策略Π选取s9作为基准调度策略。如果p1执行，则s9将不会变为不可行，因此不需要其他的项目执行响应。然而，如果执行，s9在时刻2变为不可行（见图4（a））。PR-策略Π执行从s9到s8的转换以解决不可行问题。与之关联的甘特图如图4所示。

Table 2 Scheduling set example表2 调度集示例

Fig.4 Gantt graph representation of association example图4 关联示例的甘特图表示

这个响应过程的成本计算如下：

对于β1中的项目调度实现pl，计算项目之间关联链的成本如下：f(Π1,l)=40×18=720。对于β1中的项目实现的累计概率等于类似的，可计算：（1）对于pl∈β2，f(Π1,l)=1 773；（2）对于pl∈β3，f(Π1,l)=773；（3）对于pl∈β4，f(Π1,l)=1 835；（4）对于pl∈β5，f(Π2,l)=835。同时可计算：，因此PR-策略Π1的期望混合成本为：

4.2 标准算例实验验证

为验证所提项目调度优化算法的性能，本文选取的实验对象是PSPLIB数据库，对应的问题算例模型的标号分别是J11、J13、J15、J17、J19、J21、J31。选取的每组问题算例模型的数量分别为650个，去除部分不可行算例，则总共选取的模型算例的数量是3 287个。

选取的仿真软件是Matlalb2012b，实验平台的硬件设置是：CPU-2300K 2.0 GHz，RAM 4 GB ddr4-2 400 GHz，系统为Win 10旗舰版。表3所示为本文算法独立执行200次进化迭代后所得到的计算数据与文献[14-15]两种算法的计算数据对比情况。

表3实验数据中选取收敛精度和计算时间作为评价指标，对比本文算法与选取的两种对比算法的性能优势。根据表3数据可知，本文算法在收敛精度上，偏差大小相对于设定值的百分比约为0.12%～1.36%之间，而文献[14]的精度指标分布在0.18%～2.25%之间，文献[15]的精度指标分布在0.16%～2.14%之间，本文算法在收敛精度上具有较为明显的优势。同时，在项目调度时间上，3种算法相差并不大，本文算法相对略优于文献[14]和文献[15]两种对比算法。

图5给出了选取的项目数量为30情况下，本文算法、文献[14]和文献[15]3种算法的计算甘特图分布情况。根据图5所示3种算法的计算甘特图分布情况可知，相对于文献[14]和文献[15]两种算法，本文算法得到的项目执行甘特图中，项目的总执行时间要显著优于文献[14]和文献[15]两种算法。这体现了本文算法在项目调度过程中的算法性能优势，其所执行的项目调度的方案更加合理。

Table 3 Comparison of results of example model表3 算例模型结果对比

Fig.5 Gantt graph distribution of 3 algorithms图5 3种算法的计算甘特图分布

4.3 真实案例实验验证

本实验中选取某制造厂的设备进行工序的调度，该实验算例中分别含有4台机床和零件，相关的时间参数情况见表4，设备运行网络图见图6所示。本实验中选取的基准参数是时间均值，利用本文算法进行最优方案的调度设计，调度过程中的4台机床加工顺序是π1=(O11,O13),π2=(O14,O12,O23,O21),π3=(O22,O33,O31)，π4=(O24)。考虑工件制造过程中的紧前关系，对所有的工序起止时间进行计算。

Table 4 Process,equipment and time estimation for remanufacturing workshop表4 某再制造车间工序、设备及时间估计

Fig.6 Pre-resource relationship made by workpiece图6 工件制造的资源紧前关系

对未进行压缩的100%和压缩一半的50%的工件制造的工序进行计算机模拟，仿真模拟次数设置为900次，实验结果见表5。实验结果显示，本文方法在制造厂的设备工序的调度上是有效的，能够降低工件的制造工期。

Table 5 Data table of simulation result表5 仿真结果数据表

5 结束语

本文提出了一种考虑主动/被动资源约束的随机图MDP的项目调度优化方法，主要创新点如下：（1）引入一种新的应对冲突的方法，实现了算法计算效率的提升。（2）将主动和被动项目调度问题作为一个单一的综合问题来制定，实现了资源的综合考虑。（3）设计了一种基于随机图的动态规划求解方法，对所建立的MDP模型进行优化。实验结果显示了所提方法的有效性。

在未来的研究中，主要研究方向有：（1）可能会考虑优化寻找到具有更低合并成本的解决方案。（2）寻找新的显性规则来消除项目不良响应的可能性，有助于减少模型所需的计算资源。（3）考虑对持续时间依赖的项目调度问题进行研究。（4）重点考虑反应性调度策略的选择对基线调度最优性影响的必要性。