基于种群的多层次迭代贪婪算法优化阻塞流水车间调度问题  

Population-based multi-layer iterated greedy algorithm for solving blocking flow shop scheduling problem

作　　者：张其亮[1] 俞祚明[1] 

机构地区：[1]江苏科技大学电气与信息工程学院,江苏张家港215600

出　　处：《计算机集成制造系统》2016年第10期2315-2322,共8页Computer Integrated Manufacturing Systems

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

摘　　要：针对以最小化最大完工时间为目标的阻塞流水车间调度问题,提出一种有效的基于种群的多层次迭代贪婪算法进行求解。算法基于排列形式进行编码,提出NEH_PF(Nawaz-Enscore-Ham&profile fitting)算法构造初始种群,以提高初始解的质量;设计了多层次迭代贪婪算法,并基于插入、交换策略对个体进行变异,基于Path-Relinking算法对个体进行交叉,以提高个体局部搜索能力,并提出部分交叉策略来更新种群。通过标准实例测试,验证了所提算法的有效性。Aiming at the blocking flow shop scheduling problem with minimized makespan, an effective population- based multi-layer iterated greedy algorithm was proposed. The permutation based encoding schemes was designed in the algorithm, and Nawaz-Enscore-Ham - Profile Fitting （NEH_PF） algorithm was proposed to construct the ini- tial population for improving the quality of initial results. To enhance the local search abilities of individuals, a multi-layer iterated greedy algorithm was designed, together with the interchange and insert strategies to mutate in- dividuals and path-relinking strategies to cross the individuals. The partly crossing policy was put forward to update the populations. The effectiveness of proposed algorithm was validated through a group of benchmark instances.

关 键 词：种群 迭代贪婪算法 阻塞流水车间调度 最小化最大完工时间 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]