资源受限下平行工序顺序对优化的0-1规划模型

苏志雄，魏汉英，涂远芬

(1.南昌工程学院工商管理学院，江西 南昌 330099；2. 江西省水安全与可持续发展软科学研究基地，江西 南昌 330099)

1 引言

在工程项目实施过程中，资源限制广泛存在，甚至不可避免。很多现代项目管理问题就源于资源受限，其中最具代表性的包括资源约束下的应急管理问题、资源受限项目调度问题(resource-constrained project scheduling problem，简称RCPSP)等。其中前者重点考虑资源调度，石彪等[1]新近研究了多类突发事件并发或次生时，通过在线重构方式生成应急预案资源调度方案的方法；而后者重点考虑工序调度，要求在满足项目各工序间的紧前关系和资源约束的条件下，合理地安排工序执行的先后顺序，从而使项目工期最小化。本文主要针对RCPSP进行研究。

RCPSP是典型的组合优化问题，更是NP-hard[2]。我们可以将RCPSP用另一种方式描述，首先假设资源不受限，确定一个初始任务安排(例如可安排各工序都在其最早开始时间开始)及项目工期，然后再加入资源约束，从而调整各工序以满足资源约束，并使项目工期延迟最小。显然，此时的调整就是将原先相互独立的平行工序(即可以同时进行的工序)排列为相互关联的顺序工序(即只能前后进行的工序)，减少工序的重叠，从而降低相应时段内对资源的消耗量，满足资源约束。因此，从排序的视角看RCPSP，可等同于平行工序顺序优化问题，其基本情况包括将若干个平行工序调整为1条或多条顺序工序链，以及多个顺序工序对等。

根据工序情况的不同，RCPSP可分为多种类型，如确定型、不确定型(包括模糊型等)、工序工期不变型、以及工序工期可变型(包括多模式型和可分解型等)问题。不同类型问题的特点不同，求解时所需的理论和方法也各有不同，并且每类问题都具有很高的难度，其有效的解决均有助于更好地解决总体问题。本文针对的是确定型、且工序工期不变的RCPSP。根据现有文献，求解该问题的主要途经是数学建模和算法设计。模型是问题的数学描述，其性质和特点决定了求解效率、可行性和准确性等。目前用于描述RCPSP的数学模型主要包括整数规划模型[3-4]、鲁棒模型[5-6]、约束规划模型[7-8]、基于可变强度的模型[9]、以及时间索引模型[10]等。特别是，Bianco和Caramia[11]建立的新模型中，开发了3个与工序开始时间、工序结束时间、以及某指定时刻的工序数量相关联的新变量，使得该模型优于已知的多数数学模型。张立辉等[12]将项目调度的研究范围扩展到重复性项目，发现了重复性项目与传统项目在工序时差方面的区别和联系，提出了适用于重复性项目的新时差概念体系，进而建立了更精确的重复性项目调度模型。对于这些模型的求解算法，包括精确算法和启发式算法，其中精确算法主要以分支定界法[13]为代表。鉴于RCPSP的难度，对于大规模的问题，精确算法通常耗时巨大，因此，启发式算法成为重要途径。最新文献中，用于求解RCPSP的启发式算法主要包括遗传算法[14-15]、粒子群算法[16]、鱼群算法[17]、蚁群算法[18]、过滤器算法[19]、和声搜索算法[20]、以及熵算法[21]等。然而，启发式算法尚无法确定最优解，因此难以彻底解决RCPSP。

从排序的角度分析，求解RCPSP过程中，只有相互平行的工序才需要考虑将其调整为顺序进行。现有研究主要从全局视角入手，即对于任一工序，其他某工序只要和它是平行关系，就需考虑是否将它们排列为顺序工序。考虑到工程实践中，所需资源类型众多，很多情况下资源并非全部或全程受限，而是部分、局部、以及指定性的受限，特别是意外的资源受限情况，某些资源受限可能只影响部分工序，即需将部分平行工序调整为顺序工序。处理这样的情况可能与处理全局情况有显著差异，但在目前鲜有研究。因此，针对上述情况，本文从新的视角——局部视角入手，考虑将项目中指定的部分平行工序调整为相应的顺序工序，并使项目工期延迟量最小。这些问题虽然是局部性问题，但在工程项目实践中广泛存在，且求解难度同样很大，包括一些NP-hard问题。

本文重点研究其中一类具有代表性的问题——将项目中某2n个平行工序排列为对项目工期影响最小的n个顺序工序对。该问题也称为平行工序顺序对优化问题。例如，原计划安排4名员工完成4个平行且相似的工序，但实施时2人被临时调走，要求剩余的2人完成这4个工序；假设个人的能力和精力限制每人最多只能完成2个工序，因此需要考虑如何将这4个平行工序两两排列成2个顺序工序对，从而能使项目工期所受影响最小。该调度问题具有如下特征：(1)可行方案数为(2n!)/n!，随着n增加，可选方案呈阶乘急剧增加；(2)各平行工序都有大量前继工序和后继工序，因此调整时几乎会影响项目中的所有工序，可谓“牵一发而动全身”，更增加了求解难度。该问题可视作RCPSP的特殊子问题，因此可借助通用RCPSP模型进行表述和求解。然而，本文的目标是建立更为简单高效的数学模型。

本文针对该问题提出更具针对性的理论，主要借助网络计划技术中的关键路线法(critical path method，简称CPM[22-23])，通过分析CPM网络的新特性——时间参数与路线之间的关系[24-25]，利用时间参数提出了平行工序顺序化对项目工期影响的简化公式。该公式对问题的简化十分重要：虽然调度平行工序会影响其大量前继和后继工序，但该公式只用2个参数就量化了该调度与项目工期之间的关系，实现了对问题的显著化简。在此公式基础上，本文提出了该问题的简单纯0-1规划模型。相关文献显示，混合整数规划是描述项目调度问题的基本模型，多数确定型RCPSP模型以混合整数规划为主[26-27]。然而与其相比，0-1规划模型通常更为简单高效[28]，且本文的纯0-1规划模型是建立在该问题的化简公式基础上，因此在计算效率和准确性上具备优势。实验验证，运用该模型可以在极短的时间内求得较大规模问题(如数百个平行工序的顺序对优化)的最优解。该结论为进一步求解RCPSP提供了新的理论和途径。

2 问题描述

假设工程项目中工序之间只存在严格优先关系，即任何工序只能在其紧前工序结束后才能开始，可用CPM网络表示，并计算相应的时间参数(如项目工期等)[22]，如图1所示，图中符号ETi和LTi分别表示节点(i)的时间上限(earliest time)和下限(latest time)。如果某些工序之间没有任何优先关系，则称它们相互平行，即平行工序。在CPM网络中，平行工序不在同一条路线上。

假设项目中，已知某2n个平行工序(记为A1,A2,…,A2n)面临资源受限。具体表述为：初始计划是安排相应2n个资源(可重复利用的资源)，且每个工序只需要1个资源；然而，由于突发资源限制，使得可用资源比计划缺少一半，即只有n个资源能够用于完成这2n个工序，另外，1个资源1次只能用于完成1个工序，且最多能顺序完成2个工序；因此，需要将这2n个平行工序两两排列成n个顺序工序对，如Ai→Aj，i≠j。将平行工序调整为顺序工序后，很可能、甚至必然会导致项目工期延迟，因此，该调整的目标就是使项目工期的延迟量最小。

图1 CPM网络

图2 平行工序顺序对化调整后的网络

3 理论分析及建模

3.1 理论分析

工序的基本时间参数包括其最早开始时间(earliest start time，简称ES)、最早结束时间(earliest finish time，简称EF)、最迟开始时间(latest start time，简称LS)、以及最迟结束时间(earliest start time，简称LF)，本文主要使用EF和LS，可用CPM法计算[22]。将项目中某两平行工序A和B调整为顺序工序对A→B，可能导致项目工期延迟，其延迟量记为DAB。为便于表述，我们亦称DAB为工序对A→B的延迟量，并给出DAB的简单计算公式，如定理1所述：

定理1将项目中平行工序A和B调整为顺序工序对A→B，造成项目工期延迟量，即DAB为：

DAB=max{EFA-LSB,0}

(1)

(2)

DAB=0

(3)

所以：

(4)

根据CPM法可知[22]：

带入式(4)可得：

所以：

=EFA-LSB

DAB=max{EFA-LSB,0}

式(1)正确。证毕。

图3 经过A→B的新增路线

由定理1及公式(1)可知，虽然平行工序的顺序化过程在项目中的影响范围很广，改变了诸多其他工序的进程，但是对项目工期的影响却只由其两个参数决定，从而实现了问题的简化。

根据定理1，我们可以将其拓展，推导出将项目中某2n个平行工序调整为n个顺序工序对后，项目工期延迟量的计算方法，如推论1所示：

推论1 将2n个平行工序A1,A2,…,A2n调整为n个顺序工序对Ai→Aj，i,j=1,2,…,2n，i≠j造成的项目工期延迟量等于这n个工序对的延迟量DAiAj中的最大值，即maxDAiAj。

证明根据式(1)的证明过程，如果∃DAiAj>0，则：

即：

而若∃DAiAj=0，则：

=maxDAiAj

证毕。

3.2 纯0-1规划模型

定理1和推论1的公式简化了工程项目中平行工序顺序化与项目工期的量化关系。在此基础上，我们建立了将项目中某2n个平行工序调整为n个顺序工序对，并且对项目工期影响最小的0-1规划模型，过程如下：

(1)引入0-1决策变量，用于决定是否将这2n个平行工序中的某两个Ai和Aj排列成顺序工序对Ai→Aj，即：若yAiAj=1，表示将工序Ai和Aj调整为顺序工序对Ai→Aj；否则，yAiAj=0。

(2)考虑是否将平行工序Ai和Aj排列成顺序工序对Ai→Aj(亦可简写为AiAj)，以及排列后对项目工期的影响，根据定理1和0-1决策变量yAiAj的含义，可表示为yAiAj(EFAi-LSAj)。引入变量z，使其满足：

z≥yAiAj(EFAi-LSAj)，AiAj∈Ω

(5)

其中，Ω表示这2n个平行工序中的任意两个组成的顺序工序对的集合，且所有yAiAj=1的工序对中不能有相同的工序，即任一工序只能和另一工序组成一个顺序工序对。式(5)表示z≥∀DAiAj，AiAj∈Ω，即：

z≥maxDAiAj，AiAj∈Ω

从而可得：

minz=maxDAiAj，AiAj∈Ω(6)

根据推论1，minz表示将2n个平行工序调整为n对顺序工序对后，导致项目工期的推迟量，因此模型的目标函数是：

minz

(7)

而式(5)是其约束条件。

(3)约束条件式(5)中，AiAj和Ω均是不确定的。为了更加简便和明确，我们借助上述0-1变量yAiAj来表述。

令A*表示2n个平行工序的集合，要将这2n个平行工序调整为n对顺序工序对，各工序Ai∈A*只能和A*中所有剩余工序中的一个(记为Aj)排成顺序唯一的工序对(Ai→Aj或Aj→Ai)，即∀yAiAj和∀yAjAi(∀Aj∈A*)中有且只有一个变量等于1，因此可用如下约束表示：

(8)

基于该约束, 可以将式(5)改写如下：

z≥yAiAj(EFAi-LSAj)，Ai,Aj∈A*，i≠j

(9)

根据上述式(5)、(7)-(9)，该问题的完整模型如下：

minz

s.t.z≥yAiAj(EFAi-LSAj)，Ai,Aj∈A*，i≠j

yAiAj={0,1}

该调度问题可视为一类特殊的RCPSP，而其上述模型是纯0-1规划模型。与混合整数规划模型等相比，0-1规划模型的求解效率更高[28]，因此上述模型比RCPSP混合整数规划模型等通用模型更为简单有效。

4 实验分析

我们将上述0-1规划模型用MATLAB (R2015b)编程，在配置为Intel®Core (TM) i5-2450M CPN @ 2.50GHz，内存4.00 Gb RAM的电脑上运行，运用CPLEX MIN Solver (Version 12.6)求解。首先，运用该方法模拟求解将大型工程项目中某100个平行工序调整为50对顺序工序对, 并使项目工期延迟量最小的问题，共模拟60个案例，CPU运行时间平均为0.2605秒，最短为0.17秒，如图4所示。

图4 将100个平行工序调整为50对最优顺序工序对的实验结果

进一步地，我们逐步扩大该实验规模，运用该模型分别模拟求解了将工程项目中的某200、300、400和500个平行工序调整为对项目工期影响最小的100、150、200和250对平行工序对的问题，每个问题模拟60个案例，其结果如图5所示。表1总述了上述各问题的模拟运算结果。可以看出，即使对于500个平行工序规模的问题，运用该纯0-1规划模型也仅平均耗时10.66秒(最短耗时7.74)即可求得最优解，具有较高的求解效率。

表1 实验模拟结果

图5 将200, 300, 400, 500个平行工序调整为100, 150, 200, 250对最优顺序工序对的实验结果

5 结语

当工程项目受到预期之外的资源短缺时，需要考虑将原计划中的许多平行工序调整为顺序工序，而这样会导致项目工期延迟，因此需要考虑能使项目工期延迟最小的调度方案。该平行工序顺序优化问题是特殊的或局部型RCPSP，也是组合优化问题，而本文主要针对其代表性子问题之一——将工程项目中某2n个平行工序调整为n对顺序工序对，且对项目工期影响最小。该问题的可行方案数可达(2n!)/n!，因此要实现更有效的求解效果，需要新的更具针对性的理论和方法。

本文借助CPM网络解决该平行工序顺序优化问题，从路线角度分析了工序时间参数与该调度问题之间的关系。借助这一关系，可以仅用工序的两个参数量化“平行工序顺序化”对项目工期的影响，显著降低了求解难度。进一步地，建立了该问题的纯0-1规划模型，并通过实验模拟验证了该模型的效率。研究结果显示，本文所揭示的工序时间参数与项目工期之间的关系及规律是简化和求解平行工序顺序优化问题的关键。在未来的研究中，我们将以此为基础，进一步研究该类型项目调度问题的其他子问题，进而推进总问题的有效解决。