基于控制工序性质的LOB截止日期问题分析与算法

张立辉, 戴谷禹, 邹 鑫, 乞建勋

(1.华北电力大学 经济与管理学院,北京 102206; 2.华北电力大学 经济管理系,河北 保定 071003)

0 引言

重复性项目是指在工程的各个单元和工序之间不断重复进行施工的一类工程项目[1]，包括公路、管道、桥梁和高层建筑等，涵盖了绝大多数的工程建设项目。由于重复性项目建设周期长且投资总量大，有效的计划和调度对于该类项目的顺利建设具有十分重要的意义[2]。关键路线法(critical path method, CPM)虽然是最常用的项目调度工具[3]，但在处理重复性项目时却存在许多不足，例如无法保证工作连续性、无法调度多工作队、更新繁琐等[4,5]。因此，现有研究提出了一些更适用的调度方法，如平衡线法(LOB，Line of Balance)[6]、线性调度法(LSM，Linear Scheduling Method)[7]和重复性调度法(RSM，repetitive scheduling method)[8]等。其中LOB方法最为常用，该方法采用时间和位置两个坐标将重复性项目表述为一个二维图示，以便项目管理者对进度计划的实际控制。

截止日期问题是重复性项目调度研究中最受关注的问题之一，其旨在不超过给定截止日期前提下求得一个项目工作队雇佣总量最小的调度方案[9,10]。现有研究在LOB方法框架下设计了一系列有效的截止日期问题求解算法，如CPM/LOB[11]，RUSS[12]，ALISS[13]，HLOB[9]和SHLOB[9]。其中，CPM/LOB方法结合了CPM和LOB各自的特点，旨在快速生成一个满足截止日期约束的调度方案；RUSS和ALISS方法通过不断调整工序的工作队数量来生成有效的截止日期问题进度计划；HLOB和SHLOB方法则在搜索过程中增加了寻优策略。文献[10]通过模拟仿真比较了上述几种方法之间求解效果的差异。还有一些研究则将LOB截止日期问题建立为整数规划模型进行求解[9，14]。

上述研究中的方法大多为启发式方法，能够获得一个较优的调度方案，但通常不能得到精确的最优解。由于重复性项目往往为大型工程项目，一个准确的最优进度方案能够节省大量成本，而目前关于截止日期问题精确算法的研究仍然空缺。另外，上述研究缺少对截止日期问题性质的关注，在设计求解方法时未能充分利用问题的结构特征，导致算法求解效率和效果不够理想。

关键路线是项目调度的基础，许多调度优化方法都是以关键路线为基础设计的。为了区别于传统的关键路线，通常将能够决定重复性项目总工期的工序称为控制工序[7]。相对于关键工序，重复性项目中的控制工序具有一些独特的性质，例如一些控制工序工期延长但项目总工期反而缩短。为此，文献[15，16]等依据控制工序对项目总工期的影响规律，将控制工序分为正控制工序、逆控制工序和点控制工序三种类型。在控制工序性质的影响下，许多重复性项目调度优化问题能够表现出一定的规律性结构特征，如最短工期问题[17]、资源均衡问题[18]和网络分析问题[19]等，从而有助于制定更有效的调度策略。

基于上述研究背景，本文考虑从控制工序性质出发，在LOB方法框架下分析重复性项目截止日期问题的内在结构特征，并以此为依据设计高效的调度优化精确算法，最后通过案例分析验证理论方法的有效性。

1 基于LOB的截止日期问题模型

1.1 LOB表述

作为一种基于图形的调度方法，LOB通常采用如图1所示的二维平面来表述一个重复性项目的进度计划[2]。其中，横纵坐标分别代表单元和时间，工序则采用一个向右倾斜的四边形表示。同时，每一个工序又是由多个工期相同的单元组成，每个单元则由一个小矩形表示。以高层建筑项目为例，建筑的装修工作可视为一道工序，则每一层的装修工作可视为该工序的一个单元。

图1 LOB图示

执行速率 在重复性项目中，一个工序通常会同时雇佣多个工作队进行施工，为了保证工作队施工过程的连续，所有单元需按一定的顺序分配给工作队执行，工作队则需要在不同的单元之间轮转施工。对任意工序i，其执行速率ri与单元工期di以及雇佣的工作队数量xi应满足如下关系：

ri=xi/di

(1)

基于工序的执行速率，工序内各个单元的开始时间则由式(2)联系起来。

(2)

其中sij表示第i个工序在第j个单元的开始时间。

确定所有工序的工作队雇佣数量后，可根据工序间的优先关系构建完整的LOB进度计划。

1.2 截止日期问题模型

重复性项目的截止日期问题旨在满足截止日期的前提下求得一个工作队雇佣总量最小的调度方案。本文根据文献[14]对截止日期问题的描述，构建其数学优化模型。该问题的目标即为最小化项目工作队雇佣数量，如式(3)所示，其中m表示项目的工序数量。

(3)

优先关系约束保证了重复性项目的工序在施工过程中不会发生冲突，即一个工序的某一个单元完成后，该单元上的紧后工序才能开始。式(4)表述了这种优先关系约束，其中sik表示工序i在单元k上的开始时间，sjk表示工序i的紧后工序j在单元k上的开始时间。

sik+di≤sjk

(4)

截止日期约束确保项目在指定的截止日期Td内完工。由于重复性项目的总工期通常由最后一个单元的完成时间控制，因此，截止日期约束可如式(5)所示，其中n表示项目的单元数量。

smn+dm≤Td

(5)

通常情况下，重复性项目的建设存在资源约束限制，即每个工序雇佣的工作队数量应有上限。该约束如式(6)所示，其中upi表示工序i的工作队雇佣数量上限。

xi≤upi

(6)

2 截止日期问题性质

2.1 控制工序类型与性质

在CPM中，关键工序的性质都是相同的，即延长或缩短任意关键工序，项目总工期也会相应地发生延长或缩短。但在重复性项目，不同类型控制工序的工期变化对项目总工期的影响却并不相同。在文献[15]的基础上，本文考虑将控制工序分为正控制工序、逆控制工序、开始控制工序和结束控制工序四种类型。

图2(a)和图2(b)中的工序j分别代表了典型的正控制工序和逆控制工序，工序i和k则代表了工序j的紧前控制工序和紧后控制工序。正控制工序的特点是与其紧前控制工序的优先关系约束仅在第1个单元处严格成立，即sj1=fi1，其中sj1表示工序j在第1个单元处的开始时间，fi1表示工序i在第1个单元处的结束时间。同时，正控制工序与其紧后控制工序的优先关系仅在最后一个单元处严格成立，即fjn=skn。同样，逆控制工序的特点则是与其紧前控制工序的优先关系约束在最后一个单元处严格成立，即sjn=fin，与其紧后控制工序的优先关系在第一个单元处严格成立，即fj1=sk1。

图2 正控制工序和逆控制工序

文献[15]将工序工期变化对项目总工期没有影响的控制工序定义为点控制工序，本文根据优先关系的不同进一步将点控制工序分为开始控制工序与结束控制工序。其中，开始控制工序的特点是与其紧前控制工序和紧后控制工序的优先关系都在第一个单元处严格成立，即sj1=fi1且fj1=sk1，如图3(a)所示。结束控制工序的特点是与其紧前控制工序和紧后控制工序的优先关系都在最后一个单元处严格成立，即sjn=fin且fjn=skn，如图3(b)所示。

图3 开始控制工序和结束控制工序

根据上述各类控制工序的特点可以发现，优先关系严格成立的单元不变的前提下，在一定范围内改变控制工序的执行速率不会导致控制工序自身类型发生变化。其中，正控制工序的执行速率在[1/dj,ri]内变化不会导致自身转变为其他类型的控制工序，逆控制工序执行速率的变化区间为[ri,upj/dj]，开始控制工序执行速率的变化区间为[rk,ri]，结束控制工序执行速率的变化区间则为[ri,rk]。

2.2 工序性质与总工期关系

根据文献[15]，重复性项目的总工期可由式(7)计算。

(7)

其中Di表示工序i的工期，I1表示正控制工序集合，I2表示逆控制工序集合，I3表示开始控制工序集合，I4表示结束控制工序集合。

单个工序i的工期Di可由该工序的单元数和执行速率计算得到，如式(8)所示。

(8)

将式(8)带入式(7)中，可得到基于工序执行速率的重复性项目总工期公式，如式(9)所示。

(9)

控制工序的特点表明控制工序的执行速率在一定范围内变化时其自身类型不变，而项目总工期公式(9)则反映了控制工序执行速率与总工期之间的关系。结合二者可以得到关于控制工序执行速率与项目总工期关系的命题：

命题1若工序j为正控制工序，当工序执行速率rj在[1/dj,ri]内变化时，增加工序执行速率rj，项目总工期减少，减少工序执行速率rj，项目总工期的增加。

证明若工序j为正控制工序，由正控制工序性质，其执行速率rj在区间[1/dj,ri]内变化时不改变自身工序类型。由式(9)可知，执行速率在该区间内变化时，项目总工期随执行速率rj的增加而减少，随执行速率rj减少而增加，命题得证。

命题2若工序j为逆控制工序，当工序执行速率rj在[ri,upj/dj]内变化时，减少工序执行速率rj，项目总工期减少，增加工序执行速率rj，项目总工期增加。

命题3若工序j为开始控制工序，当工序执行速率rj在[rk,ri]内变化时，增加或减少工序执行速率rj，项目总工期不变。

命题4若工序j为结束控制工序，当工序执行速率rj在[ri,rk]内变化时，增加或减少工序执行速率rj，项目总工期不变。

命题2、3、4的证明方法同命题1。上述命题阐述了控制工序类型在保持不变的前提下，工序执行速率变化与项目总工期之间的关联，项目管理者可根据其中的规律更精确地控制重复性项目总工期。

2.3 问题性质

命题1～4建立了控制工序执行速率与项目总工期之间的联系，由于工序的执行速率是由雇佣的工作队数量和单元工期决定，因此上述命题本质上建立的是工作队雇佣数量与项目总工期之间的联系。由于截止日期问题的目标是求得一个工作队雇佣数量最少的进度计划，利用上述命题可得到最优的截止日期问题进度计划应满足如下几个条件。

条件2和3的证明方法同条件1。

上述三个条件揭示了截止日期问题的一些规律，其中，条件1利用了项目总工期公式中逆控制工序具有雇佣工作队数量和项目总工期同向变化的特点，即工作队雇佣数量减少项目总工期也减少。条件2和条件3则利用了开始控制工序和结束控制工序工作队雇佣数量在一定范围内变化不影响项目总工期的特点。这些性质对于实际工程项目的进度安排具有指导意义，项目管理者可以根据这些性质判断一个调度方案是否合理。同时，这些性质可以进一步为调度算法的设计提供依据。

3 分支限界算法设计

目前求解截止日期问题的方法主要集中于启发式算法。启发式算法通常能够得到一个较优的可行解，但重复性项目往往投资和建设规模较大，求得精确的最优调度方案对节约项目成本和资源具有非常重要的意义。分支限界算法是一种求解问题精确解的有效算法，其算法流程包括分支、限界和剪枝几个步骤。基于上述截止日期问题的性质，本文设计了一种具有针对性的分支限界算法实现对截止日期问题的精确求解。

3.1 分支策略

截止日期问题的解空间可由一个树型结构进行组织，每一层的结点分别对应一个工序的工作队雇佣数量情况，如图4所示。每个结点包含了相应的进度计划信息，包括工序编号，工序单元工期，工作数量等。分支限界算法从根结点出发，不断选择当前未分支的结点中目标下界最小的结点作为拓展结点进行分支，分支的数量由工序i的紧后工序j的工作队雇佣量上限决定。

图4 解空间图示

3.2 限界策略

为求得截止日期问题的一个下界，对工序工作队雇佣数量这一整数变量xi进行连续松弛，并不考虑其资源约束。在该情况下，显然当所有工序的执行速率都相同且总工期等于截止日期时，项目所需的工作队数量最少，此时工序的执行速率可由式(10)确定。

r=(m-1)/(Td-T1)

(10)

每个工序的工作队理想雇佣数量可由式(11)计算得到。

ci=diri=(m-1)di/(Td-T1)

(11)

(12)

将式(12)从整体考虑到局部，当某个结点对应的前j个工序的工作队雇佣数量已确定，则该结点的目标下界估计式如式(13)所示。

(13)

3.3 剪枝策略

剪枝策略是分支限界算法在搜索迭代过程中利用已知的信息判断结点是否可行或是否有可能成为最优解，若能够判断出不可行或不是最优解则删除该结点以加快算法搜索效率。利用本文提出的截止日期问题性质以及问题固有结构，可以设计出如下三个剪枝策略。

剪枝策略1：若某一节点的项目总工期估计下界fT超过截止日期Td，即fT>Td，应删除该结点。项目总工期的估计下界可由式(14)计算。

(14)

3.4 算法流程

基于上述分支策略、限界策略和剪枝策略，本文设计的针对截止日期问题求解的分支限界算法步骤流程如下所示：

步骤1建立初始结点并初始化参数；

步骤2选择下界最小的结点作为拓展结点；

步骤3当没有结点能够被选做拓展结点时，算法结束，得到最优解，否则，转步骤4；

步骤4对当前拓展结点进行分支，并计算子结点参数；

步骤5利用剪枝策略删除不满足条件结点；

步骤6标记该拓展结点为已拓展并转步骤2。

4 算例分析

4.1 计算效果分析

本文选用文献[9]中的案例验证算法计算效果的有效性。该项目为一高速公路项目，共包含24个工序和10个单元。利用本文提出的分支限界算法对该案例进行求解，并与CPM/LOB[11]，ALISS[13]和SHLOB[9]三种启发式算法的计算结果进行比较，其结果如表1所示。

表1 案例计算结果

由表1可知，相对于现有算法，本文提出的分支限界算法能够得到一个最优的调度方案。CPM/LOB方法虽然都能够得到一个工作队雇佣数量较少的调度方法，但是无法满足截止日期约束，是不可行的。ALISS能够生成一个满足截止日期的方案，但是需要雇佣更多的工作队，项目成本较高。SHLOB方法也得到了问题的最优解，但是该方法实际上引入了随机搜索机制，计算效果并不稳定。通过数值实验，使用SHLOB算法求解该案例1000次，仅5次能够得到最优解，计算效果并不十分理想。

4.2 计算效率分析

进一步分析本文提出的剪枝策略对算法计算效率的影响。依据剪枝策略的选择，考虑3个版本的分支限界算法。其中，算法1仅使用剪枝策略1，算法2使用剪枝策略1和2，算法3则使用所有剪枝策略。测试算例根据表2的参数设置随机生成。

表2 算例参数设置

本文采用Microsoft Visual C++实现算法程序，代码在一个主频为2.4GHz、内存为4G的个人计算机上运行。测试完所有案例后，采用如下3个指标衡量算法的计算效率：

(1)ACT：算法平均计算时间。

(2)MCT：算法最大计算时间。

(3)NUM：算法遍历的结点数量。

3个版本算法的计算结果如表3～5所示。从表中可以看出，所有算法的计算时间都随着案例规模的增加而增加。所有算法中，算法3无论是计算时长还是计算时间增长速度都显著优于算法1和算法2，即使用所有剪枝函数能够最大限度提高算法的计算效率。对比直接求解截止日期问题数学模型的计算效率，表6给出了采用Lingo优化求解器求解相同规模案例的计算时间，可见本文提出的分支限界算法计算效率显著优于Lingo求解器。

从遍历结点数量看，采用不同的剪枝策略会导致不同的遍历结果。以工序数量为30时为例，相对于算法1，算法2能够少遍历36.6%的结点，而相对于算法2，算法3则能够少遍历96.5%的结点。可见，剪枝函数能够有效的识别非最优解从而加快算法的搜索速率，但是不同的剪枝策略对算法搜索效率的提高程度有所不同。其中，剪枝策略3，即利用逆控制工序和结束控制工序性质的剪枝策略，对计算效率的提升最为显著。

表3 算法1计算效率

表4 算法2计算效率

表5 算法3计算效率

表6 Lingo计算效率

5 结论

本文从控制工序性质出发，对重复性项目截止日期问题进行分析。在确定不同类型控制工序稳定区间的基础上，将重复性项目总工期公式转换为基于执行速率的动态形式，建立工序执行速率与项目总工期的关系，并推得最优截止日期问题进度方案所需要满足的条件。项目管理人员可以利用这些性质检验一个调度方案是否可行且经济。进一步地，本文设计了一个具有针对性的分支限界算法，利用所提出的截止日期问题性质设计剪枝函数并整合到算法流程中。算例的计算结果表明本文提出的算法能够得到问题的精确最优解，且计算效率优于启发式算法以及模型求解器。

本文研究主要针对的是重复性项目截止日期问题，而对于其他类型的调度优化问题也可能存在类似的性质和特点，如费用优化问题和时间费用权衡问题等。因此，基于控制工序性质分析其他重复性项目调度优化问题的规律特征，并以此设计更有效的调度优化算法是未来非常具有潜力的研究方向。