基于计算实验的资源受限多项目调度策略优化

李迁，张怀明，丁翔

（南京大学a.工程管理学院；b.政府管理学院，南京 210093）

近年来，“标准化”、“工厂化”、“预制化”等建造模式在工程建设过程中被大力推广应用，它不仅能够保证工程质量和进度，也能促使业主与供应商之间建立更加紧密的协作关系。工程业主通过合同方式委托供应商生产工程材料或部件，并要求其按时、按质、按量供货；供应商针对不同工程业主订单建立各个不同的项目团队来组织生产材料或部件，并基于其资源和收益进行多项目资源调度。由于工程建设的不确定性，工程业主为了保证工程进度，往往采取一定激励策略来鼓励供应商为其优先安排生产，供应商在考虑不同订单最晚交货期及其总体资源约束等情况下，采用内部资源倾斜或外购资源来开展多项目资源调度，实现供应商的整体收益最大化。

资源受限项目调度（RCPSP）问题已经被证明是NP-hard问题[1]。许多研究用来计算该问题的下界，其中一些是基于线性规划的思想展开的，Carlier等[2]提出了一种高效的工具来解决资源受限项目调度问题，该工具是基于活动执行时间下界来确定完工时间。对于RCPSP问题可以展开若干问题的研究，其中模糊项目调度成本-时间的平衡问题是其中的研究热点，该问题的研究需要在最小化项目成本与最大化项目缩短时间之间进行平衡。Deblaere等[3]研究了多模式RCPSP 反应调度问题，并提出了一种精确式算法在多模式资源受限项目调度中应用。Leu等[4]研究发现，在资源调度过程中采取“自己完成、承包商完成及合作完成”3种任务模式下活动成本的差异，Chen等[5]指出，活动时间的减少与活动成本的增加这两者之间存在一定的线性关系，因此，将模糊项目调度的时间-成本平衡问题抽象为模糊线性规划问题。Ashtiani等[6]针对随机模糊资源受限项目调度问题提出了一种预处理的调度策略，并结合遗传算法提出两阶段算法。通过对其进行仿真实验发现，此种算法对于方差较大的问题明显优于其他算法。同时，也有学者针对资源调度方案质量开展鲁棒性问题研究，它是指调度方案对于在项目执行过程中因不可控制因素而造成的对各种资源需求突然增加的适应能力[7]。Van de Vonder等[8]分析了资源受限调度问题中的质量鲁棒性和方案鲁棒性之间的平衡关系。另外，也有部分学者针对RCPSP问题中的不同目标进行研究。刘振远等[9]在资源受限条件下，以活动成本为目标进行工程调度的研究，不仅只局限于传统的静态固定成本，还包括项目完工后的持有成本。Elmaghraby[10]提出了多执行模式的概念，每项任务在开始之前要从不同的模式中选择一种模式开始。刘士新等[11]探讨了多执行模式下资源受限工程建设项目调度问题的算法，设计了一种SA/GA 的混合算法，并通过对标准问题的测试取得了良好的效果[11]。

综上所述，现有关于RCPSP 的研究主要集中在作业任务调度设计、模糊项目调度设计、调度方案的鲁棒性以及资源受限项目调度算法设计等，缺乏基于工程项目多利益干系人之间交互行为对资源调度影响的研究。因此，本文将工程业主激励机制引入到供应商资源决策模型中，建立相应的资源受限多项目调度模型，通过分析工程业主、供应商以及供应商项目团队等主体之间的动态交互规则，研究不同情景下的工程业主激励策略对供应商资源调度方案的影响。

1 资源受限多项目调度模型设计

1.1 模型说明

假设某供应商同时有来自M个独立工程项目的订单同时开始生产，这M个项目使用供应商的共享资源R，各自的资源约束分别为（R1，R2，…，Rm），工期约束为（D1，D2，…，Dm）。这M个项目中每个项目内部有N个任务，这N个任务之间满足紧前活动关系，每个项目内部的N个活动之间不存在资源方面的约束。假设M个工程业主中的某一业主实施了激励措施，在没有实施激励前，供应商对该项目的投入成本为Ci，项目执行工期为Di，供应商项目团队得到的收益为，工程业主根据负责其项目生产的供应商项目团队努力水平α、投入S来进行项目激励，供应商根据激励S可以采取3种行为：①完全购买额外的市场资源进行补充；②通过倾斜内部资源优先分配给实施激励的项目；③购买外部资源和倾斜内部资源的策略共同使用。本文建立此情景下的数学模型：

式（1）表示当某工程业主实施激励措施后新的所有项目工期目标；式（2）表示实施激励后供应商的总收益最大化，ρ为购买额外资源的比例；式（3）表示当某项目实施激励后，其项目工期最小化；式（4）表示供应商通过完全倾斜内部资源来满足某个激励项目时的资源约束，其中，rij为供应商多个项目在实施过程中对某一资源的实际需求量，Ri为供应商拥有某一资源的数量，QRi为供应商对实施激励项目进行的资源倾斜，SRi/Ci为工程业主通过实施S激励所对应增加的供应商额外资源；式（5）表示供应商通过完全购买外部资源来满足某个激励项目时的资源约束；式（6）表示供应商通过购买外部资源和倾斜内部资源结合使用的方式来满足某个激励项目的资源约束条件；式（7）表示通过实施激励后，供应商新的资源约束条件；式（8）表示新的某项目任务时间变化；式（9）中，Δtij为通过增加额外资源投入，某项目任务所减少的时间；式（10）表示某项目工期约束。

1.2 主体动态目标

1.2.1供应商Agent设计 供应商在制定多项目调度决策时一般分为两个阶段进行：第1阶段，根据供应商内部资源的状态以及多个项目的工期资源约束情况，计算调度方案集合；然后，根据供应商的最小工期目标进行调度方案的筛选，选择出最符合执行的调度方案，交由供应商项目团队负责执行。第2阶段，在项目执行过程中或制定调度方案开始前，供应商分析工程业主对某一具体项目实施激励方案，并对其激励方案进行评估（包括激励强度和新的工期约束）。

供应商根据激励方案，优先通过对内部资源的调度来满足激励方案的约束，工程业主激励S可以直接转化为供应商的收益。这种行为不会增加供应商总的资源数量，但其会对其他项目的资源配置及工期产生直接影响，因此，供应商对于是否接受工程业主的激励措施，需要进行严格计算；如果通过购买部分或全部S的外部资源来满足激励项目的工期要求，则该行为会导致供应商的资源总量变大，对其他项目产生间接影响。同时，此种方式下供应商的收益会减少，供应商在进行决策时需要对如下两方面进行综合考量：

（1）完全通过内部资源调配满足激励要求。供应商收益和供应商资源总量分别为：

（2）通过购买一定量的外部资源满足激励要求。供应商新收益和供应商资源总量分别为：

1.2.2工程业主Agent设计 工程业主通过对激励措施来加快项目生产进度，并根据激励措施实施前后的项目进度以及供应商资源投入情况的比较分析，来决定是否在项目实施的某一阶段开展激励，如果工程业主通过评估认为激励措施取得了预期效果，则其在下一阶段实施激励的概率就会增大；反之，工程业主在下一阶段会降低激励实施的概率或停止进行激励措施。工程业主通过供应商项目团队的努力水平这一观测指标对项目激励的效果进行评估。

工程业主在项目执行过程中的某阶段实施S激励，供应商根据激励增加资源。根据上文假设，当供应商在某个项目的i阶段上增加的资源，该阶段的工期

因此，工程业主在进行评估时主要依据f（ri）（供应商实际再投入资源与业主给予激励后所期望资源倾斜的差值）、g（ri）（激励后期望工期与实际工期差值）进行决策，通过分析f（ri）、g（ri），可得供应商项目团队的实际努力水平与工程业主对其预期努力水平αi之间的关系，如表1所示。

表1 努力水平关系表

1.2.3供应商项目团队Agent设计 供应商项目团队是连接工程业主和供应商之间的桥梁，其在进行多项目之间的调度问题上具有关键作用。供应商项目团队在决策过程中主要分为两个阶段：第1阶段，针对自己所负责的项目，进行细致地分析和研究，将具体项目任务的工期以及所需要的资源情况上报给供应商，供应商根据所有项目的情况，进行资源统一分配；第2阶段，在项目实施过程中尽可能地付出努力水平α（期望努力水平），如果工程业主在项目Q阶段对其实施S的激励，供应商项目团队要将新的项目工期约束、所需要倾斜的资源数量以及所需要购买资源的情况报告供应商。供应商项目团队在项目执行过程中不断修正自身的努力水平，从而使得α与（实际水平）尽量保持一致。

1.3 主体交互规则

在供应商与工程业主之间的交互中，工程业主通过观测供应商项目团队对于项目的进展情况以及外部环境变化对产品生产提出新的要求，决定是否实施激励措施。当工程业主决定实施激励措施时，根据观测到供应商项目团队的努力水平制定S的激励。供应商根据其项目团队提供的项目资源约束，在所有项目之间进行资源调度。同时，当供应商决定接受激励方案时，其项目团队需要向供应商提供所需倾斜资源的额度来确保激励项目的实施。因此，供应商项目团队不仅是项目的执行者，更是供应商和工程业主之间信息传递的纽带。同时，供应商和工程业主需要根据供应商项目团队的数据进行正确的决策。供应商与工程业主之间的信息交互模式如图1所示。

图1 工程业主、供应商与项目团队主体交互规则

具本规则：

（1）工程业主根据项目具体情况，向供应商提供一定的激励措施来加快项目工期。

（2）供应商项目团队根据工程业主提出的激励机制，进行评估工期和资源约束情况，并反馈给其所在的供应商，制定相应的方案。

（3）供应商根据其项目团队提出的方案，决定资源配置模式（倾斜内部资源或购买外部资源）。

（4）供应商根据其项目团队的执行情况以及工程业主的激励情况，进行激励绩效的评估，并根据评估结果决定下一阶段的策略。

（5）供应商项目团队根据其供应商绩效评估的结果，调整自身的努力水平。

（6）工程业主根据供应商项目团队在激励机制下的努力表现水平，决定下一阶段的激励策略。

（7）重复（1）～（6），直到工程业主、供应商项目团队的努力水平以及供应商的绩效评估达到资源调度的动态平衡状态。

2 实验案例与结果分析

2.1 实验案例

某供应商同时承接了5个工程项目订单，由于这5个项目都属于同一类型，每个项目划分为10个阶段来完成，当项目执行过程中没有异常干扰时，可以得到这5 个项目中每个阶段关键资源使用情况以及阶段工期。同一项目在不同阶段的关键资源不同，但是不同项目处于同一阶段时所使用的资源相同，供应商将项目分别交给5 个项目团队负责。表2 项目（a，b，c，d）中，a、b、c表示某个阶段需要的3类资源数量，d表示此阶段所需要的工期。5个项目的具体工期约束为：项目1工期约束70天、项目2～5的工期约束为100天，针对上述5个项目，供应商在每个阶段的总资源约束情况如表2所示。

表2 项目不同阶段的资源使用、工期及供应商资源约束

2.2 计算实验算法设计

在项目工期计算过程中，主要是通过改进优化对齐技术算法，按照资源和工期约束的具体情况，进行动态设计，具体步骤如下：

（1）确定每一个项目的资源约束因子

每一个项目的工期约束因子

综合约束因子λi=αηi+βξi，α、β为工期和资源的平衡关系；

（2）设定算法循环n次停止；

（3）根据综合约束因子排序，在满足初始资源约束的条件下，产生初始解，生成集合A1；

（4）计算在步骤（1）初始解产生后，检查系统资源池的数据，根据最小资源约束性，生产集合E1；

（5）A1集合完成某个项目后，释放可用资源进入资源池，资源池更新，同时产生集合F1，并更新A1变为A2，更新E1为E2；

（6）检查Ei集合中的各个项目，是否达到最迟项目工期，若达到最迟项目工期，则进行逆向调度；否则，继续进行正向调度；

（7）检查Ei、Ai是否为空集；

（8）若为空集，则输出集合Fi，产生一种可行解，并计算此解下目标函数；若为非空，则返回（4）进行循环；

（9）随机产生初始解，返回（3）进行循环；

（10）输出n次计算结果，并从中得到最优解。

2.3 实验结果及分析

2.3.1初始最优调度方案根据项目的工期及

资源约束，通过对齐技术来计算多项目的资源调度，得到119种调度方案。根据工期最小化原则，本文初始最优调度方案如表3所示。

表3 初始最优调度方案

在最优调度方案的基础上，计算工程业主激励策略以及供应商资源分配策略。根据供应商项目团队的努力水平，通过对两种情景模式进行实验设计，分析这两种情景模式下工程业主激励策略对资源调度方案的影响，以及供应商采取不同资源分配方式下对项目调度安排的影响。

2.3.2情景1：努力水平一致下的激励实施效果情景假设：供应商项目团队在激励措施下的努力水平与未接受激励措施的努力水平一致，即αi，供应商通过倾斜内部资源的方式来满足激励的要求。图2（a）～（f）分别表示当有1～5个项目进行激励时，项目工期变化情况以及供应商收益随着激励实施的变化情况。

由图2可知，当只有一个或两个项目实施激励时，供应商能够通过内部资源重新配置来满足工程业主的激励要求，项目工期大幅缩短，同时满足其他工期的约束要求，供应商的收益有很大的提升；但是当有3个以上项目同时采取激励措施时，此时被激励项目的工期没有明显得到缩短，供应商的收益情况趋向于稳定。这说明，此时供应商通过内部资源调控手段使得资源利用率达到最大化。由此可见，当供应商在进行内部资源重新配置过程中，不同项目之间实施激励策略的顺序显著影响激励效果，并且存在一个资源瓶颈点，使得激励措施的效果明显减弱。在此情况下，供应商可以不再接受其他工程业主的激励方案。

2.3.3情景2：努力水平不一致下的激励实施效果情景假设：供应商项目团队在工程业主激励机制下的努力水平与未接受激励的努力水平不一致，当工程业主在实施激励策略时，供应商项目团队的努力水平、工期及供应商收益也会不断发生变化。根据前文分析可知，当有一个或两个项目进行激励时，供应商通过倾斜内部资源的方式能够达到激励约束的要求，在这种背景下，本文研究当努力水平不一致时，工程业主实施激励的效果。假设工程业主有4种激励方案，如表4所示的修正系数x/y，当项目团队实际努力水平小于正常期望的努力水平a时，给予其·y激励；反之，则给予·x。

通过对不同修正系数进行实验分析，图3、4分别所示为在不同修正系数下，项目1的工期及供应商的收益变化情况。当修正系数组合为0.7/1.3时，修正曲线与期望努力水平下的曲线重合度最高；当修正系数组合为0.9/1.1时，项目工期缩短情况最明显，但此情景下供应商激励收益最小。因此，当工程业主实施项目激励时，供应商需要平衡好项目工期最小化和收益最大化这两者关系，相应地，工程业主要根据供应商收益变化来制定最佳的修正系数组合。

图5、6模拟了工程业主在进行连续激励时，多个项目的工期变化及供应商收益变化的情况，当供应商接受两个项目同时进行激励时，供应商的总收益最大；当供应商同时接受5个项目进行激励时，因为通过外部资源采购而使得供应商资源总量最大，但是总收益却明显减少。在5个项目同时进行激励的过程中，当激励发生在第8阶段时，此时供应商收益达到最大。因此，供应商通过控制实施激励项目的数量与激励实施过程的节点，能够使得自身收益最大化。

图2 项目工期及激励实施变化情况示意图

表4 激励实施下的努力水平变化表

图3 一个项目动态激励工期变化

图4 一个项目动态激励供应商收益变化

图5 外部资源采购下项目工期变化

图6 外部资源采购下供应商收益变化

3 结语

工程项目“标准化”和“装配化”的实施过程是由工程业主、供应商以及供应商项目团队三方共同完成的，不同主体的利益诉求存在差异。工程业主主要目标是交付的材料或部件质量高和工期短；供应商主要目标是在成本最小的前提下，其收益最大；供应商项目团队主要目标是在最小努力水平下收益最大。本文将激励机制引入到对资源受限调度问题的研究中，构建了多项目调度模型；基于计算实验理论设计了工程业主、供应商和供应商项目团队的主体属性及相互之间的交互规则。通过对实验数据的计算，分析了工程业主提供激励措施下，供应商项目团队努力水平“一致”及“不一致”两种情景下，供应商资源配置方式、项目工期以及供应商收益等变化情况，这为工程业主设计有效激励措施以及供应商的资源调度方案决策提供如下参考意见：

（1）供应商在制定资源调度方案时，需要对多个项目进行评估：①需要评估工程业主对项目的重视程度，这一点关系到工程业主在项目执行过程中实施激励机制的可能性；②需要评估工程业主对项目所制定的标准，项目标准直接关系到供应商对选择项目资源种类以及数量等方面的决策。

（2）工程业主在实施激励之后，对于激励绩效的评估需要考虑两方面：①项目工期是否缩短；②供应商项目团队在项目实施过程中努力程度是否保持一致。因此，工程业主在进行项目控制过程中需要将结果控制和过程控制相结合，如定期开展考核及派驻专业人员到供应商现场监督项目团队执行。

（3）供应商项目团队作为供应商中实施项目的主体，在进行实施项目之前需要进行如下评估：①根据项目工期、项目实施标准等情况，结合过往项目实施经历，制定合理的努力水平值，确保能够满足项目的工期约束；②供应商项目团队在接受工程业主激励方案后，需保持其努力水平与工程业主的激励策略一致，确保项目团队在努力水平值最小的条件下获得较高的激励收益。