Abstract
In this paper we study the problem of scheduling n deteriorating jobs on m identical parallel machines. Each job's processing time is a nondecreasing function of its start time. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of the due-date, earliness and tardiness penalties. We show that this problem is NP-hard, and we present a heuristic algorithm to find near-optimal solutions for the problem. When the due-date penalty is 0, we present a polynomial time algorithm to solve it.
| Original language | English |
|---|---|
| Pages (from-to) | 1103-1108 |
| Number of pages | 6 |
| Journal | Journal of the Operational Research Society |
| Volume | 58 |
| Issue number | 8 |
| DOIs | |
| Publication status | Published - 1 Aug 2007 |
Keywords
- Deteriorating jobs
- Due-date
- Parallel-machine scheduling
ASJC Scopus subject areas
- Management Information Systems
- Strategy and Management
- Management Science and Operations Research
- Marketing