摘要
单机总加权延迟调度(SMTWTS)问题是一类由于任务完工时间超过交货期从而优化目标为加权延迟成本最小的单机调度问题,已被证明是NP难题。蚁群算法受自然界蚁群觅食机理启发而来,也曾被用于其它类型的单机调度问题研究,但SMTWTS被认为是实际生产中面临的主要问题。本文提出一种改进蚁群算法求解SMTWTS问题,该算法对信息素更新策略进行了改进,引入信息扰动及变异策略,并对参数进行了合理设置,对比实验表明搜索效率好于遗传算法。
Single Machine Total Weighted Tardiness Scheduling （SMTWTS） problem is a kind of single machine scheduling problem in which completion time of jobs may exceed the due dates and the objective is to minimize the total weighted tardiness, SMTWTS has been proved to be NP-hard, Ant Colony algorithm has been inspired by the feeding behaviour of real ant colonies to be used to other kinds of single machine scheduling problems, but SMTWTS is considered main problem of production in practice. SMTWTS was solved by an improved ant colony algorithm, in which pheromone updation rules were improved, pheromone perturbation and mutation method were introduced and several parameters were appropriately set. Finally contradistinctive experiments are executed to prove outperforming genetic algorithm.
出处
《系统仿真学报》
EI
CAS
CSCD
北大核心
2008年第8期2052-2055,共4页
Journal of System Simulation
基金
国家863项目(2006AA04Z134)
国家自然科学基金(70772029)
安徽省自然科学基金(050460401)
关键词
单机总加权调度问题
蚁群算法
信息素更新
信息素扰动
变异
参数设置
single machine total weighted tardiness scheduling problem
ant colony algorithm
pheromone updation
pheromone perturbation
mutation
parameter setting
