求解差异工件批调度问题的改进型蚁群算法  

Improved ant colony algorithm for solving batch scheduling problem with non-identical job sizes

作　　者：贾兆红[1,2] 李丹[2] 李龙澍[1,2] 

机构地区：[1]安徽大学计算智能与信号处理教育部重点实验室,合肥230039 [2]安徽大学计算机科学与技术学院,合肥230039

出　　处：《控制与决策》2014年第10期1758-1764,共7页Control and Decision

基　　金：国家自然科学基金项目(71171184);国家留学基金委项目(201206505002);安徽大学自然科学基金项目(33050044)

摘　　要：针对最小化制造跨度的差异工件尺寸单批处理机调度问题,通过将其转化为最小化浪费空间的问题,采用候选集策略构建分批以减少搜索空间,利用基于浪费空间的启发式更新信息素,提出一种改进的最大最小蚁群算法.此外,在算法中还引入了一种局部优化策略,以进一步提高算法的性能.仿真实验结果表明,所提出的算法优于其他几种已有算法,验证了所提出算法的有效性和鲁棒性.By formulating the problem of minimizing the makespan on a single batch machine with non-identical job sizes as a problem of minimizing the wasted space minimization, a candidate set strategy is designed to narrow the search space when constructing the batches, combined with a heuristic based on the wasted space to update the pheromone information. Incorporated with a local optimization method to further improve the performance, an improved max-min ant system algorithm is presented. Moreover, the parameter setting in the proposed algorithm is analyzed by experimental designs to determine the appropriate parameter values. The simulation results show the effectiveness and robustness of the proposed algorithm that outperforms several previously studied algorithms.

关 键 词：调度 批处理机 制造跨度 最大最小蚁群算法 局部优化 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]