摘要
由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的,从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization baseda batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT(best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.
In this paper, two ant colony optimization（ACO） algorithms are proposed to minimize makespan for scheduling jobs with non-identical sizes on a single batch processing machine. Compared with the traditional ACO algorithm, we design new heuristic information based on utilization ratio and load balance ratio of a batch for this problem. In the first algorithm named JACO（ ant colony optimization based a job sequence）, the solu- tion is coded as a job sequence which is corresponding to a solution of the problem based on BBF（ Batch Best Fit） heuristic, and whose pheromone trail is associated with the sequence of jobs. In the second algorithm named BACO（ ant colony optimization based a batch sequence）, the solution is coded as a batch sequence which represents a solution of the problem. Its pheromone trail is associated with the extent that jobs are scheduled into the same batch. Computational results show that JACO and BACO significantly outperform other four algorithms addressed in literatures, which are SA （simulated annealing）, GA （genetic algorithm）, FFLPT （first-fit longest processing time） and BFLPT（best-fit longest processing time）. Furthermore, BACO is better than JACO. These results show that BACO is an effective and efficient method for solving scheduling problems to minimize makespan on a single batch processing machine with non-identical job sizes.
出处
《管理科学学报》
CSSCI
北大核心
2009年第6期72-82,共11页
Journal of Management Sciences in China
基金
国家自然科学基金资助项目:(70671096)
国家杰出青年基金(B类)资助项目(70629002)
关键词
调度
批处理机
蚁群优化算法
组合优化
scheduling
batch processing machines
ant colony optimization
combinatorial optimization
