同类机环境下不同尺寸工件的分批调度问题  

Batch scheduling on uniform parallel machines with non-identical job sizes

作　　者：李小林[1] 杜冰[1] 许瑞[1] 陈华平[1] 

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

出　　处：《计算机集成制造系统》2012年第1期102-110,共9页Computer Integrated Manufacturing Systems

基　　金：创新研究群体科学基金资助项目(70821001);高校博士点基金资助项目(200803580024);国家自然科学基金资助项目(71171184)~~

摘　　要：为了有效地利用批处理机,提高生产效率,提出了同类机加工环境下具有不同尺寸工件的批处理机调度问题并进行了求解。由于该问题是NP难解的,给出了一个下界以衡量近似算法的性能,并证明了该下界的有效性。提出了批的隐性加工时间的概念,并以此为基础给出了一种新的局部优化算法,对最大最小蚁群算法进行了改进。使用启发式算法最终对同类机环境下分批调度问题进行求解。通过仿真实验将该蚁群算法与遗传算法、微粒群优化算法及BFLPT等进行比较和性能分析。To improve the production efficiency by using batch processor effectively,a batch scheduling problem with non-identical job size on uniform parallel machines was proposed and solved.This problem was proved to be NP-hard,thus a lower bound was presented to evaluate the performance of approximation algorithms,and the validity of this lower bound was proved.On the basis of recessive processing time concept,a new local optimization algorithm was proposed to improve the max-min ant algorithm.A heuristic algorithm named Longest Processing Time for Uniform Machines（LPTUM） was used to solve the problem.Through simulation experiment,the proposed algorithm was compared to genetic algorithm,particle swam optimization and BFLPT,as well as the performance was analyzed.

关 键 词：同类机 批调度 蚁群优化算法 组合优化 启发式算法 

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