曾彪, 刘欣

(上海交通大学安泰经济及管理学院, 上海 200030)

基于遗传算法的项目管理优化仿真研究

曾彪, 刘欣

(上海交通大学安泰经济及管理学院, 上海 200030)

传统的项目进度一维优化扩展至有偏好的二维目标（进度、成本）优化, 同时将成本优化目标分解为项目成本大小以及资源均衡度从而构成三维目标优化, 将无资源约束的环境扩展至资源约束下的复杂环境, 将局部搜索优化领域扩展至全局范围内的优化. 在内容上, 先对项目的单目标优化管理理论进行详尽研究并指出其现实的局限性, 同时提出了智能启化式方法-遗传算法在资源约束下项目管理优化方面的优势. 在此基础上本文构建了基于三维目标偏好的项目管理优化仿真模型, 解决了项目管理优化理论中最为重要的两大问题：资源约束下的项目进度优化以及资源约束下的三维目标（项目进度、项目成本以及资源均衡度）的优化问题. 为了验证此模型对以上问题的有效性, 本文应用Matlab仿真技术进行仿真模拟并与传统方法做比较, 从结果可以看出遗传算法能够更好的解决此类问题.

项目管理; 三维目标优化; 遗传算法; 三维偏好

1引言

随着经济全球化的发展, 各个行业的竞争环境已经从相对稳定型转变成了动态多变型. 新技术的发展以及动态的资源供给要求组织在项目范畴内逐渐实行矩阵式管理以做到快速决策, 利用有限的资源谋得最优绩效.但是现有项目管理优化理论更多地是将项目假定在没有任何约束或是较为宽泛的约束下进行, 项目管理优化的目标也往往集中在项目的进度方面. 即便增加了项目成本因素也仅涉及成本的大小, 而没有考虑该项目不同时段对资源需求量的变化对整个组织绩效的影响. 同时不同行业, 不同组织以及不同项目对项目管理优化目标也存在不同的偏好, 这也增加了优化函数以及优化方法的复杂性, 从而也对传统的项目管理优化理论提出挑战.

如表1所示, 目前项目管理优化方法可以分为四大类别：软逻辑优化, 精确算法, 启发式算法以及在此基础上形成的智能启发式算法. 应用性较为普遍的智能启发式算法包括模拟退火算法以及逐渐成为研究热点的遗传算法以及混合算法等.

表1 项目管理优化方法综述Table 1 Project schedule optimizing method review

分离弧概念启发式方法Bell&Han(1991), Tormos&Lova(2001)将分离弧的概念引入启发式算法, 对于特定行业或是特定项目起到了较为理想的优化效果能启发式方法模拟退火算法Boctor、Cho 与 Kim、Bouleimen 与Lecocq、Valls 等(2005)将物理退火步骤中系统粒子变动引起的能量与状态的变化数字化, 以项目管理优化目标函数的解来代替遗传算法[3]S Hartmann, D Briskorn（2010）, Alczraz& Maroto, Sonke Hartmann依据项目求解目标的适应度函数为判别标准, 将一定数量的母代种群中适应度函数值较高的个体挑选出来直接遗传至下一代, 避免其变异、交叉混合遗传算法Valls, P Wuliang, Quintanilla(2007), 刘士新[4], 王梦光和唐加福(2002)以遗传算法为基础, 但是在某些特定的优化过程中引入退火算法以及其他智能启发式算法的优化方法. 应用范围较为广泛.

对于智能启发式算法, Lee&Kim[5]提出将蚁群算法与遗传算法相结合创造一种新的复合算法, 作者借用启发式算法的优先规则进行算法编码. Hartmann(1998)[6]提出了以各个工序的列表来表达基因的遗传算法, 这些列表则是以项目季度为基础. 1999 年 Linet Ozdamar[7]做了一种命题假设, 提出在资源有限供应的前提约束条件下求得工期最短的项目进度优化算法, 并借以遗传算法实现最优解的求解. Alczraz & Maroto(2001)[8]引入了自适应这一自然科学应用领域的机制到启发式算法. 2002 年, Sonke Hartmann[9]在Alczra的基础上完善了自适应遗传理论. Bouleimen & Leeoeq(2003)[10]摒弃了应用较为普遍的遗传算法, 引入模拟退火算法求解资源约束下的项目进度优化问题.

在项目管理理论中, 最重要的是项目进度、项目成本以及项目质量三要素：而项目质量是项目的固有属性,是项目管理最基础的目标, 其本身优化的空间非常有限. 同时项目的质量目标对于每个行业, 每个公司以及每个项目其标准各不相同, 从而无法建立一个应用较为广泛的量化模型, 也无法在此基础上进行优化分析. 鉴于项目质量管理优化研究价值不大, 同时研究较为复杂, 因此本文仅锁定二维的项目管理范畴, 即项目成本以及项目进度范畴, 同时将项目成本分解为成本大小与资源均衡度.

2基于遗传算法的项目管理优化模型

结合前文所提到的单目标项目管理优化理论的研究经验, 本文将传统的项目进度一维优化扩展至有偏好的二维目标（进度、成本）优化, 同时将成本优化目标分解为项目成本大小以及资源均衡度从而构成三维目标优化. 进而本文提出了基于三维目标偏好的项目管理优化模型. 其中三维目标包括项目成本大小、项目进度（时间）以及项目资源利用的均衡度. 偏好依据不同行业、不同公司、不同项目以及不同的项目管理者而不同, 主要依靠专家打分法确定各个维度的具体偏好值. 同时借助启发式算法—遗传算法去计算该模型的解.

约束条件：

其中: a1+a2 =1, a3+a4=1, 且a1, a2, a3, a4不小于零. 假定在t时刻项目工序i开工, 则xit =1, 否则为0. ESN 表示整个项目的历时工期; N 为项目工序的最后一个; Di 为项目工序i的历时时间; ESi 为项目工序i最早的开始时间; LSi 为项目工序 i最晚的开始时间; Rik 为项目工序i 对特定资源k单位时间用量; Skt 为整个项目在时间t时可以提供的k资源总量; Bn 为项目工序n的所有紧前工序的集合; M表示总工期内资源统计时段数; R’ 表示平均资源使用量; Ri 表示第i天资源使用量,且Ri=∑Ri; Rij表示为第i天j工序资源使用量; C1i表示在第i天保持项目运行的直接费用; C2i表示在第i天保持项目运行的间接费用.

式（1-1）为目标函数, 表示多目标皆为最小化时项目的目标函数. 本文的问题模型以最小化项目工期、资源的综合利用、最小化项目运营成本为目标. f1(x)代表最小化的项目工期, 是对项目进度优化目标的测量. 与前述模型相同, 为了实现项目进度的最优化解, 项目可以尽可能增加资源, 增加赶工度, 项目的每个工序都应尽可能的实现最早完成时间. f2(x)是表征项目资源平衡利用指数的目标函数, 我们将资源受限的条件下资源平衡的指标定义为最小化资源利用的方差, 以单位时间资源使用量所计算得到的方差来作为评价遗传算法子个体优劣的标准. 评价函数的判断标准是资源利用方差越小的个体适应值越大, 表明其均衡利用度越大. 这样,随着遗传进化的进行,算法最终找到方差最小的资源计划. f3(x)代表项目运行的总成本大小, 包括项目运行过程中所消耗的直接费用成本以及与项目进度成正比的间接费用成本.

另外, 遗传算法的优点是将问题参数编码成染色体后进行优化, 而不是针对参数本身, 从而不受函数约束条件的 限制; 搜索过程从问题的 一个解开是, 而不是单个个体, 具有隐含并行搜索特征, 可大大减少陷入局部最小的可能. 但同时遗传算法也存在以下缺点: 对于结构复杂的 RCPSP, 搜索空间大, 搜索时间比较长, 往往会出现早熟早收敛的情况; 对初始种群很敏感, 初始种群的选择常常直接影响解的质量和算法效率.

3结论

三维目标[11]: 1.最小化项目工期: 资源约束下传统的项目进度优化管理问题的目标, 即追求项目工期最短. 2.项目成本大小: 包括项目的直接成本以及项目的间接成本. 3.项目资源均衡利用率: 各节点单位时间所需资源总量的均衡利用. 如图1所示, 借用Matlab仿真技术, 应用遗传算法可以得到项目三维目标优化结果. 项目的总进度与项目总的成本大小之间呈现出凹形的逻辑关系, 即工期过短或过长都会造成施工成本大幅上升. 这与项目的直接成本与间接成本有关, 工期过低, 项目资源需求量过大, 直接成本过高, 从而导致项目成本大幅上升. 而工期过长, 与间接成本有关的人员工资, 储存费用等大幅升高导致项目成本上升. 而项目进度与项目资源均衡利用度基本成反比关系, 这是因为项目各个工序的资源需求量是各不相同的, 而关键路径法所得的最佳项目进度是不考虑项目资源约束以及项目资源均衡利用率的, 因此要提高项目的资源综合利用率就不得不改变项目的关键路径, 增加缓冲期, 从而也会延长项目结束时间, 增加项目的工期. 而项目成本同项目资源均衡度之间呈凹型的关系, 项目资源均衡度过低往往导致项目资源的浪费, 从而意味着增加了项目的直接成本, 而项目资源均衡度过高往往意味着项目总周期的拉长, 同时也意味着项目间接成本的增加[12].

图1 基于三维目标偏好的项目管理优化模型Figure 1 preference of 3D Project schedule optimizing Model

[1] PATTERSON J H, W D Huber. A horizon-varying, zero-one approach to project scheduling [J]. Management Science, 1974, 20(6): 990-998.

[2] BRUCKER P. A branch and bound algorithm for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 1998, 107(2): 272-288.

[3] 张扬, 基于遗传算法的多资源约束下工程项目进度计划优化研究 [D]. 华东交通大学, 2009.

[4] 刘士新, 项目优化调度理论与方法[M]. 北京: 机械工业出版社, 2007.

[5] LEE J K, KIM Y D. Search heuristics for resource constrained project scheduling[J]. Journal of the Operational Research Society, 1996: 678-689.

[6] HARTMANN S. A competitive genetic algorithm for resource‐constrained project scheduling[J]. Naval Research Logistics (NRL), 1998, 45(7): 733-750.

[7] OZDAMAR L. A genetic algorithm approach to a general category project scheduling problem[J]. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 1999, 29(1): 44-59.

[8] ALCARAZ J, C MAROTO. A robust genetic algorithm for resource allocation in project scheduling[J]. Annals of Operations Research, 2001, 102(1-4): 83-109.

[9] HARTMANN S. A self‐adapting genetic algorithm for project scheduling under resource constraints[J]. Naval Research Logistics (NRL), 2002, 49(5): 433-448.

[10 BOULEIMEN K, H LECOCQ. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J]. European Journal of Operational Research, 2003, 149(2): 268-281.

[11] LEU S-S, A T Chen, C-H Yang. A GA-based fuzzy optimal model for construction time–cost trade-off[J]. International Journal of Project Management, 2001, 19(1): 47-58.

[12] 陈建华, 林鸣, 马士华. 基于过程管理的工程项目多目标综合动态调控机理模型[J]. 中国管理科学, 2005. 13(5): 93-99.

The optimization simulation model based on the project’s three-dimensional target preferences

ZENG Biao, LIU Xin
(Antai College of Economics and Management, Shanghai JiaoTong University, Shanghai 200030, P.R.C.)

The paper extends the traditional one-dimensional project schedule optimization to a preference of 2D target (schedule, cost) optimization, and then to a three-dimensional target optimization. First this article shows the theory of dynamic optimizing project schedule in detail and points out the limitations of existing methods. At the same time, it expounds the intelligent and mineralization type method, the basic principle and application of genetic algorithm, and how to use Matlab genetic algorithm of intelligent optimization function. This paper constructs the multidimensional model of optimizing management of project schedule. At last, the model solves the project schedule management problem respectively: no resource constraints project schedule optimization, the resource constraints project schedule optimization and multi-objective optimization (resource, cost, efficiency). Meanwhile, in order to verify the validity of the genetic algorithm to solve above problems, this paper applies universality case for validation. The results show that the genetic algorithm can solve such problem better compared with other traditional methods.

project management; three-dimensional target optimization; genetic algorithm; preference of 3D

TU712

A

1003-4271(2014)03-0474-04

10.3969/j.issn.1003-4271.2014.03.27

2013-12-23

曾彪(1986-), 男, 山东省济宁市人, 硕士研究生, 研究方向: 技术经济及管理; 刘欣(1969-), 女, 布依族, 上海市人, 副教授, 研究方向: 项目管理和决策分析.