An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem

TLDR

Traditional local search algorithms make a single move per iteration, whereas dynasearch permits a series of moves, expanding the search space. The paper introduces dynasearch, a dynamic‑programming neighborhood search that aims to use lookahead to avoid poor local optima. Dynasearch explores an exponential‑size neighborhood in polynomial time and is evaluated on the single‑machine total weighted tardiness scheduling problem. Computational experiments demonstrate that dynasearch, particularly when iterated with random moves away from previous minima, outperforms first‑improve, best‑improve, and other local search methods for minimizing total weighted tardiness.

Abstract

This paper introduces a new neighborhood search technique, called dynasearch, that uses dynamic programming to search an exponential size neighborhood in polynomial time. While traditional local search algorithms make a single move at each iteration, dynasearch allows a series of moves to be performed. The aim is for the lookahead capabilities of dynasearch to prevent the search from being attracted to poor local optima. We evaluate dynasearch by applying it to the problem of scheduling jobs on a single machine to minimize the total weighted tardiness of the jobs. Dynasearch is more effective than traditional first-improve or best-improve descent in our computational tests. Furthermore, this superiority is much greater for starting solutions close to previous local minima. Computational results also show that an iterated dynasearch algorithm in which descents are performed a few random moves away from previous local minima is superior to other known local search procedures for the total weighted tardiness scheduling problem.