An Exact Exponential Branch & Merge Algorithm for the Single Machine Total Tardiness Problem

The design of exact exponential algorithms for NP-hard problems focusing on worst-case scenarios has always been a challenging issue. The high interest in this area is mostly theoretical and motivated by achieving a better understanding of the intrinsic complexity of NP-hard problems. In fact, some of them appear to be solvable with a lower exponential complexity than others belonging to the same complexity class. The application of exact exponential algorithms to scheduling problems have been so far, however, quite limited. 

Here, we tackle the single machine total tardiness problem where a set of n jobs must be scheduled on a single machine. For each job j, a processing time pj and a due date dj are defined. The problem asks for arranging the jobset in a sequence so as to minimize the sum of tardiness of each job. The problem is NP-hard in the ordinary sense and it has been extensively studied in the literature and many exact procedures have been proposed. The state-of-art result on its time complexity is the dynamic programming algorithm running on O(2^n) but in exponential space. We propose a new technique called branch-and-merge whose time complexity converges to O*(2^n) and it requires only polynomial space.