高铁工程多项目调度研究

张海波 / 中铁七局集团西安铁路工程公司

高铁工程多项目调度研究

张海波 / 中铁七局集团西安铁路工程公司

在当前信息化、专业化、精细化管理的形势下，高铁工程建设项目进一步规范化、标准化的要求下，为进一步实现高铁工程多项目调度优化，本文建立了多资源约束下高铁工程多项目调度问题的数学模型，并提出了一种基于遗传算法的求解方法。

高铁工程；多项目调度；遗传算法

1.高铁工程多项目调度问题模型

1.1 高铁工程多项目调度问题描述

高铁工程施工企业一般都是通过网络计划方式来做项目计划的，针对网络计划图中的多项目问题，本文通过增加虚拟开始/结束作业的方式[1]，将多个海工装备项目网络计划进行合并，形成一个虚拟的带作业工期和资源消耗量的特殊单代号网络图，在本文中， ni为第 i 个作业的作业编号，di表示第 i 个作业的工期，r1i、r2i表示第 i 个作业在单个工作日对 R1、R22 种资源的消耗量，S ，E 为合成项目的虚拟开始/结束作业，s1，e1、s2，e2分别为项目 1、2 的虚拟开始/结束作业，ds1，ds2、de1，de2为虚拟作业 s1，e1、s2，e2对应的工期。

在此基础上，为了建立多资源约束下多项目调度优化问题模型，进行如下假设:（1） 一旦启动项目中的作业，不得中断作业，必须持续到完工;（2）在工期使用范围内，资源供给能力为均匀分布; （3） 单位时间内各作业对某种资源的需求量之和必须小于该资源的供给上限; （4）除了共享资源外，项目之间相互独立。

1.2 高铁工程多项目调度问题模型建立

高铁工程多项目调度包含 m 个并行项目，共享 k 种可更新资源，其中第 k 种资源的供给上限为 Rk，第 i 个项目包含 ni+ 2 个作业，其中第 0 个和第ni+ 1 个作业为项目 i 的拟开始和结束作业，具有一定的持续时间但不消耗任何资源。第 i 个项目中的第 j 个作业记为 Aij，其工期为 dij，开始时间记为 Sij，对第 k 种资源的需求量为 rijk，用 Pij表示作业Aij的紧前作业集合，It表示第 t 个工作日正在进行的所有作业集合，则问题的数学模型可以描述为

公式（1）为目标函数，表示所有项目最短加权总工期，∂i表示第i个项目的权重，公式（2）指并行项目的权重系数之和必须为1；公式（3）为项目作业的紧前关系约束，一个作业开始前必须保证其所有紧前作业集中的作业均已完工；公式（4）为资源约束，单个工作日内所有作业对某一资源的需求量之和必须小于该资源的供给上限；公式（5）指作业对人以资源的需求都不得为负；公式（6）指第t个工作日正在进行的所有作业集合。

2.高铁工程多项目调度问题数学模型求解

2.1 算法设计

在低层和高层遗传算法的进化中，采用模拟退火处理后的Pc、Pm进行交叉和变异操作，对交叉和变异过的个体分别进行模拟退火操作，从而帮助种群跳出局部最优解。高层遗传算法每运行一代都进行终止判断，如果不满足终止条件，继续高层遗传算法，进化5代后，返回低层遗传算法进行新一轮的寻优。

2. 1.1 染色体编码。

本文采用作业列表的方式进行染色体编码，染色体表达式为: Vk= ［r1，r2，…，ri，…，rmn］，其中 mn为所有项目的总作业数，ri表示第 i 个作业。

2.1.2 适应度函数。

由于本文采用特殊方法进行种群的初始化以及交叉变异操作，不会产生非法染色体，所以在对个体的适应度评价时无需引入惩罚函数，本算法的适应度函数: f( s) = 1 /F( s) ，式中: F( s) 是个体 s的目标函数值，即所有项目工期的加权和。

2.1.3 约束条件处理。

高铁工程多项目调度问题的主要约束条件包括两个: 作业紧前关系约束以及资源约束[2]。采用常规的方法( 如惩罚函数法) 并不能很好的处理这两个约束条件，本文采用的染色体编码设计主要考虑作业的先后关系，而作业的开始时间以及资源消耗则是通过解码操作完成的，这样自然就将作业紧前关系约束和资源约束分开了，因此本文设计了以下策略来进行高铁工程多项目调度问题的约束条件处理:作业紧前关系约束: 在初始化种群时就考虑，使初始化时产生的个体都满足该约束条件，并采用特殊处理的交叉变异算子，避免不满足紧前关系约束个体的产生；资源约束:在解码操作时直接考虑资源约束，当加入新作业存在资源冲突时自动将该作业的开始时间延。

2.1.4 初始化种群.

本文在初始化种群的同时考虑紧前关系约束，使产生的个体都满足约束条件，具体的实施策略是:采用3 个一维数组 A1、A2、A3和 1 个二维数组B ，其中 A1是未完成作业集合，A2是可执行作业集合( 过渡数组) ，A3是已完成作业集合，二维数组B中的每一列是 A1中相应列作业对应的紧前作业集合，B 数组相当于是一个紧前关系约束条件数组，在整个循环过程中都不发生变化。

2.1.5 解码操作

本文在实例验证时发现，在解码过程中直接把资源约束条件考虑进去，比采用惩罚函数法更加方便有效．假设有 m 个并行项目，Ti表示项目 i 的工期，Sj表示作业 j 的开始时间，染色体 Vk=［r1，r2，…，ri，…，rmn］表示所得到的拓扑排序后的作业列表，对该染色体的解码操作如下：

1) 令 S1= 0，j = 1 ;

2) 当 j ≤ mn 时，j = j + 1 ，转 3) ，否则转 6) ;

3) Sj= max{ Sk+ dk} ( k ∈ Pj) ，转 4) ;

4) 判断各资源在作业 j 的持续时间内是否存在冲突，若存在则转5)，否则，转2) ;

5) Sj= Sj+ 1 ，转 4) ;

6) 返回所有作业的最早开始时间，结束。

求得各项目工期为：

2.1.6 遗传算子设计。

1) 选择算子 选择算子采用轮盘赌选择法，并采取精英保留策略。

可又有谁这么大本事，神不知鬼不觉地偷走这么多东西？这营业部四周有高达3米的围墙，上面还插了很多玻璃碎片，别说人，就是在院坝里寻食的黑眼麻雀都要抬高了脑袋才能飞过去。其次这仓库大门对着不到五米就是我家，再怎么说我不可能一点声响都听不到，就算我老了耳朵不中用，但正值壮年的藏獒莽子，绝对不会听不到，平时，除了营业部里的人，没几个人敢在莽子前出现。就算是那几个下货物的人认识莽子，可他们怎么可能会有仓库的钥匙，这仓库的钥匙只有我和丁主任有，而丁主任怎么可能干这监守自盗的事，难道……难道？别人以为是我干的？

2) 交叉算子 为了避免产生非法解，本文在一般单点交叉的基础上进行了一定的改进，具体运算过程如下: 在［1，mn］范围内随机生成一个整数p，将父染色体Xi和Xj的前p个基因互换得到子染色体Yi和Yj(现在的）Yi和Yj中存在重复作业，属于非法解)，再从 Xi中找出与 Yi的前 p 个基因不同的剩下 mn － p 个基因按在 Xi中的先后顺序替换掉子染色体 Yi的后 mn － p 个基因，同理从 Xj中找出剩下的mn － p 个基因将子染色体 Yj替换。

3) 变异算子。变异算子的目的是防止算法陷入局部最优解[3]，增加种群多样性，尤其是在进化后期，种群中的个体过于相似，仅通过交叉操作很难产生新个体，因此必须采用变异算子来引入新个体．

2.1.7 模拟退火操作。

1) 交叉和变异概率的模拟退火本文根据退火优化思想［9］，设计了具有自适应的 Pc、Pm。

2) 交叉和变异后个体的模拟退火

首先在交叉/变异后个体 Vi的邻域 N( Vi) 内随机选取一点Vi1( Vi1也是问题的一个可行解) ，随机生成［0，1］之间的数q，判 断 由 式 ( 13 ) 计 算 的Pt( T2) 是否大于q ，若大于则用 Vi1代替 Vi，否则保留 V。

2.2 高铁多项目调度问题算法步骤

2) 初始化种群

3) 将当前种群随机均分成 C 个子种群，对每个子种群独立运行各自模拟退火遗传算法( 低层遗传算法)。

4) 每个子种群独立进化5 代后，将 C 个遗传算法的结果种群记录到二维数组R［1 ～ C，1 ～ c］中(c = popsize / C ) 。同时，将 C 个子种群的平均适应度记录到数组A［1 ～ C］中。

5) 高层遗传算法保留若干最优个体后，运行 1代，判断结果是否满足终止条件，若满足，转 7) ，若不满足，转 6)。

6) 判断是否运行了 5代，是则转 3) ，否则转 5)。

7) 程序结束并输出结果。

3.结束语

本文针对高铁工程多项目调度建立了优化数学模型，提出了一种基于遗传算法的求解方法，并将模拟退火算法和遗传算法进行融合，对遗传算法进行分层，可有效求解大规模高铁工程多项目调度问题。

[1] 王凯，李原，张杰． 基于人工免疫算法的航空多项目资源均衡技术［J］． 计算机工程与应用，2008，44( 16) : 211-214．

[2] Van PETEGHEM V，VANHOUCKE M． A genetic algorithm for the preemptive and non-preemptive multi-mode resourceconstrained project scheduling problem ［J］． Euopean Journal of Operational Research，2010，201: 409-418．

[3]刘刚，曹勇，李华德．几种改进遗传算法的性能比较［J］．微计算机信息，2007，23( 10) : 190-192．