Scheduling with target start times

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

Scheduling with target start times

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

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

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 O(n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.

Original language	English
Title of host publication	Ten Years LNMB
Editors	W.K. Klein Haneveld, O.J. Vrieze, L.C.M. Kallenberg
Place of Publication	Amsterdam
Publisher	Centrum voor Wiskunde en Informatica
Pages	45-54
ISBN (Print)	90-6196-475-X
Publication status	Published - 1997

Publication series

Name	CWI Tract
Volume	122

Cite this

@inbook{e2fcbc0bb0d24286965f8637896a67fb,

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 O(n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.",

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

year = "1997",

language = "English",

isbn = "90-6196-475-X",

series = "CWI Tract",

publisher = "Centrum voor Wiskunde en Informatica",

pages = "45--54",

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

booktitle = "Ten Years LNMB",

}

TY - CHAP

T1 - Scheduling with target start times

AU - Hoogeveen, J.A.

AU - Velde, van de, 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 O(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 O(n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.

M3 - Chapter

SN - 90-6196-475-X

T3 - CWI Tract

SP - 45

EP - 54

BT - Ten Years LNMB

A2 - 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

Fingerprint

Cite this