Minimizing Total Completion Time on Uniform Machines with Deadline Constraints

Abstract. 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