| Article ID: | iaor20081712 |
| Country: | Netherlands |
| Volume: | 109 |
| Issue: | 1/2 |
| Start Page Number: | 180 |
| End Page Number: | 184 |
| Publication Date: | Jan 2007 |
| Journal: | International Journal of Production Economics |
| Authors: | Ng C.T., Kang Liying |
| Keywords: | deteriorating items |
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.