Scheduling jobs with release times on a machine with finite storage

W.M. Nawijn, Walter Kern, S.M. Baas

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
66 Downloads (Pure)

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 languageUndefined
Pages (from-to)120-127
Number of pages8
JournalEuropean journal of operational research
Volume78
Issue number1
DOIs
Publication statusPublished - 1994

Keywords

  • METIS-140677
  • IR-30038

Cite this