基于SDVRPTW 模型的项目设备优化调度方法

饶卫振 ，刘锋 ，金淳，侯艳辉

（1.山东科技大学 经济管理学院，山东 青岛 266590；2.东北财经大学 管理科学与工程学院，辽宁 大连 116025；3.大连理工大学 系统工程研究所，辽宁 大连 116024）

资源约束下项目调度问题（Resource-Constrained Project Scheduling Problem，RCPSP）基于大型工程项目施工背景，需要将其细分为不同工序，并采用优化方法，基于各种有限资源数量以及项目工序先后次序要求科学确定工序的最早和最晚开工时间，以保证整个项目的按期完成、达到成本最小或者收益最大。

由于RCPSP的求解复杂性为NP-hard，并且在工程项目中具有广泛的应用[1]。国内外学者对该问题进行了研究，并且重点针对在现实工程中，工序完成时间经常不确切的情况，研究了随机[2]、模糊[3]或不确定[4]完成时间的RCPSP 问题。另外，有部分学者针对RCPSP 问题进行了优化方法方面的研究[5-6]。但现有RCPSP 的研究主要假设资源有限的情况下如何优化工期，并且假设各个工序对于资源的需求独立进行满足。然而，由于经济、社会和政治等外在因素的影响，一些大规模项目的各工程环节的开工和完工时间基本确定，而主要的问题是如何在工序中有效调度资源，以优化资源消耗量。本文研究大规模项目设备调度问题（Equipmentscheduling Problems on Large-scale Project，ESPLP），假设项目总工期和其中各工序最早及最晚开工时间已经确定，设备属于非消耗资源且数量有限。在该条件下，如何在各个工序之间合理调度这些设备，因此，确切地说，ESPLP 与RCPSP 具有类似的工程背景，但问题的约束条件与优化目标均具有明显区别。

ESPLP问题可以归结为需求可拆分、带时间窗的车辆路径问题（Split-Delivery Vehicle Routing Problem with Time Windows，SDVRPTW）。项目中的工序等价于待服务的客户、设备类似服务车辆，工序最早和最晚开工时间等价于时间窗，每个工序可先后接受多个设备，相当于客户需求可以拆分。

需求可拆分的车辆路径问题（Split-Delivery Vehicle Routing Problem，SDVRP）由Dror 等 提出[7]，他们发现，客户需求接受多辆车的服务有时能够节约成本，并针对该问题提出了求解的构建型算法[8]。随后，有学者研究了SDVRP 的下界[9-10]，以及求解该问题的算法，Archetti等对该问题从模型分析[11]、复杂度比较[12]和有效算法方面进行了较为全面的研究[13-15]。Frizzell等[16]在SDVRP 的基础上考虑了时间窗约束，研究了SDVRPTW，并提出了求解的构建型算法。针对SDVRPTW 问题，Desaulniers[17]研究了求解该问题的分支定界法；Archetti等[18]在Desaulniers的研究基础上，提出了分支定界算法的改进策略，进一步提高了该算法求解SDVRPTW 的性能。孟凡超等[19]研究了求解SDVRP问题的禁忌搜索算法。杨亚璪等[17]采用三阶段启发式算法求解该问题，并取得了较为满意的结果。刘旺盛等[21]证明了客户需求不宜拆分应满足的条件，并设计了符合解的特征的聚类算法。

通过分析以上研究发现：①SDVRPTW 问题中客户的时间窗是相互独立的；②车辆对每个客户服务的时间是提前设计的常量，与车辆的送货量无关；③当前鲜见将SDVRPTW 模型应用于项目设备优化调度的文献。本文研究项目设备调度优化问题，部分工序之间存在先后次序关系，紧前工序的实际开工时间会直接影响紧后工序的最早开工时间，因此，本问题中每个工序的最早开工时间并不是相互独立的；另外，工序中需求某种设备的量一般采用“辆（台）˙天”表示，即工序对设备的需求量与时间密切相关。本文基于SDVRPTW 模型和问题本身特征，构建了数学模型，并证明了项目设备最优调度方案应具备的特征，针对模型提出了求解该问题的远缘杂交遗传算法。最后，通过实际问题验证了本模型和算法的有效性。

1 问题定义与数学模型

1.1 问题定义

ESPLP问题定义：在属于相同项目或不同项目的n个工序中，均需要使用存在指定仓库的某种设备（使用完成后设备需要运回仓库），已知每个工序的最早开工时间ei与最晚开工时间li、持续时间ai及工序间的紧前关系矩阵Sn×n，当工序i是j的紧前工序时，sij=1，否则等于0（sij∈Sn×n），且每个工序对该设备的需求量为qi（台˙单位时间），且设在任意两工序i、j间调度设备的耗时和成本分别为tij和cij，如何在保证各工序需求得到完全满足的前提下，确定需要的设备数量以及分别在n个工序和仓库间服务的次序和持续时间，并使所有设备在项目工期T结束之前回到仓库，且总调度成本最低。

ESPLP问题的假设：

（1）调度的设备是工序使用的关键资源，如果设备没有到对应工序则不能开工。

（2）每个工序的设备需求可拆分，即可以调度多台设备供其使用。

（3）任意节点间的调度成本和调度耗时符合三角不等式。

SDVRPTW 问题：设有n＇个客户的需求量为，每个客户接受服务的时间窗为，现配送中心有载量为Q的若干车辆，设客户需求可以由多辆车满足，任意两客户间的车辆移动成本和耗时已知，问题的优化目标为车辆的总行驶成本最低。

项目设备调度问题与SDVRPTW 的相同点：①工序等价于客户；②仓库等价于配送中心；③设备等价于配送车辆；④工序最早开工时间与最晚开工时间，等价于客户接受服务的时间窗。

项目设备调度问题与SDVRPTW 的不同点：①工序间有紧前关联（只有紧前工序完工后，工序才能开工），而客户之间的时间窗是相互独立的；②设备满足工序需求表现为使用时间长度，而配送车辆满足客户需求表现为送货量。

由于本文研究的ESPLP问题与SDVRPTW 存在上述区别，故不能直接采用SDVRPTW 模型来解决本问题。

1.2 数学模型

数学模型符号：

N——工序节点集合｛1，2，…，n｝

υ——设备所在仓库节点0、n+1与工序节点集合，即｛0，n+1｝∪N

ai——工序i的持续时间，a0=an+1=0

ei——工序和仓库i的最早开工时间，其中，0≤i≤n+1，e0=en+1=0

T——项目总工期，且

li——工序和仓库i的最晚开工时间，其中，0≤i≤n+1，l0=ln+1=T

cij——设备由节点i调度至j的成本

qi——工序和仓库i的设备服务需求量（台˙单位时间），其中，q0=qn+1=0

bef（i）——为工序i紧前工序集合

Sn×n——sij∈Sn×n表示工序i、j间的紧前关系，当工序i是j的紧前工序时，sij=1；否则，sij=0

tij——设备由节点i调度至j的耗时

A——A∩V×V，（ij）∈A表示节点i～j可行，即ei+min｛ai，qj｝+tij≤lj

A（N）——A∩N×N，其中N×N为任意两工序间的弧集合

A*（N）——A*（N）⊆A（N），如果（i，j）∈A*（N）必定（j，i）∉A*（N），且（i，j）∈A*（N）的弧为

ku——｝

A-（u）——

P（N）——N中元素个数及需求车辆数均大于2的子集的集合

V+（i）——为在弧集合A中由节点i可直接调度的目的地节点集合

F——设备集合

H——调度方案中使用设备的数量

数学模型目标函数为：

目标函数式（1）表示最小化调度设备的总成本；约束条件式（2）表示满足所有工序的需求量；式（3）约束了服务每个工序的最少设备数量；式（4）用于计算当前调度方案用到的设备数量；式（5）表示调度方案中使用设备数量的取值范围；式（6）是Kohl[22]在VRPTW 模型研究中证明的k-path不等式，表示服务工序数量和最少需求设备数量均大于等于2的任意工序集u，应满足的不等式。

约束条件式（7）～（9）约束了调度方案的设备服务路径结构，每台设备服务的路径均由节点0出发，经过若干工序节点后回到节点n+1，式（7）表示任意设备开始只能调度至某个工序中；式（8）表示任意工序调度进来和调度出去的设备数必须相等；式（9）表示所有设备最后均要回到仓库节点n+1。约束条件式（10）～（13）约束了设备调度至工序中使用时需要满足的时间窗，式（10）表示设备调度至目标工序到达时间必须早于或等于开始服务的时间；式（11）约束了任何设备到达目标工序的服务时间必须在最早开工时间与最晚开工时间范围内；式（12）表示任何设备的服务工序时间的累加和不超过项目总工期；式（13）约束了设备服务的时间长度不超过目标工序的持续时间；式（14）表示任何工序的开工时间应该晚于所有紧前工序的最早完工时间；式（15）表示本模型中的决策变量为0，1变量。

2 问题求解的难度分析

如前所述，本文研究的 ESPLP 类似于SDVRPTW，但也存在一定的区别。对于不带时间窗的SDVRP问题其求解复杂度Archetti[11]做了比较深入的分析和研究。SDVRP 的求解难度要高于VRP问 题[11-12]，SDVRPTW 是SDVRP 的 一 般 化，其求解难度更大[17-18，23]。在SDVRP中，Dror等证明了定理1和推论成立[7-8]。

定理1在SDVRP 和SDVRPTW 的最优解中，如果任意两节点间的车辆行驶成本和耗时符合三角不等式，则任意两配送车辆共同服务的客户数量至多为1个。

推论如果任意两节点间的车辆行驶成本和耗时符合三角不等式，则任意两配送车辆的行驶路线包括m个（m≥2）共同服务的客户，则一定可以找到一个共同服务客户为m-1个、且更优的可行配送方案。

Desaulniers[17]指出，定理1和推论在SDVRPTW 中同样适用。

如前所述，ESPLP 与SDVRPTW 存在两点区别：①工序间有紧前关联（只有紧前工序完工后，工序才能开工），而客户之间的时间窗是相互独立的；②设备满足工序需求表现为使用时间长度，而配送车辆满足客户需求表现为送货量。这导致本问题的工序时间窗为变量，且设备在工序的停留时间与工序需求量成正比，这也导致推论在本问题中不成立，即如定理2描述。

定理2如果任意两设备可行服务路线包括m个（m≥2）共同服务的工序，则不一定可以找到一个共同服务工序为m-1个、且更优的可行调度方案。

证明不失一般性，做如下假设：

（1）两设备分别用f1、f2表示。

（2）两设备服务共同工序为｛1，2，…，m｝。

（3）设备f1、f2服务路线经过的节点集合分别为V（f1）、V（f2）（包 括0 和n+1 节 点，显 然，，服务路线闭回路的弧集合用S（f1）、S（f2）表示。

（4）设备f1在共同服务工序｛1，2，…，m｝的服务时间有。

要证明定理2等价于证明减少1个共同服务工序后，通过调整调度方案能够同时使f1、f2服务方案可行（满足服务时间窗，且累计服务时间、调度时间和等待时间不高于项目总周期T），且总调度成本较原来更低。

设备f1、f2总服务调度 时间T1、T2可由下式计算：

现任选公共服务工序i，i∈｛1，2，…，m-1｝，令设备f1放弃服务该工序，设备f2服务工序i的时长由变为，并设工序i在原设备f1服务路线中之前的节点为i+之后的节点为i-。

显然，f1在取消1个服务工序后，到达节点i-的时间会提前Δt=ti+i+tii--ti+i-，由于耗时符合三角不等式，故必定有Δt≥0，即此时f1的服务路线可行；另外，由于调度成本也符合三角不等式，故取消工序i后，调度f1节约的成本为

然而设备f2服务工序i的时长由变为，当下式成立时，设备到达下一个服务节点j的时间将超过最晚开工时间lj，即

因此，定理2成立。

与SDVRPTW 相比，ESPLP问题的最优解结构不具规律，在求解过程中难以发现方案的显著缺陷。这导致ESPLP 问题与SDVRPTW 相比更加难以求解，并且至少也是NP-hard问题。

3 远缘杂交遗传算法

遗传算法是由Holland等在20世纪70年代提出的，现在已广泛应用于求解包括VRP 问题在内的各种优化问题。当前，已经有部分学者采用遗传算法求解了VRPTW 问题，并取得了良好的效果[24-27]。本文研究的 ESPLP 问题类似于SDVRPTW 问 题，SDVRPTW 是VRPTW 的 扩 展问题，并且针对遗传算法容易较早收敛的缺点，设计了远缘杂交遗传算法（Distance-cross Genetic Algorithm，DCGA）。

3.1 调度方案编码

本文研究的问题较SDVRPTW 问题更加难以求解，不仅需要确定设备服务不同工序的路线，而且要确定设备在不同工序中服务的时间。在此，分别采用2个组数表示上述信息，如图1所示，表示一个2台设备服务5个工序的调度方案，且设项目总周期为10时间单位。

图1 调度方案编码示意图

3.2 算法设计思想

传统GA算法经常过早收敛于质量一般的求解结果，本文基于遗传学中“父母基因互异，后代基因趋优”的思想设计了DCGA。即父代方案在交叉变异的过程中，不仅考虑父代方案的质量，并且考虑方案之间的结构差异，从而在进行父代方案两两分组过程中，将结构差异较大的方案之间进行交叉产生新方案。

因此，DCGA 算法与传统GA 的主要区别在于交叉变异父代解选择阶段，前者父代选择同时考虑了个体的结构差异和适应度值，而后者仅根据适应度值大小选择交叉变异的父代解。

3.3 DCGA算法步骤

（1）生成初始种群。采用快速贪婪算法[28]与插入算法[29]生成规模为NumofSolution（为偶数）的初始方案种群。

（2）计算适应度函数值。令NumIter=1（NumIter参数为目标函数连续未改进的迭代数），适应度评价函数为方案总成本的倒数。根据适应度函数计算种群中每个方案的适应度值。

（3）计算结构差异程度。计算种群中任意2个方案的结构差异程度值，计算公式如式（19）所示，可以得到NumofSolution×NumofSolution的差异程度矩阵数据。

（4）父代方案匹配。基于（3）计算的差异程度结果矩阵，采用文献[30]中的快速算法进行两两匹配，以最大化总差异程度值为目标。

（5）进行交叉变异。采用双交叉点操作，基于父代解匹配分组方案，采用PIX[31]和OX[32]法进行交叉得到下一代种群，并且以概率Pc进行变异。

（6）修复不可行方案。检查交叉后方案的可行性，对于不可行方案，采用插入法调整修复。

（7）优胜劣汰。为了保持种群规模，淘汰质量最差的NumofSolution/2方案，使种群大小保持为NumofSolution，计算当前最优解，如果没有改进，则NumIter=NumIter+1。

（8）终止条件判断。如果NumIter大于设定参数NumofSolution或运行时间达Tmax，符合终止条件，则转（2），否则转（9）。

（9）输出最优方案。输出种群中最优方案。

DCGA 算法的流程图如图2所示。

图2 DCGA 算法的流程图

量化任意2个可行方案差异程度的计算方法：

式中：IdeNum Arc（xi，xj）为方案xi、xj之间相同弧的数量；Num Arc（xi）为方案xi中总的弧数量，显然，按照式（19）计算的任意两方案之间的差异程度取值范围在[0，1]之间。

4 案例求解与分析

以某建筑集团公司在青岛工程项目调度挖掘机为例，其数据来源为作者实际调研取得。具体信息为，本项目共100多个工序，其中有25个工序涉及到使用挖掘机。25个工序开始施工地点和设备所在库区如图3所示（A 为位置标识）。由图3可见，25个工序和挖掘机所在仓库（调配中心，用0表示）的位置大概分布在3～5 km2的施工区域，为了确切表示其所在位置，以仓库所在地为原点建立一个直角坐标系，然后计算25个工序在此坐标系中的坐标位置，具体坐标信息及各工序相关数据如表1所示。项目计划所有挖掘工作应在20个工作日之内完成，即T=20。表1中各工序时间点表示结束时间，如工序1的最早开工时间e2=2，表示第2个工作日结束时间，即第3个工作日开始时间。

图3 项目及工序施工地所在位置

注意在表1中，当ei=li时，表示关键工序，即工序需要的设备必须在ei=li之前到达，如工序5、9、12均为关键工序；在非关键工序中，工序19是24的紧前工序，因此，当设备调度至工序19的时间t早于e19时，有

成立；当设备调度至工序19的时间t在e19～l19时，工序24的最早开工时间将变为e24=t+a19。

实际工作中，当前调度设备的方法为人工调度法，并且假设各工序之间的调度和装配检修时间、不同工序施工地点之间调度成本相同，如假设各工序之间调度和设备检修时间均为0.5天。人工调度方法步骤：①根据各工序最早开工时间和最晚开工时间的平均值（ei+li）/2，并根据（ei+li）/2+ai取值按升序方式将工序排序；②根据排序将工序安排至挖掘机，找到第1台挖掘机的服务路线；③不考虑已满足需求的工序，基于剩下的工序重复②，直至所有工序满足需求。

根据人工调度方法，本实例的调度方案需要8台挖掘机，服务工序顺序分别为：

挖掘机在每个工序的停留时间为需求量qi，其中工序2、25、14在工序的持续时间ai＜qi，因此，单台挖掘机无法满足其需求，工序2挖掘机2、3服务时间分别为2、1；工序25挖掘机5、7服务时间分别为2、0.5；工序14挖掘机6、8服务时间分别为1、1。

表1 包含25个工序的ESPLP实例相关数据

按照人工调度方法必定可以找到一个可行调度方案，使所有的工序均能够在要求时间内完成施工。但人工调度法简单假设任意工序之间调度耗时和成本相同是不合理的，本文基于实际调度中耗费的人力及根据施工地点之间距离信息，得到任意2个工序间调度1 台挖掘机的成本和耗时矩阵，如表2 所示，其中调度耗时包括设备的检修时间。

表2 包含25个工序的ESPLP实例的任意工序之间调度成本（下三角）和耗时（上三角）

表2中成本单位为元，耗时单位为工作日。按照表2，可以计算得到人工调度方法得到的总成本为16 310元。

基于本实例，采用本文提出的模型和DCGA 算法求解，其中DCGA 中的相关参数如表3所示。编程语言为 MatlabR 2012b，运行平台为CPU 为Inter（R）core（TM）2 Duo，内存为2.0 GB，主频为2.93 GHz。

表3 DCGA算法参数取值

求解得到的调度方案共需要4台挖掘机，其服务路线分别为：

其中工序2、25、14在工序的持续时间ai＜qi，因此，单台挖掘机无法满足其需求，工序2挖掘机1、2服务时间分别为1.5、1.5；工序25挖掘机3、4服务时间分别为1、1.5；工序14挖掘机3、4服务时间分别为1、1。根据表2调度成本矩阵计算得到总调度成本为6 960元，远低于人工调度方案的16 310元，其挖掘机服务路线如图4所示。

图4 DCGA 求解的调度方案

通过求解结果表明，采用本文提出的模型和算法得到的调度方案，与实践中人工调度方法相比能大幅度减少设备数量和总调度成本，充分利用设备资源。

为了验证本文设计的DCGA 算法步骤（4）中父代方案匹配策略的有效性，在此，分别采用标准DCGA 算法和在步骤（4）中采用随机匹配方式的DCGA（为了方便描述用DCGA-1 表示）求解本问题，两者求解的收敛过程如图5所示。

图5 DCGA 与DCGA-1收敛过程对比示意图

由图5 可知，虽然DCGA-1 收敛更快，但求解质量低于DCGA。因此，在遗传算法中选择父代方案进行交叉变异时，考虑父代方案结构差异能够提升遗传算法的求解质量，可以克服传统遗传算法过早收敛的缺陷。

由于当前国际公认的SDVRPTW 标准算例比较鲜见，为了进一步验证DCGA，本文采用DCGA（参数取值与表3 一致）求解了部分国际标准SDVRP算例，并与文献[11，33]中的算法求解结果进行了比较。

由求解结果发现，DCGA 的优化质量非常具有竞争力，求解20个算例中的15个算例结果优于文献[11，33]中的算法（表4中DCGA 求解最优算例结果加粗显示），且总体平均改进在5%左右。

表4 DCGA与文献[11，33]中算法求解结果对比

5 结论

在大型项目中经常涉及多个不同工序使用共同有限资源设备，资源设备在不同工序中的有效调度能够有效降低施工成本，提高设备利用率。本文将该设备调度问题ESPLP归结为类似SDVRPTW 的问题，并建立了数学模型，设计了DCGA 算法求解本问题，得到如下结论：

（1）ESPLP 也 是 NP-hard 问 题 并 且 与SDVRPTW 相比更加难以求解。

（2）ESPLP 问 题 的 最 优 解 与SDVRPTW 不同，两台设备服务的共同工序可以超过2。

（3）DCGA 算法能够有效求解ESPLP问题，通过求解实例发现，DCGA 得到的求解方案，与实际中的人工调度方法相比，能够大幅度节约使用的设备数量和总调度成本，并且求解SDVRP 标准算例的性能具有较强竞争力。