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

Original language | English (US) |
---|---|

Pages (from-to) | 95-115 |

Number of pages | 21 |

Journal | ACM Transactions on Algorithms |

Volume | 2 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2006 |

## All Science Journal Classification (ASJC) codes

- Mathematics (miscellaneous)

## Keywords

- Deadline constraints
- Mean flow time
- Polynomial-time algorithms
- Uniform machines