## Abstract

Consider n independent jobs and m identical machines in parallel. Job j has a processing time p_{j} and a deadline d̄_{j}. It must complete its processing before or at its deadline. All jobs are available for processing at time t = 0 and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines; such a schedule is called a feasible schedule. Given a feasible set of jobs, our goal is to find a schedule that minimizes the total completion time Σ C_{j}. In the classical α |β| γ scheduling notation this problem is referred to as P |prmt, d̄_{j}| Σ C_{j}. Lawler (Recent Results in the Theory of Machine Scheduling, in Mathematical Programming: The State of the Art, A. Bachem, M. Grötschel, and B. Korte, eds., Springer, Berlin, 1982, pp. 202-234) raised the question of whether or not the problem is NP-hard. In this paper we present a polynomial-time algorithm for every m ≥ 2, and we show that the more general problem with m unrelated machines, i.e., R |prmt, d̄_{j}| Σ C_{j}, is strongly NP-hard.

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

Pages (from-to) | 1370-1388 |

Number of pages | 19 |

Journal | SIAM Journal on Computing |

Volume | 32 |

Issue number | 5 |

DOIs | |

State | Published - Aug 2003 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Deadline constraints
- Maximum lateness
- Parallel and identical machines
- Polynomial-time algorithm
- Preemptive scheduling
- Total completion time
- Unrelated machines