差异工件流水车间批调度问题的求解  

Scheduling flow-shop problem with batch processing machines and non-identical job size

作　　者：朱颀[1] 陈成栋[1] 陈华平[1] 

机构地区：[1]中国科学技术大学管理学院,合肥230026

出　　处：《计算机工程与应用》2013年第13期221-227,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(No.70821001;No.71171184)

摘　　要：针对流水车间批调度问题,提出一种基于群智能算法的求解思路。结合问题具体特点,给出工件集合的分批策略,设计了将Palmer和Best Fit(BF)分批规则相结合的分批方法;在批排序阶段,提出了一种改进的微粒群算法;在粒子初始生成阶段,通过引入NEH启发式算法改进了粒子的初始化质量;在全局最佳位置更新前,通过变邻域搜索优化了算法的局部搜索能力,避免了算法陷入局部最优。仿真实验表明,改进后的算法优于传统的微粒群算法和NEH启发式算法。An approach based on swarm intelligence is presented to solve the problem of scheduling tasks on flow-shop with batch processing machines. According to the characteristics of the problem under study, a method based on Palmer and Best Fit heuristic algorithm is developed to form batches. Moreover, an improved Particle Swarm Optimization （PSO） algorithm is pre- sented to sequence the obtained batches. In PSO, the NEH heuristic is employed to improve the quality of the initial population. In order to enhance the search capabilities of the proposed algorithm, a variable neighborhood searching is performed for each iteration before the global best position is updated. The experimental results show that the proposed algorithm has a better effec-tiveness than the standard PSO algorithm and the NEH heuristic.

关 键 词：流水车间 批处理机 微粒群算法 变邻域搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]