作者：吴苏寒totaltardiness
摘要：多任务处理与排序论的跨领域组合,可以解决现实生活中许多面临寻找'最优解'或'近似解'的问题。旨在讨论解延迟时间最小化问题。选取经典排序论模型,考察资源与工作之间通过合理的时间安排,以实现目标函数的要求。经典算法中常用SPT排序和EDD排序来解决单机器排序问题,但对某些问题则只能给予近似解,因此在此基础上由SPT与EDD排序方法产生了很多启发式算法。因为基本问题的总时间(∑~T)本身为NP-hard问题,所以我们用一种启发式算法——禁忌搜索(Tabular Search)算法实现单机器以总延迟最小为目标函数在两种特殊情形下的近似解。考虑到多任务处理的情况,额外增加了转换时间模块(f(·))与打断时间模块(g(·)),目标函数因此变化为∑(C_j-T_j)·U_j。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
