Abstract
In this paper we study the NP-hard problem of scheduling n deteriorating jobs on m identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only.
| Original language | English |
|---|---|
| Pages (from-to) | 180-184 |
| Number of pages | 5 |
| Journal | International Journal of Production Economics |
| Volume | 109 |
| Issue number | 1-2 |
| DOIs | |
| Publication status | Published - 1 Sep 2007 |
Keywords
- Deteriorating jobs
- Fully polynomial-time approximation scheme
- Parallel-machine scheduling
ASJC Scopus subject areas
- Business, Management and Accounting(all)
- Economics and Econometrics
- Management Science and Operations Research
- Industrial and Manufacturing Engineering