东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

一种差异工件单机批调度问题的蚁群优化算法

期刊名称：管理科学学报, 2009. 12(6): 72-82.
时间：0
分类：TP29[自动化与计算机技术—控制科学与工程;自动化与计算机技术—检测技术与自动化装置]
作者机构：[1]中国科学技术大学管理学院,合肥230026
相关基金：基金项目：国家自然科学基金资助项目：（70671096）;国家杰出青年基金（B类）资助项目（70629002）
相关项目：分布系统的协调优化与风险管理

关键词：调度, 批处理机, 蚁群优化算法, 组合优化, scheduling, batch processing machines, ant colony optimization, combinatorial optimization

中文摘要：

由于在利用蚁群算法构建差异工件（即工件有尺寸差异）单机批调度问题的解时，批的加工时间是不确定的，从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息，引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息，提出了JACO （ ant colony optimization based a job sequence）和BACO（ant colony optimization based a batch sequence）两种蚁群优化算法．在算法JACO中，解的编码为工件序列，它对应着用BF（best fit）分批规则生成的调度方案，信息素代表工件间的排列顺序；在算法BACO中，解的编码为批序列，信息素代表工件间的批相关性，由此信息素通过中间信息素量来构造相应的解，并引入特定的局部优化策略，提高了算法的搜索效率．实验表明，与以往文献中的sA（simulated annealing）、GA（genetic algorithm）算法以及FFL门（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.

同期刊论文项目