摘要
为了有效地利用批处理机,提高生产效率,提出了同类机加工环境下具有不同尺寸工件的批处理机调度问题并进行了求解。由于该问题是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.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2012年第1期102-110,共9页
Computer Integrated Manufacturing Systems
基金
创新研究群体科学基金资助项目(70821001)
高校博士点基金资助项目(200803580024)
国家自然科学基金资助项目(71171184)~~
关键词
同类机
批调度
蚁群优化算法
组合优化
启发式算法
uniform parallel machines
batch scheduling
ant colony optimization
combinatorial optimization
heuristic algorithms
