具有最大总加权满意度的单机调度问题的dynasearch算法

Dynasearch algorithms for single machine scheduling problem with total weighted satisfaction

研究了总加权满意程度最大化的单机调度问题.对最优解的性质进行分析和证明,提出该类问题的统治规则.提出该问题新的基于dynasearch邻域的迭代局域搜索算法(ILS).算法主要特点:1)dynasearch是基于多摄动的思想,即一次可以做多个相互独立的交换(或插入);2)用动态规划获得最优dynasearch移动;3)ILS采用随机kick策略对局部最优解进行摄动,然后继续迭代.实现了该问题的两种dynaearch算法;把两种dynasearch算法与统治规则相结合;在进行kick时引入误差限制.实验表明:嵌入统治规则的算法优于没有统治规则的算法;基于dynasearch交换的ILS优于基于dynasearch插入的ILS;dynaearch算法要优于以交换为邻域的多初始点改进算法.

The paper extends the dynasearch algorithm to single machine scheduling problem to maximize the total weighted satisfaction level （SMTWSL）. It gives an analysis and proof about the character of optimal solution based on which we propose a dominance rule for the problem. For this problem, it presents a new iterated local search algorithm based on dynasearch neighborhood with the following characters： 1 ） While traditional local search algorithms make a single move at each iteration, dynasearch allows a series of independent moves to be performed. 2） A dynasearch move, composed of several optimal independent moves, is obtained by dynamic programming in the expanded neighborhood. 3） A local optimal solution, obtained from an initial one by ILS algorithm, is disturbed by a random kick tactic and then is searched again by dynasearch algorithm. While dynasearch algorithm was applied to the SMTWSL problem, three pieces of work has been done： Two dynasearch algorithms are carried out. Combination of dominance rule with the algorithm speeding up the dynasearch algorithm. An error limit that restricts the difference between the local optimal solution and the solution after perturbation, also speeds up the dynasearch algorithm. The conclusions are： The combination of ILS dyasearch algorithm and dominance rule is superior to the ILS dynasearch algorithm alone. The dynasearch swap algorithm is superior to that of the dyansearch insert algorithm. Both of the swap and insert dynasearch algorithms are better than the multi-start improving algorithm based on swap.