随机资源约束项目调度问题基于序的果蝇算法
An order-based fruit fly optimization algorithm for stochastic resource-constrained project scheduling
摘要点击 1248  全文点击 858  投稿时间:2014-09-02  修订日期:2014-12-22
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2015.40813
  2015,32(4):540-545
中文关键词  随机资源约束项目调度  果蝇算法  协作进化  预选机制  最优计算量分配
英文关键词  stochastic resource-constrained project scheduling  fruit fly optimization algorithm  collaborative search  pre-select scheme  optimal computing budget allocation
基金项目  国家重点基础研究发展计划项目(2013CB329503), 国家自然科学基金项目(61174189)资助.
学科分类代码  
作者单位邮编
郑晓龙 清华大学 自动化系 100084
王凌 清华大学 自动化系 100084
中文摘要
      针对项目活动工期为随机变量的资源约束项目调度问题, 提出一种基于序的果蝇算法. 为了实现随机环境下解的有效评价, 提出一种预选机制, 并采用基于序的最优计算量分配技术. 为了使果蝇算法能够求解资源约束项目调度问题, 采用交换操作执行果蝇算法的嗅觉搜索, 并采用保优更新操作执行视觉搜索. 为了均衡算法的局部搜索和全局搜索能力, 在标准果蝇算法中引入了协作进化环节并采用两点交叉操作加以实现. 在不同随机分布的情况下, 采用标准测试集进行仿真测试. 与现有算法的比较结果验证了所提预选机制和基于序的果蝇算法的有效性.
英文摘要
      An order-based fruit fly optimization algorithm (OFOA) is proposed to solve the resource-constrained project scheduling problem (RCPSP) with stochastic activity duration. To evaluate solutions effectively under the stochastic environment, a pre-select scheme is proposed, and the order-based optimal computing budget allocation (OCBA) is adopted. To make the FOA suitable for RCPSP, the swap operator is used to perform the smell-based search, and the elite updating operator is used as vision-based search. To balance the exploration and exploitation abilities, a collaborative search element is embedded into the original FOA and implemented by using the two-point crossover operator. Simulation tests are carried out with the benchmark dataset by taking several types of distributions into account. The comparisons with existing algorithms demonstrate the effectiveness of the proposed pre-select scheme and the OFOA.