中国机械工程

• 智能制造 • 上一篇    下一篇

基于二元分布估计算法的置换流水车间调度方法

裴小兵;赵衡   

  1. 天津理工大学管理学院,天津,300384
  • 出版日期:2017-11-25 发布日期:2017-11-23
  • 基金资助:
    天津市哲学社会科学规划项目(TJYY17-013)

Permutation Flow Shop Scheduling Problem Based on Hybrid Binary Distribution Estimation Algorithm

PEI Xiaobing;ZHAO Heng   

  1. School of Management,Tianjin University of Technology,Tianjin,300384
  • Online:2017-11-25 Published:2017-11-23

摘要: 针对最大完工时间最小的置换流水车间调度问题,提出了一种结合二元分布估计算法与生物地理学算法的混合优化算法(HB-EDA)。算法以分布估计算法为架构,以二元概率模型为进化依据,针对优秀染色体和劣势染色体分别通过概率模型挖掘出具有优势信息和劣势信息的链接基因区块组成区块库1和区块库2,借鉴生物地理学算法中的群体迁移思想,用两个区块库分别对优势和劣势染色体以指定比例进行更新操作产生子群体,并对染色体进行切段与重组,以进一步筛选高适应度的解。最后通过对Reeves和Taillard标准测试集的仿真结果和算法比较验证了所提出算法的有效性。

关键词: 置换流水车间调度, 生物地理学优化算法, 分布估计算法, 组合区块

Abstract: To solve the permutation flow shop scheduling problems with the objective of minimizing makespan, an effective new hybrid binary estimation distribution algorithm(HB-EDA) was proposed based on binary estimation of distribution algorithm and BBO. HB-EDA took distribution estimation algorithm as architecture and the binary probability model was used as the evolutionary basis. For the excellent chromosomes and the inferior chromosomes, the link gene blocks with the dominant informations and the disadvantage informations were excavated by the probability model, these blocks were reserved in two archives for future use. Integrating with migration operator of BBO, two block archives were used to update maternal chromosomes with certain migration rate to generate sub-groups, then performing segmentation and recombination on the chromosomes to further selecting high fitness solution. Simulation results on Reeves and Taillard suites and comparisons with other algorithms validate the excellent searching ability and efficiency of the proposed algorithm.

Key words: permutation flow shop scheduling, biogeography-based optimization(BBO), distribution estimation algorithm, building block

中图分类号: