1991
Scheduling around a small common due date
Publication
Publication
European Journal of Operational Research p. 237- 242
A set of n jobs has to be scheduled on a single machine which can handle only one job at a time. Each job requires a given positive uninterrupted processing time and has a positive weight. The problem is to find a schedule that minimizes the sum of weighted deviations of the job completion times from a given common due date d, which is smaller than the sum of the processing times. We prove that this problem is NP-hard even if all job weights are equal. In addition, we present a pseudopolynomial algorithm that requires O(n2d) time and O(nd) space.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1016/0377-2217(91)90228-N, hdl.handle.net/1765/12356 | |
| ERIM Top-Core Articles | |
| European Journal of Operational Research | |
| Organisation | Erasmus Research Institute of Management |
|
Hoogeveen, H., & van de Velde, S. (1991). Scheduling around a small common due date. European Journal of Operational Research, 237–242. doi:10.1016/0377-2217(91)90228-N |
|
