Scheduling jobs with release times on a machine with finite storage

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

doi:10.1016/0377-2217(94)90209-7

Scheduling jobs with release times on a machine with finite storage

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

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

6 Citations (Scopus)

169 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 language	Undefined
Pages (from-to)	120-127
Number of pages	8
Journal	European journal of operational research
Volume	78
Issue number	1
DOIs	https://doi.org/10.1016/0377-2217(94)90209-7
Publication status	Published - 1994

Keywords

METIS-140677
IR-30038

Access to Document

10.1016/0377-2217(94)90209-7

Nawijn94scheduling

Cite this

@article{db0af51007764862b6ade3f65f0ffa6b,

title = "Scheduling jobs with release times on a machine with finite storage",

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.",

keywords = "METIS-140677, IR-30038",

author = "W.M. Nawijn and Walter Kern and S.M. Baas",

year = "1994",

doi = "10.1016/0377-2217(94)90209-7",

language = "Undefined",

volume = "78",

pages = "120--127",

journal = "European journal of operational research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Scheduling jobs with release times on a machine with finite storage

AU - Nawijn, W.M.

AU - Kern, Walter

AU - Baas, S.M.

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

KW - METIS-140677

KW - IR-30038

U2 - 10.1016/0377-2217(94)90209-7

DO - 10.1016/0377-2217(94)90209-7

M3 - Article

SN - 0377-2217

VL - 78

SP - 120

EP - 127

JO - European journal of operational research

JF - European journal of operational research

IS - 1

ER -