多执行模式项目调度问题的克隆选择优化.pdfVIP

第21卷 第3期 模式识别与人工智能 Vo1．21 No．3 2008年6月 PR AI June 2008 多执行模式项目调度问题的克隆选择优化水 潘晓英 刘 芳 焦李成 (西安电子科技大学智能信息处理研究所智能感知与图像理解教育部重点实验室西安 710071) 摘 要 针对多执行模式资源受限项目调度问题的具体特点，采用基于调度的编码方式、半随机的初始种群产生 方式、受限变异等策略，提出一种克隆选择优化算法用于求解项目活动的最优调度以使整个工程工期最短．该方法 将问题特性与免疫克隆选择算法所具有的全局有哪些信誉好的足球投注网站特性、解的多样性和不易早熟的特点相融合，在能获得最优解 的前提下，使得所花费的代价大为降低．通过对标准测试库PSPLIB中调度问题的仿真实验表明，该算法具有良好 的性能，对于各组测试集中的大部分问题都能在合理的时间内寻找到最优解．与其它启发式算法相比，该方法具有 更优的性能． 关键词 多执行模式，调度编码，半随机初始化，受限变异 中图法分类号 TP 181 Clonal Selection Optimization for ． Multi—Mode Resource Constrained Project Scheduling Problem PAN Xiao—Ying，LIU Fang，JIAO Li—Cheng (Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education， Institute of Intelligent Information Processing，Xidian University，Xian 710071) ABSTRACT Based on the analysis of the characteristics of project optimization scheduling，a clonal selection algorithm for multi—mode resource constrained project scheduling problem(CSA—MRCPSP)is proposed． It is used to obtain the optimal scheduling sequences SO that the duration of the project is minimized． Some strategies are adopted such as schedule encoding，semi—random initialization，and restricted mutation operator．CSA—MRCPSP synthesizes the characteristics of project scheduling global search， diversity，and no prone to premature in immune clonal selection．Thus the cost is reduced with the optimal solution being found．The experimental results on PSPLEB show CSA—MRCPSP has good performance and it can find optimal solu