Abstract
Consider a single machine with a buffer which can store up to b waiting jobs for some fixed b. Given the release times, the weights and the processing times of n consecutive jobs, a maximum weight subset of jobs is to be found that is schedulable without violating the buffer's capacity constraint. A polynomial algorithm for the unweighted loss-delay problem is presented. The weighted case is shown to be NP-hard as well as an unweighted two-machine version.
Original language | Undefined |
---|---|
Pages (from-to) | 120-127 |
Number of pages | 8 |
Journal | European journal of operational research |
Volume | 78 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1994 |
Keywords
- METIS-140677
- IR-30038