引用本文:郑晓龙,王凌,王圣尧.求解置换流水线调度问题的混合离散果蝇算法[J].控制理论与应用,2014,31(2):159~164.[点击复制]
ZHENG Xiao-long,WANG Ling,WANG Sheng-yao.A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem[J].Control Theory and Technology,2014,31(2):159~164.[点击复制]
求解置换流水线调度问题的混合离散果蝇算法
A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem
摘要点击 2632  全文点击 2477  投稿时间：2013-07-05  修订日期：2013-09-23
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2013.30675
  2014,31(2):159-164
中文关键词  置换流水车间调度  离散果蝇算法  协作进化  混合算法
英文关键词  permutation flow-shop scheduling  discrete fruit fly optimization algorithm  co-evolution  hybrid algorithm
基金项目  国家重点基础研究发展计划资助项目(2013CB329503); 国家自然科学基金资助项目(61174189).
作者单位邮编
郑晓龙 清华大学 自动化系 100084
王凌* 北京清华大学自动化系 100084
王圣尧 清华大学 自动化系 
中文摘要
      针对置换流水线调度问题, 提出了一种新颖的混合离散果蝇算法. 算法每一代进化包括4个搜索阶段: 嗅觉 搜索、视觉搜索、协作进化和退火过程. 在嗅觉搜索阶段, 采用插入方式生成邻域解; 在视觉搜索阶段, 选择最优邻 域解更新个体; 在协作进化阶段, 基于果蝇个体间的差分信息产生引导个体; 在退火操作阶段, 以一定概率接受最 优引导个体从而更新种群. 同时, 通过试验设计方法对算法参数设置进行了分析, 并确定了合适的参数组合. 最后, 通过基于标准测试集的仿真结果和算法比较验证了所提算法的有效性和鲁棒性.
英文摘要
      To solve the permutation flow-shop scheduling problem (PFSP), we propose a novel hybrid discrete fruit fly optimization algorithm (HDFOA). Each generation of evolution in the algorithm contains four search stages: smell-based search, vision-based search, co-evolutionary search and annealing procedure. In the smell-based search stage, an insertion operator is adopted to produce neighbors. In the vision-based search stage, the individuals are replaced by their best neighbors. In the co-evolutionary search stage, the guiding individuals are produced based on the differential information among fruit flies. In the annealing procedure, the best guiding fruit flies are accepted according to certain acceptance probabilities for updating the population. Moreover, the effect from parameter setting is analyzed by using the experiment design method, and a combination of suitable parameter values is determined. Finally, simulation results and comparisons based on the benchmark testing sets demonstrate the effectiveness and robustness of the proposed algorithm.