论文部分内容阅读
单机总加权延迟调度(SMTWTS)问题是一类由于任务完工时间超过交货期从而优化目标为加权延迟成本最小的单机调度问题,已被证明是NP难题。蚁群算法受自然界蚁群觅食机理启发而来,也曾被用于其它类型的单机调度问题研究,但SMTWTS被认为是实际生产中面临的主要问题。本文提出一种改进蚁群算法求解SMTWTS问题,该算法对信息素更新策略进行了改进,引入信息扰动及变异策略,并对参数进行了合理设置,对比实验表明搜索效率好于遗传算法。
Single-machine total weighted delay scheduling (SMTWTS) problem is a kind of single machine scheduling problem with the task of completing the task exceeding the delivery time and the optimization goal being the least weighted delay cost, which has been proved to be an NP problem. Ant colony algorithm is inspired by the foraging mechanism of ants in nature and has also been used in other types of scheduling problems. However, SMTWTS is considered as a major problem in practical production. This paper proposes an improved ant colony algorithm to solve the SMTWTS problem. The algorithm improves the pheromone updating strategy, introduces information perturbation and mutation strategy, and sets parameters rationally. Comparative experiments show that the search efficiency is better than the genetic algorithm.