首页 | 新闻公告 | 作者指南 | 编委会 | 关于杂志 | 订阅 | 相关链接 | 下载区 | 联系我们

一种差异工件单机批调度问题的蚁群优化算法
摘要点击 4271  全文点击 4103    
查看全文  查看/发表评论  下载PDF阅读器
中文关键词  调度; 批处理机; 蚁群优化算法; 组合优化;
英文关键词  scheduling; batch processing machines; ant colony optimization; combinatorial optimization;
基金项目  国家自然科学基金资助项目:(70671096);;国家杰出青年基金(B类)资助项目(70629002)
学科分类代码  
作者单位
王栓狮 中国科学技术大学管理学院 
陈华平  
程八一  
李燕  
中文摘要
      由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的,从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了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 solution is coded as a job sequence which is corresponding to a solution of the prob...
关闭

版权所有 © 2007 《管理科学学报》
通讯地址:天津市南开区卫津路92号天津大学第25教学楼A座908室 邮编:300072
联系电话/传真:022-27403197 电子信箱: jmstju@263.net