广义优先关系下工序共用时差的计算与应用

苏志雄，顾辉明，魏汉英

(南昌工程学院 工商管理学院，江西 南昌 330099)

在现代化生产和管理中，日益激烈的时间竞争已成为最显著特征之一。时间早在上世纪80年代就被认为是竞争优势来源[1]，使得管理者越发重视时间在项目中的功能。机动时间是该竞争优势来源的具体化表现，主要用于避免和缓和潜在的项目延期，保护项目的重要工序。某工序的机动时间不仅刻画了该工序对于项目的重要性，而且还反映了项目的结构特性，为项目计划与进度提供指导依据。鉴于此，机动时间长期被视作项目优化的重要参数，多数项目管理方法，特别是项目调度，均以机动时间为基础[2-3]。工序机动时间的概念和算法是在网络计划技术(以Critical Path Method为代表，简称CPM[4])出现后被逐步提出并完善，其经典类型包括总时差，自由时差，安全时差，节点时差和干扰时差[2，5]。前三类时差主要界定单工序的活动范围，而后两类时差的实质则是不同工序的机动时间的相互重叠和互斥，体现了工序间的相互影响情况，是项目调度复杂程度的重要决定因素[3]。其中，工序节点时差概念的提出源自Activity-on-Arrow网络，反映的是该网络中前后相邻工序的共用节点的时差，但是这一时差概念在Activity-on-Node网络中却体现的不够直观，为化解这一矛盾，工序节点时差也被称为工序共用时差[2]。本文将使用这一概念名称。

广义优先关系[6](generalized precedence relations，简称GPRs)及其理论是对网络计划技术的拓展，较全面涵盖了现代工程项目中工序间的优先关系，包括各类型最小和最大时距。随着GPRs的提出，GPRs下的工序机动时间成为研究的必然。Elmaghraby[7]等提出目前通用的GPRs表示法，并较早提出GPRs下工序总时差，自由时差和安全时差的计算方法，适用于工序工期不变的情况。Valls和Lino[8]，杨冰[9]，Yakhchali和Ghodsypour[10]针对最小时距，而周梦和杜志达[11]针对最大时距，分别研究了工序时间参数的计算方法。在GPRs下工序机动时间研究过程中，一些学者发现，当工序的工期发生变动时，现有时差会出现诸多奇异现象。Elmaghraby[7]等发现GPRs 下一些关键工序的工期延长/缩短，反而导致总工期缩短/延长，即关键工序与总工期逆相关，还发现一些关键工序的工期变化不会影响总工期。与关键工序相对应，非关键工序很可能也具有类似的奇异现象。Qi[12]等发现一些工序随着工期的延长，其总时差反而增加，即“总时差越用越多”。苏志雄[13]等提出隐性时间参数的概念，一定程度上对奇异现象做出解释。阚芝南[14]等发现在GPRs网络中，工序间加入不同表现形式的同一时间约束，可能会产生不同的最大路长，可能导致奇异现象出现。受此启发，Su[15]等从GPRs网络路长的角度分析了上述GPRs下工序总时差奇异现象的起因和机理。最近，Su[16]发现了GPRs下机动时间隐性消耗现象等新奇异现象。

现有文献显示，目前对GPRs下工序机动时间计算方法的研究主要针对工序总时差，自由时差和安全时差，在机动时间特性研究上尤以总时差为重点对象。然而，对于GPRs下另两类经典类型时差——工序共用时差和干扰时差，尚缺乏充分研究。对工序共用时差和干扰时差的研究在经典CPM网络中有一定的体现，具有较明确的概念和计算方法[2]。Michael[17]等发现CPM箭线式网络中的虚箭线对工序共用时差和干扰时差会产生较大影响，进而研究了虚箭线最小化问题。Demeulemeester[3]等进一步研究了CPM网络中的虚箭线，提出了工序时间参数的修正方法，力求避免虚箭线对工序共用时差和干扰时差的影响。张立辉[18]等建立了工序共用时差与CPM网络路长间的关系，进而开发出工序共用时差对相关网络优化问题的新功能。针对工序共用时差和干扰时差所导致的工序间相互影响的规律，李星梅[19]等借助CPM网络研究了这两类时差的动态特征，揭示了单工序对其他工序的影响程度和范围。苏志雄[20]等发现由于工序共用时差和干扰时差的存在，项目的总体机动时间并非定值，而是会随着工序使用共用时差的不同而变化。GPRs网络和CPM网络差异很大，CPM网络中的节点可表示工序共用时差，但GPRs网络中的节点却只能表示工序总时差[8]，并且CPM网络中工序干扰时差的计算方法也同样不适用于GPRs网络。Li[21]等进一步分析了GPRs下工序间时距与工序工期的关系，两者的动态变化交叉影响者工序机动时间的值和可用范围。因此，需要新的思路和方法研究GPRs下的工序共用时差和干扰时差。

工序共用时差和干扰时差导致了项目中工序间的关系错综复杂，对任何具有这两类时差的工序的调整都可能改变其他大量工序的时间参数，可谓“牵一发而动全身”，是项目调度优化中最怕遇见且最难处理的情况之一。因此，要获得更优甚至最优的项目调度结果，提高项目管理效率，从工序共用时差和干扰时差入手有可能成为新的研究视角和突破口。本文重点针对GPRs下的工序共用时差，借助GPRs网络研究其概念、计算方法、以及特性，并应用于带有 GPRs的资源均衡中，主要包括：化简该问题模型；对模型的难易区域进行区分，使得在求解过程中具有针对性，进而提出更有效混合算法的新思路。

1 广义优先关系(GPRs)

1.1 GPRs包含的时距类型

GPRs包含的工序j和k之间时距类型如表1所示(sk和fk分别表示工序k的开始和结束时间)。

1.2 GPRs表示方法

Elmaghraby[7]等提出的GPRs箭线式网络是当前国际通用的GPRs表示法，特征如下：

(1)网络起点编号为(0)，终点编号为(2n+1)，n表示工序数；

(2)工序k的图示包含开始节点(2k-1)，结束节点(2k)，箭线(2k-1，2k)，(长度d2k-1，2k=dk)和箭线(2k，2k-1)，(长度d2k，2k-1=-dk)，dk为该工序的工期；

(3)工序j到k的时距用箭线(h，i)或(i，h)表示，h=2j-1，2j，i=2k-1，2k，其中，箭线(h，i)表示最小时距，其长度dhi=δ，箭线(i，h)表示最大时距，其长度dih=-δ。

1.3 GPRs下的现有工序时差

文献[7]针对工序工期不变的情况，提出了工序k的总时差TFk，自由时差FFk和安全时差SFk：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

2 GPRs下的工序共用时差

2.1 工序工期不变的情况

类似地，假设工序j和k之间存在其他类型优先关系(如图1(a)～(d)所示为工序间最小时距)，同样可以得出CFjk。若工序j和k之间存在多类型优先关系，包括最小时距(从工序j指向工序k的箭线)和最大时距(从工序k指向工序j的箭线)，则CFjk取决于这些箭线干扰时差中的最大者，即

(8)

前式为该情况的特例，因此式(8)是相邻工序共用时差的总公式。

由于工序k可能有多个相邻工序，且与各相邻工序的共用时差不同，为便于分析，给出工序k的统一共用时差，以工序间的共用时差最大值为基础。首先介绍紧前和紧后工序概念。GPRs网络中，如果有表示优先关系的箭线从工序j指向工序k，称工序j是工序k的紧前工序，工序j是工序k的紧后工序。

(1)工序k的前共用时差，记为CFk，表示该工序与其紧前工序的共用时差，

(9)

(10)

(3)工序k的总共用时差，记为CFk，表示该工序与所有相邻工序的共用时差，

(11)

图1 各类型最小时距

2.2 工序工期可延长的情况

根据式(4)～(7)，GPRs网络中，任意工序k的工期延长时，可能会出现以下现象：

(12)

(13)

根据式(8)～(11)算出工序j和k的各类共用时差CFjk、*CFk和CFk。

2.3 工序工期可缩短的情况

GPRs网络中工序k由箭线(2k-1，2k)和(2k，2k-1)组成，也可绘成图2，为避免混淆，记工序k在图2中为-k，其开始节点为(2k)，结束节点为(2k-1)。根据隐性时差和伪时差理论，若-dk增大，即工序k工期缩短，则对应工序-k可能出现隐性时差和伪时差，根据式(12)～(13)：

(14)

(15)

2.4 半岛工序和孤岛工序

*CFk=0

则称其为“孤岛工序”，在执行过程中不会与任何工序相互影响。孤岛工序的特点使其能够降低管理(特别是调度等)方面的难度，若项目中的孤岛工序越多，则该项目在处理调度等问题时难度可能越低。

图2 反向视角的各类型最小时距

3 应用分析

本文提出的GPRs下的新工序概念可为项目调度提供新思路和方法。结合节2.4可知，半岛工序和孤岛工序可为GPRs下工序对项目调度的复杂程度进行分级。例如，孤岛工序独立于其他工序，调整时所需考虑的因素最少；干扰工序是导致项目调度中工序关系错综复杂的主因，调整时所需考虑的因素最多。因此，根据工序类型的不同，可在项目中进行复杂程度划分，分别用具有对应特征和功能的算法进行处理，进而以此为基础进行算法综合，设计出新的混合算法，实现更好的求解效果。

minz

(16)

s.t.

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

上述模型中，式(19)～(26)表示工序间优先关系。GPRs下工序间优先关系数量远多于工序数量，若能鉴别删减冗余优先关系，可显著减小模型约束条件，实现模型简化。以图3为例，该网络所示项目的资源均衡问题。根据节2.1，计算工序共用时差，例如，根据式(8)计算工序2和8的共用时差CF2，8，

因此两工序没有共用时差，实际并无约束，可删去箭线(4，15)；依此类推，得图4所示网络，与图3相比，表示优先关系的箭线数量由32减少到6，即模型中优先关系约束条件减少81.25%。图4显示有较多半岛和孤岛工序，弱化了工序间相互影响，只有少数工序在资源均衡中会影响其他工序，降低了问题求解难度。

4 结论

工序机动时间是项目管理的重要优化参数。在基于CPM的项目中，工序机动时间包括总时差，自由时差，安全时差，共用时差和干扰时差。然而在带有GPRs的项目中，现有工序机动时间却只包括总时差，自由时差和安全时差。随着现代工程项目的规模扩大化和结构复杂化，工序间遍布GPRs。工序共用时差和干扰时差能够体现工序间相互影响的规律，若合理应用有助于减小项目复杂结构的影响，对于项目管理十分重要。本文重点研究GPRs下的工序共用时差。

GPRs的表示方法与经典CPM网络相比差异显著，GPRs下的工序时差难以直接借助CPM方法计算。本文根据工序共用时差和干扰时差的含义，以GPRs箭线式网络为工具，提出相应的概念和计算公式。通过分析上述公式及GPRs网络结构，发现具有独特性质的工序，并提出新的工序概念，如半岛工序和孤岛工序。这些工序的特性有助于GPRs下项目调度的更有效求解。本文研究了GPRs下的工序共用时差在资源均衡问题中的应用。工序共用时差可以实现资源均衡问题的简化，主要体现在能删减冗余优先关系，减小资源均衡模型的规模。