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.