改进蚁群算法求解单机总加权延迟调度问题

单机总加权延迟调度(SMTWTS)问题是一类由于任务完工时间超过交货期从而优化目标为加权延迟成本最小的单机调度问题,已被证明是NP难题.蚁群算法受自然界蚁群觅食机理启发而来,也曾被用于其它类型的单机调度问题研究,但SMTWTS被认为是实际生产中面临的主要问题.本文提出一种改进蚁群算法求解SMTWTS问题,该算法对信息素更新策略进行了改进,引入信息扰动及变异策略,并对参数进行了合理设置,对比实验表明搜索效率好于遗传算法.

Improved Ant Colony Algorithm for Single Machine Total Weighted Tardiness Scheduling Problem

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.