Abstract: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