一种求解资源受限项目调度问题的自适应遗传算法  

A Self-adapted Genetic Algorithm for Resource-constrained Project Scheduling Problems

作　　者：王宏[1] 林丹[1] 李敏强[2] 

机构地区：[1]天津大学理学院数学系,天津300072 [2]天津大学系统工程研究所,天津300072

出　　处：《系统工程》2005年第12期99-102,共4页Systems Engineering

基　　金：国家自然科学基金资助项目(7030100570171002)

摘　　要：遗传算法(GA)应用在经典资源受限项目调度问题中取得了显著的效果。本文提出了一种新的编码方法,亦即在任务链表后面加上两个基因,一个是表示解码规则的S/P基因,另一个是表示解码方向的F/B基因,由这两个基因同时控制任务链表的解码规则和解码方向。为了验证其有效性,选用标准数据库PSPL IB中的156个例子进行验证,结果表明:本算法优于采用编码为任务链表和带有S/P基因的任务链表的两个遗传算法。本算法的设计思想对于解决相关组合最优化问题具有一定的指导意义。This paper proposes a new GA approach to solve the classical resource-constrained project scheduling problem （RCPSP）. A new representation for solutions employed is an activity list with two genes which determine the decoding procedure and decoding direction for the related activity list simultaneously. This allows the GA to adapt itself to a problem instance. As test instances we employed the standard sets for RCPSP. The result shows that our GA yields better results than the other two GAs which make use of the activity list representation and the activity list with S/P gene representation respectively.

关 键 词：项目调度 资源受限 遗传算法 编码 

分 类 号：C934[经济管理—管理学]