Scheduling with target start times

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

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

    41 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 languageEnglish
    Title of host publicationTen years LNMB
    Subtitle of host publicationPh.D. research and graduate courses of the Dutch Network of Operations Research
    EditorsW.K. W.K. Klein Haneveld, O.J. Vrieze, L.C.M. Kallenberg
    Place of PublicationAmsterdam
    PublisherCentrum voor Wiskunde en Informatica
    Pages45-53
    ISBN (Print)90 6196 475X
    Publication statusPublished - 1997

    Publication series

    NameCWI Tract
    PublisherCWI
    Number122

    Fingerprint

    Objective function
    Total completion time
    Single machine
    Preemption
    Costs

    Keywords

    • METIS-144720

    Cite this

    Hoogeveen, J. A., & van de Velde, S. L. (1997). Scheduling with target start times. In W. K. W.K. Klein Haneveld, O. J. Vrieze, & L. C. M. Kallenberg (Eds.), Ten years LNMB: Ph.D. research and graduate courses of the Dutch Network of Operations Research (pp. 45-53). (CWI Tract; No. 122). Amsterdam: Centrum voor Wiskunde en Informatica.
    Hoogeveen, J.A. ; van de Velde, S.L. / Scheduling with target start times. Ten years LNMB: Ph.D. research and graduate courses of the Dutch Network of Operations Research. editor / W.K. W.K. Klein Haneveld ; O.J. Vrieze ; L.C.M. Kallenberg. Amsterdam : Centrum voor Wiskunde en Informatica, 1997. pp. 45-53 (CWI Tract; 122).
    @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",

    }

    Hoogeveen, JA & van de Velde, SL 1997, Scheduling with target start times. in WK W.K. Klein Haneveld, OJ Vrieze & LCM Kallenberg (eds), Ten years LNMB: Ph.D. research and graduate courses of the Dutch Network of Operations Research. CWI Tract, no. 122, Centrum voor Wiskunde en Informatica, Amsterdam, pp. 45-53.

    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 proceedingChapterAcademic

    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 -

    Hoogeveen JA, van de Velde SL. Scheduling with target start times. In W.K. Klein Haneveld WK, Vrieze OJ, Kallenberg LCM, editors, Ten years LNMB: Ph.D. research and graduate courses of the Dutch Network of Operations Research. Amsterdam: Centrum voor Wiskunde en Informatica. 1997. p. 45-53. (CWI Tract; 122).