New Solution Approaches to the General Single- Machine Earliness-Tardiness Problem

This paper addresses the general single-machine earliness-tardiness problem with distinct release dates, due dates, and unit costs. The aim of this research is to obtain an exact nonpreemptive solution in which machine idle time is allowed. In a hybrid approach, we formulate and then solve the problem using dynamic programming (DP), while incorporating techniques from branch-and-bound (BB). This approach (DP-BB) has been proven to be effective in solving certain types of scheduling problems. We further propose a new adaptation of the approach to a general problem with a nonregular objective function. To address some shortcomings of DP-BB, we also apply a BB approach in which partial dynamic programming dominance (BB-PDP) is exploited. Computational experiments were conducted with randomly generated test instances in order to evaluate the effectiveness of the two approaches. The results clearly showed that our new approaches can solve all the instances with up to 40 jobs and most of the instances with 50 jobs, which outperforms those frequently used approaches in scheduling research.