复杂时间约束的水利工程项目调度问题研究

张　松,陈华平,刘　建

(1.中国科学技术大学管理学院,安徽合肥230026; 2.淮河水利委员会治淮工程建设管理局,安徽 蚌埠233001)

复杂时间约束的水利工程项目调度问题研究

张松1,陈华平1,刘建2

(1.中国科学技术大学管理学院,安徽合肥230026; 2.淮河水利委员会治淮工程建设管理局,安徽 蚌埠233001)

水利工程项目的调度属于资源受限的项目调度问题,但现实中这类项目存在着一种复杂的时间约束,即项目中的某些活动在特定时间段内不允许执行.针对这类特殊约束,本文提出了一种新的资源受限项目调度扩展模型,设计了多优先规则的启发式算法进行求解.并在此基础上提出了一种混合遗传算法,构造了新的交叉算子同时结合精英保留和双对齐技术来改善解的质量.最后,用调整后的项目调度问题库(project scheduling problem library)大量实例验证了算法的有效性.

资源受限;项目调度;遗传算法;水利工程

1　引　言

水利工程建设项目通常具有周期长、任务多、资金和资源投入高等特点,对于水利工程项目的合理计划和科学调度比较困难.上世纪五十年代发展起来的传统的项目计划和调度方法,如甘特图、关键路径法(critical path method,CPM)、计划评审技术(program evaluation and review technique,PERT)都曾在水利工程项目中获得广泛的应用.然而,随着项目规模的扩大、投入资源种类的增多以及工艺流程的复杂化,对水利工程项目的计划和调度越来越困难,这时管理者更多依赖于其个人经验和人际协调,往往会导致调度安排不合理并带来巨大的经济和社会损失.因此研究水利工程项目的科学调度非常有必要.水利工程项目的调度属于资源受限的项目调度问题(resource constraint project problem,RCPSP).RCPSP问题是管理领域近几十年来研究的热点,其基本模型是要求在满足项目内部各任务之间的时序约束和资源约束的同时,优化项目的总工期.作为一类组合优化问题,很多学者从各个角度进行了总结,详细综述参见文献[1-6].

针对RCPSP问题在现实生活中的应用,学者们已经探索了很多领域,比如Bomsdorf等[7]研究了电影拍摄中的拍摄调度问题;Lorenzoni等[8]讨论了港口中船只在规定时间限制下的进港操作;Vanhoucke[9]介绍了项目调度中跟质量相关的时间槽约束,并以一个生物技术研发项目调度为例,提出了一种精确求解算法解决了之前提出的时间槽约束.然而,水利工程项目调度又不同于传统的RCPSP问题,主要体现在项目的特殊时间约束方面.关于时间约束的RCPSP调度模型最普遍的是RCPSP/max模型,研究的是活动之间最小/最大时间延迟问题,Neumann等[10]进行了详细的综述.在此之前,有些学者从项目管理中活动网络关键路径分析的角度Chen[11]提出了time-window和time-schedule两种特殊的时间约束.time-window约束中有些活动必须在一个时间窗口内开始,time-schedule约束中有些活动必须在预先设定的时刻表中的一些时间点开始,比如列车时刻表.Zhan和Franck等从项目计划的角度考虑到了工作日和非工作日的区别,分别研究了活动的日历约束[12,13],并把活动区分为可中断活动和不可中断活动,但在非工作日,所有活动都不能进行.类似的Yang[14]提出了另外一种time-swtich约束,该约束假设活动只能开始于周期性的指定时间间隔内.Drexl 等[15]在介绍新的问题实例生成器的构建过程中提出了一种新的“forbidden periods”约束,以排课为例,相同的课不应该被间隔成两段分别排在第一天的结束和第二天开始的时间,因此为每个活动都指定了一个最早/最晚结束时间.程序[16]在time-window的基础上提出了预约时间窗口约束模型,现实中有些活动必须在预约时间段内开始并完成,针对这类问题作者给出了一种混合智能算法.

已存在的时间约束关系大部分是关于项目中任务个体之间的各种相对时间限制,而实际应用中既存在任务之间的相对时间约束又存在对于项目整体的时间约束,例如堤防和河道建设,建设工期常常超过一年于是存在安全度汛的问题.项目中有些活动不受汛期影响可以安排在汛期进行,有些活动则必须考虑汛期的影响重新安排.汛期就是一种特殊时间段,在该特殊时间段内某些活动不能够进行而某些活动可以进行,这样才能更好地确保项目的安全和工期及提高资源的利用率.这类特殊时间约束的项目调度在其他工程建设中也比较常见,称之为“禁止时间窗口”约束.Blazewicz等[17]已经证明了RCPSP问题是NP-hard问题,有“禁止时间窗口”约束的项目调度进一步增加了问题的复杂性和求解难度.

2　问题描述

经典的RCPSP问题描述如下:一个项目由J个活动组成,活动j=1和j=J分别表示项目开始和结束的两个虚拟活动,虚拟活动的处理时间和资源需求都为零.J+表示所有活动的集合.每个活动的处理时间为dj.活动j的开始时间为sj,完成时间为cj,显然有sj+dj≤cj.假定活动一旦开始就不能中断.活动之间存在着时序关系,用Pred(j)表示活动j的紧前活动集合,即活动j必须在Pred(j)集合中所有活动结束之后才能开始,用Succ(j)表示活动j的后继活动集合,即集合Succ(j)中所有的活动都必须在活动j结束之后才能开始.项目涉及K种可更新资源,其中第k种资源每个周期的容量为Rk.活动j在执行时对资源k的需求量为rk,活动在任一时刻对资源的需求量不能超过该资源的容量.所有的参数默认为非负整数.RCPSP问题的优化目标是在同时满足活动之间的时序约束和项目资源约束的前提下,最小化项目的完成时间(makespan).

如前所述,水利工程项目的调度具有“禁止时间窗口”约束,在禁止时间窗口内,有些活动无法进行,因此这些特殊活动的调度就需要提前或者推迟.如果不在该时间段内,则这些特殊活动的调度跟普通活动一样就不再受影响.以一个项目示例来进一步表述这一问题.图1表示一个由21个活动(包括两个虚拟活动)组成的项目,假设项目只使用一种资源R,资源数量为4.方框表示的活动是特殊活动,特殊活动集合为{2,7,11,15,18,19}.假设特殊时间段为[5,16].图2是一个调度计划.因为活动2是特殊活动受到特殊时间段的影响,因此在时刻15不能立即开始,这段时间就造成了人员和资金等的极大浪费.图3显示的调度计划在特殊时间段排除了特殊活动的影响,因此相对就能够获得比较好的工期.

图1　项目示例图Fig.1　Sample project

图2　调度计划1Fig.2　Schedule 1

图3　调度计划2Fig.3　Schedule 2

进一步扩展,假设由于天气或者技术等原因,项目中每个活动都具有各自的“禁止时间窗口”,其对应的特殊时间段记为[STi1,STi2],特殊活动集合记为U+,U+⊆J+,则考虑特殊时间和特殊活动约束的RCPSP模型整理如下.其中式(1)表示目标函数为最小化项目的工期;式(2)表示活动之间的时序约束;式(3)表示项目中的资源约束; 式(4)表示特殊的时间约束,特殊活动必须在特殊时间段开始之前完成或者在特殊时间段结束之后才能开始,如果特殊活动集合U+=Ø,则此问题就退化为经典的RCPSP问题,如果所有活动的特殊时间段都一致,则可以转换为活动的日历约束[13]问题.模型中的符号说明整理见表1.

表1　模型中的符号说明Table 1　The parameters used in model

3　求解算法

求解此类特殊时间约束的项目调度问题,难点在于如何处理跟特殊时间段相关的项目活动,本文提出了多优先规则的启发式算法,在此基础上提出了一种新的混合遗传算法来进一步改善解的质量.

3.1多优先规则的启发式算法

启发式算法在解决RCPSP问题中具有广泛的应用,因为算法求解速度快,尤其适用大规模的计算;他们是很多高效率的元启发算法的重要组成部分;算法逻辑直观且易于理解,为大多数商业项目计划和调度软件所采用来获得良好的可行解.通常基于优先规则的启发式调度算法主要由两部分组成,即进度生成机制和优先规则[18].进度生成机制可细分为以活动为阶段变量的串行进度生成机制和以时间为阶段变量的并行进度生成机制.多优先规则法多次使用进度生成机制,每次选用不同的优先规则,最后选择其中的最优解作为最终的调度方案.解决经典的RCPSP问题的优先规则对于本问题具有不适应性必须对其进行调整,调整的主要思路是要结合特殊时间段和特殊活动的约束,在使用优先规则选择活动时,如果在备选活动中有特殊活动且特殊活动能够在特殊时间段开始前完成则优先选择特殊活动.如果备选活动中有两个及以上的特殊活动且这些特殊活动都能够在特殊时间段开始前完成则优先选择活动序号最小的特殊活动(tie-breaker).

本文采用的进度机制和优先规则的组合如表2所示.

表2　调度生成机制和所用优先规则Table 2　The schedule generation scheme and priority rules

3.2混合遗传算法

Hartmann[19]在1998年提出的解决RCPSP问题的遗传算法被证明是非常有效的,本文在其基础上针对新问题的特点设计了禁止时间窗口交叉算子,引入了双对齐技术和精英保留策略来提高求解质量,构建了一个混合遗传算法.接下来,先简单介绍混合遗传算法的基本流程,然后详细介绍混合遗传算法的各要素.混合遗传算法的步骤如下.

步骤1进行初始化:种群规模为popsize,迭代代数为Gen,变异概率为Pm;

步骤2生成初始种群pop;

步骤3使用双对齐技术调整种群中的染色体;

步骤4计算个体的适应值;

步骤5选择父代染色体;

步骤6应用禁止时间窗口交叉算子;

步骤7进行变异操作;

步骤8产生新的种群.如果达到设定的迭代代数则算法结束,否则转向步骤3.

首先生成初始种群,种群规模为popsize值设定为一个偶数,迭代代数为Gen、变异概率为Pm.然后使用一个简单有效的局部搜索策略―双对齐技术调整种群中的染色体,详细的描述在第3.2.2节.接下来计算个体的适应值.随机的从父代种群中选择两个染色体应用禁止时间窗口交叉算子(第3.2.3节)产生两个新的个体.再对新个体进行变异操作.将新生成的个体加入种群则目前种群规模就变为了2xpopsize,最后根据适应值的大小将染色体进行排序,从中选择适应值较好的个体保存,使得种群规模恢复为popsize,产生了新的种群.重复进行以上步骤,直到达到设定的迭代代数Gen或者预定的CPU时间.

3.2.1初始种群的产生和适应值函数

算法采用紧前关系可行活动链表编码方式,用串行调度方案作为解码规则.与Hartmann遗传算法不同的地方在于解码的时候需要考虑“禁止时间窗口”的特殊时间约束,如果特殊活动的开始时间受到影响则推迟该活动的开始时间.初始种群一部分是随机生成,另一部分则是采用多优先规则启发式算法当中的比较好的规则产生的解.遗传算法使适应值高的个体具有较高的生存机会,因此需将极小化目标函数转化为适应值函数,适应值函数f(i)=Fmax-Si,其中Fmax为最近5代中个体对应的最大工期,Si是对个体i解码所得的总工期即目标函数值.

3.2.2双对齐技术

已有众多学者使用局部搜索策略作为算子改进了遗传算法获得了更好的解,本文使用双对齐技术作为局部改进算子来实现同样的目的.由于双对齐技术的简单、快速和有效,很适合应用于解决RCPSP问题. Valls等学者[20,21]对该方法进行了详细的介绍.在实现对齐方法之前,对相关的概念进行定义.

定义1一个积极调度(左积极调度)是指调度中没有一个活动能在不推迟其他活动或不违反约束的情况下提早开始.类似的,右积极调度是指一个调度,其中没有一个活动能在不提前其他活动,或者违反约束或者增加工期的情况下更晚结束.

定义2右齐(左齐)活动操作,给定一个调度S,右齐(左齐)一个活动j/=J(1),获得一个新调度S′,并且尽可能的大.即在其他活动开始时间不变的条件下,尽可能的推迟活动j的开始时间.

对一个调度方案的双对齐操作就是首先以活动的完成时间降序排列,然后对每个活动进行右齐操作,依次获得活动最晚可以完成的时间,即其后续任务中最早开始的时间之前且满足资源约束关系的最晚时间.然后在此基础上再对每个活动进行左齐操作,将活动按开始时间升序排列,逐个将活动安排在最早可以开始的满足时序和资源约束的时刻上开始.当所有任务都调度完毕以后,即可得到至少不差于原方案的调度计划.

3.2.3禁止时间窗口交叉算子

通过分析具有“禁止时间窗口”约束的RCPSP问题的调度方案,发现如果跟“禁止时间窗口”对应的特殊时间段没有安排活动,则该特殊时间段的资源利用率相对就比较低,反之,则说明特殊时间段都安排了活动,项目调度没有产生停顿的现象,更可能取得好的项目工期.于是借鉴Valls[21]中的尖峰交叉算子,本文提出了一种新的交叉算子,称之为禁止时间窗口交叉算子.详细描述如下.用S表示一个调度, [U1,U2]表示一个“禁止时间窗口”对应的特殊时间段,用SA(u)表示调度中在特殊时间段内运行的活动集合, 即SA(u)={i∈J+;[U1,U2[∩[si,ci[/=Ø}.调度方案S在特殊时间段内资源使用率(resource utilisation ratio, RUR)为

给定一个阈值δ,这里设定δ=0.7,如果RUR(u)≥δ,则说明调度方案S在特殊时间段内是高资源使用率.用λ表示在特殊时间段执行的活动列表,λ=(jp,jp+1,...,jq),此列表有可能为空.假设选择两个个体F, M作为父代,如果父代F,M中的特殊时间段资源使用率都不高于δ,则使用传统的一点交叉算子;如果F,M中任一特殊时间段的资源使用率高于δ,则使用两点交叉算子,交叉点分别为λ的开始和结束活动的位置.如图5所示.

图5　禁止时间窗口交叉示例Fig.5　Forbidden time windows crossover operator

禁止时间窗口交叉算子跟特殊时间段的资源利用率密切相关,如果父代中特殊时间段的资源利用率比较高则通过两点交叉将该特征保存到子代中;如果父代中特殊时间段的资源利用率没有达到阈值,则进行一点交叉操作增加解的多样性.

3.2.4变异和选择

活动链表中基因变异采用对换变异,随机选择两个基因进行对换,依变异概率交换其位置,如果交换后的活动序列不满足紧前关系约束,则恢复原来的位置.选择采用二元竞赛机制,精英保留策略[22]嵌入其中,以保证当前种群中一定数量的最优个体直接进入下一代种群.选择概率为

4　仿真测试

本文的算法均采用java实现,测试环境为Intel双核CPU主频3.4G,内存大小8G,操作系统为Windows7.

4.1项目实例的生成

经典RCPSP问题基本上都采用Kolisch等设计[23]的PSPLIB实例库来对算法进行测试,而本问题研究了新的扩展模型,原有的实例库不再适用,因此需要在PSPLIB实例库的基础上增加新的时间约束.PSPLIB实例库中的每个项目实例都记载了当前学者们用各种算法求得的项目完工最短工期,特殊时间段的大小随机设定为原实例库中最短工期的15%～25%,特殊时间段的起始位置在整个项目最短工期范围内随机生成,但不包含开始和结束的时刻.特殊活动随机生成不允许重复,特殊活动占整个项目活动数量的8%～15%,不包括开始和结束两个虚活动.活动数量为30、60、90、120的四类项目实例,对应生成的算例数量分别为480、480、480和600.

遗传算法中的各参数设置如下:变异概率Pm设定为0.05,popsize设定为活动数量,算法的终止条件为迭代次数Gen设置为200或者在连续50代内结果没有变化.

4.2算法结果及比较

首先将J120的一个实例分别用并行调度方案和WCS优先规则、串行调度方案和LST优先规则以及混合遗传算法进行求解,发现makespan值分别为209、288、186.分析调度方案,发现该实例的“禁止时间窗口”对应的特殊时间段比较长并且起始位置位于项目前段,特殊活动数量占整个项目活动数量的12%,启发式算法只能简单确定一个调度方案,目标解值的优劣非常随机,而混合遗传算法能够充分探索解空间,不断进行“优胜劣汰”,从而一步步逼近问题最优解.接下来针对所有J30、J60、J90和J120的项目实例进行求解,结果汇总如下表所示.表3和表4分别记录的是采用并行调度方案和串行调度方案多优先规则求解的情况,在活动数量是30、60、90的各480个项目实例和活动数量是120的600个项目实例中,统计了各个优先规则求出的解中是各优先规则求得的解中的最小值的次数以及所用的时间.表5、表6中记录了各个规则求取的所有算例makespan的平均值,最后一列是所有算例最好解的平均值.表7记录的是使用遗传算法的求解结果.

表3　多优先规则并行调度方案结果统计Table 3　Result of multi-priority rules parallel schedule

表3、表4中用粗体字显示的是7个优先规则中前两位的最好的结果,从统计数据可以看出并行调度方案中,优先规则WCS和LST的表现最好;在串行调度方案中,优先规则LST和LFT的表现最好.从表5、表6中可以看出使用多优先规则的并行调度方案比串行调度方案表现要好,尤其是并行调度方案中的优先规则WCS和LST表现最为突出.图6展示了遗传算法和并行调度方案多优先规则(PSPR)、串行调度方案多优先规则(SSPR)最好解的makespan平均值的对比.遗传算法在活动数量比较小的情况下并没有明显优势,随着活动数量的增加,遗传算法的表现要优于优先规则,但是遗传算法花费的时间要远远大于优先规则.

表4　多优先规则串行调度方案结果统计Table 4　Result of multi-priority rules serial schedule

表5　并行调度方案平均makespanTable 5　The parallel schedule mean makespan

表6　串行调度方案平均makespanTable 6　The serial schedule mean makespan

表7　遗传算法平均makespanTable 7　The genetic algorithm mean makespan

图6　遗传算法和启发式优先规则makespan对比Fig.6　Compare makespan between GA and priority rule

5　结束语

具有特殊时间和特殊活动约束的水利项目调度问题属于经典RCPSP问题的一类扩展,本文针对这类问题提出了多优先规则的启发式算法和一种改进的混合遗传算法进行求解.根据实验结果可以得出以下结论: 1)针对测试问题,多优先规则的并行调度方案要优于串行调度方案;2)针对测试问题,基于时间约束的优先规则LFT和LST以及WCS要明显优于其他优先规则;3)改进的遗传算法在求解大规模问题时表现很好,但是求解时间随着问题规模的增大变大并且远远大于启发式优先规则所用的时间;具有特殊时间约束的项目调度问题在实际应用中很普遍,如何结合问题实际开发更有效率的智能算法将是以后工作的研究方向.

[1]Tamás K.Project scheduling:A review of recent books.Operations Research Letters,2005,33(1):105–110.

[2]Kolisch R,Padman R.An integrated survey of deterministic project scheduling.Omega:The International Journal of Management Science,2001,29(3):249–272.

[3]Hartmann S,Briskorn D.A survey of variants and extensions of the resource-constrained project scheduling problem.European Journal of Operational Research,2010,207(1):1–14.

[4]Brucker P,Drexl A,Mohring R,et al.Resource-constrained project scheduling:Notation,classification,models,and methods. European Journal of Operational Research,1999,112(1):3–41.

[5]Odedairo B O,Oladokun V.Relevance and applicability of multi-objective resource constrained project scheduling problem:Review article.Engineering,Technology&Applied Science Research,2011,1(6):144–150.

[6]刘士新,王梦光,唐加福.资源受限工程调度问题的优化方法综述.控制与决策,2001,16(B11):647–651. Liu S X,Wang M G,Tang J F.The optimization algorithms for solving resource-constrained project scheduling problem:A review. Control and Decision,2001,16(B11):647–651.(in Chinese)

[7]Bomsdorf F,Derigs U.A model,heuristic procedure and decision support system for solving the movie shoot scheduling problem. OR Spectrum,2008,30(4):751–772.

[8]Lorenzoni L L,Ahonen H,Alvarenga A G.A multi-mode resource-constrained scheduling problem in the context of port operations. Computers&Industrial Engineering,2006,50(1/2):55–65.

[9]Vanhoucke M.Scheduling an R&D project with quality-dependent time slots//Computational Science and its Applications.Berlin: Springer,2006:621–630.

[10]Neumann K,Schwindt C,Zimmermann J.Resource-constrained project scheduling with time windows//Perspectives in modern project scheduling.New York:Springer,2006:375–407.

[11]Chen Y L,Rinks D,Tang K.Critical path in an activity network with time constraints.European Journal of Operational Research, 1997,100(1):122–133.

[12]Zhan J.Calendarization of time planning in MPM networks.Zeitschrift für Operations Research,1992,36(5):423–438.

[13]Franck B,Neumann K,Schwindt C.Project scheduling with calendars.OR Spektrum,2001,23(3):325–334.

[14]Yang H H,Chen Y L.Finding the critical path in an activity network with time-switch constraints.European Journal of Operational Research,2000,120(3):603–613.

[15]Drexl A,Nissen R,Patterson J H,et al.ProGen/πx:An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions.European Journal of Operational Research,2000,125(1):59–72.

[16]程序,吴澄.一种复杂项目调度问题的混合智能算法.计算机集成制造系统,2006,12(4):585–589. Chen X,Wu C.Hybrid algorithm for complex project scheduling.Computer Integrated Manufacturing Systems,2006,12(4):585–589.(in Chinese)

[17]Blazewicz J,Lenstra J K,Kan A H G R.Scheduling subject to resource constraints:Classification and complexity.Discrete Applied Mathematics,1983,5(1):11–24.

[18]Kolisch R.Serial and parallel resource-constrained project scheduling methods revisited:Theory and computation.European Journal of Operational Research,1996,90(2):320–333.

[19]Hartmann S.A competitive genetic algorithm for resource-constrained project scheduling.Naval Research Logistics,1998,45(7): 733–750.

[20]Valls V,Ballestin F,Quintanilla S.Justification and RCPSP:A technique that pays.European Journal of Operational Research,2005, 165(2):375–386.

[21]Valls V,Ballestín F,Quintanilla S.A hybrid genetic algorithm for the resource-constrained project scheduling problem.European Journal of Operational Research,2008,185(2):495–508.

[22]刘士新,王梦光,唐加福.一种求解资源受限工程调度问题的遗传算法.系统工程学报,2002,17(1):1–7. Liu S X,Wang M G,Tang J F.GA for solving resource-constrained project scheduling problem.Journal of Systems Engineering, 2002,17(1):1–7.(in Chinese)

[23]Kolisch R,Sprecher A.PSPLIB:A project scheduling problem library:OR software–ORSEP operations research software exchange program.European Journal of Operational Research,1997,96(1):205–216.

Research on the complicated time-constrained project scheduling in water conservancy

Zhang Song1,Chen Huaping1,Liu Jian2
(1.School of Management,University of Science and Technology,Hefei 230026,China; 2.Engineering Construction Management Bureau,Huaihe River Conservancy Commission,Bengbu 233001,China)

Water conservancy project scheduling is a resource-constrained project scheduling problem(RCPSP),which is usually limited by complicated time constraints and some activities cannot be executed within the predefined time period.To address this issue,a novel variant model of RCPSP is proposed and a multipriority rules heuristic approach is developed.Furthermore,a hybrid genetic algorithm is presented.And a new designed crossover operator is combined with the elitism strategy and double justification technique, which greatly improves the quality of the solution.Finally,computational experiments are conducted on randomly generated and modified instances based on the benchmark problem instance sets in a project scheduling problem library,and the results show the efficiency of the proposed approaches.

resource-constrained;project scheduling;genetic algorithm;water conservancy

TP273

A

1000-5781(2016)01-0135-10

10.13383/j.cnki.jse.2016.01.014

2013-11-27;

2014-08-25.

国家自然科学基金资助项目(71171184);水利部公益性行业科研专项资助项目(201001017).

张松(1980—),男,安徽宿州人,博士生,研究方向:项目调度、批调度、智能优化算法等,Email:eshine80@mail.ustc.edu.cn;

陈华平(1965—),男,江苏江阴人,教授,博士生导师,研究方向:信息系统、批调度、网络计算、高性能计算、智能计算及其应用等,Email:hpchen@ustc.edu.cn;

刘建(1961—),男,江苏徐州人,教授,研究方向:管理、水利工程建设等,Email:liujian3037@163.com.