Scheduling with target start times

J.A. Hoogeveen; S.L. van de Velde

Scheduling with target start times

J.A. Hoogeveen, S.L. van de Velde

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

179 Downloads (Pure)

Abstract

We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The goal is to minimize an objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in 0( n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.

Original language	English
Title of host publication	Ten years LNMB
Subtitle of host publication	Ph.D. research and graduate courses of the Dutch Network of Operations Research
Editors	W.K. W.K. Klein Haneveld, O.J. Vrieze, L.C.M. Kallenberg
Place of Publication	Amsterdam
Publisher	Centrum voor Wiskunde en Informatica
Pages	45-53
ISBN (Print)	90 6196 475X
Publication status	Published - 1997

Publication series

Name	CWI Tract
Publisher	CWI
Number	122

Keywords

METIS-144720

Access to Document

Hoogeveen1997schedulingFinal published version, 3.95 MB

Cite this

@inbook{c9dc8444a17a4a2e82b485fd490e7ec7,

title = "Scheduling with target start times",

abstract = "We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The goal is to minimize an objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in 0( n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.",

keywords = "METIS-144720",

author = "J.A. Hoogeveen and {van de Velde}, S.L.",

year = "1997",

language = "English",

isbn = "90 6196 475X",

series = "CWI Tract",

publisher = "Centrum voor Wiskunde en Informatica",

number = "122",

pages = "45--53",

editor = "{W.K. Klein Haneveld}, W.K. and O.J. Vrieze and L.C.M. Kallenberg",

booktitle = "Ten years LNMB",

address = "Netherlands",

}

Scheduling with target start times. / Hoogeveen, J.A.; van de Velde, S.L.
Ten years LNMB: Ph.D. research and graduate courses of the Dutch Network of Operations Research. ed. / W.K. W.K. Klein Haneveld; O.J. Vrieze; L.C.M. Kallenberg. Amsterdam: Centrum voor Wiskunde en Informatica, 1997. p. 45-53 (CWI Tract; No. 122).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

TY - CHAP

T1 - Scheduling with target start times

AU - Hoogeveen, J.A.

AU - van de Velde, S.L.

PY - 1997

Y1 - 1997

N2 - We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The goal is to minimize an objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in 0( n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.

AB - We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The goal is to minimize an objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in 0( n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.

KW - METIS-144720

M3 - Chapter

SN - 90 6196 475X

T3 - CWI Tract

SP - 45

EP - 53

BT - Ten years LNMB

A2 - W.K. Klein Haneveld, W.K.

A2 - Vrieze, O.J.

A2 - Kallenberg, L.C.M.

PB - Centrum voor Wiskunde en Informatica

CY - Amsterdam

ER -

Scheduling with target start times

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this