Minimizing total completion time on uniform machines with deadline constraints

Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time Σ C_j. In the classical α | β | γ scheduling notation, this problem is referred to as Qm | prmt, d̄_j | Σ C_j. It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.