A tabu search algorithm for parallel machine total tardiness problem

In this study, we consider the problem of scheduling a set of independent jobs with sequence dependent setups on a set of uniform parallel machines such that total tardiness is minimized. Jobs have non-identical due dates and arrival times. A tabu search (TS) approach is employed to attack this complex problem. In order to obtain a robust search mechanism, several key components of TS such as candidate list strategies, tabu classifications, tabu tenure and intensification/diversification strategies are investigated. Alternative approaches to each of these issues are developed and extensively tested on a set of problems obtained from the literature. The results obtained are considerably better than those reported previously and constitute the best solutions known for the benchmark problems as to date. Scope and purposeSeveral surveys on parallel machine scheduling with due date related objectives (Oper. Res. 38(1) (1990) 22; EJOR 38 (1989) 156; Oper. Res. 42 (1994) 1025) reveal that the NP-hard nature of the problem renders it a challenging area for many researchers who studied various versions. However, most of these studies make the assumption that jobs are available at the beginning of the scheduling period, which is an important deviation form reality. In this study, as well as distinct due dates and ready times, features such as sequence dependent setup times and different processing rates for machines are incorporated into the classical model. These enhancements approach the model to the actual practice at the expense of complicating the problem further. For this complex problem, we present a tabu search (TS) algorithm to minimize total tardiness and provide the best solutions known for a set of benchmark problems.