MINIMIZING THE SUM OF WEIGHTED COMPLETION TIMES WITH UNRESTRICTED WEIGHTS

Given a set of tasks with associated processing times, deadlines and w eights unrestricted in sign, we consider the problem of determining a task schedule on one machine by minimizing the sum of weighted complet ion times. The problem is NP-hard in the strong sense. We present a lo wer bound based on task splitting, an approximation algorithm, and two exact approaches, one based on branch-and-bound and one on dynamic pr ogramming. An overall exact algorithm is obtained by combining these t wo approaches. Extensive computational experiments show the effectiven ess of the proposed algorithm.