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 Sept 2007 |
Keywords
- Deteriorating jobs
- Fully polynomial-time approximation scheme
- Parallel-machine scheduling
ASJC Scopus subject areas
- General Business,Management and Accounting
- Economics and Econometrics
- Management Science and Operations Research
- Industrial and Manufacturing Engineering