Abstract
We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.
Original language | English |
---|---|
Pages (from-to) | 685-695 |
Number of pages | 11 |
Journal | Journal of the Operational Research Society |
Volume | 45 |
Issue number | 6 |
DOIs | |
Publication status | Published - 1 Jan 1994 |
Keywords
- NP-completeness
- Parallel-machine
- Scheduling
- Sequencing
ASJC Scopus subject areas
- Management Information Systems
- Strategy and Management
- Management Science and Operations Research
- Marketing