Polynomial-time algorithms for single-machine bicriteria scheduling

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

    Research output: Book/ReportReportAcademic

    39 Downloads (Pure)

    Abstract

    We address the problem of scheduling nindependent jobs on a single machine so as to minimize an objective function that is composed of total completion time and a minmax criterion. First, we show that, if the second criterion is maximum cost, then the problem is solvable in $O(n^3 \min\{n, \log n+\log \rho_{max}\})$ time, where \rho_{max} is the maximum job processing time, for every nondecreasing composite objective function. Second, we show that, if the second criterion is maximum promptness, then the problem is solved in O(n^4) time for every nondecreasing linear composite objective function if preemption is allowed or if total completion time outweighs maximum promptness. Key Words & Phrases: single-machine scheduling, bicriteria scheduling, composite objective function, Pareto optimal points, extreme points, total completion time, maximum cost, maximum lateness, maximum promptness.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages10
    Publication statusPublished - 1992

    Publication series

    NameMemorandum COSOR
    Volume9221
    ISSN (Print)0926-4493

    Fingerprint

    Bicriteria
    Polynomial-time algorithm
    Objective function
    Single machine
    Total completion time
    Costs
    Single machine scheduling
    Preemption
    Key words
    Maximum lateness

    Cite this

    Hoogeveen, J. A., & Velde, van de, S. L. (1992). Polynomial-time algorithms for single-machine bicriteria scheduling. (Memorandum COSOR; Vol. 9221). Eindhoven: Technische Universiteit Eindhoven.
    Hoogeveen, J.A. ; Velde, van de, S.L. / Polynomial-time algorithms for single-machine bicriteria scheduling. Eindhoven : Technische Universiteit Eindhoven, 1992. 10 p. (Memorandum COSOR).
    @book{08764b7b2edc4707a30427ee3cb21c24,
    title = "Polynomial-time algorithms for single-machine bicriteria scheduling",
    abstract = "We address the problem of scheduling nindependent jobs on a single machine so as to minimize an objective function that is composed of total completion time and a minmax criterion. First, we show that, if the second criterion is maximum cost, then the problem is solvable in $O(n^3 \min\{n, \log n+\log \rho_{max}\})$ time, where \rho_{max} is the maximum job processing time, for every nondecreasing composite objective function. Second, we show that, if the second criterion is maximum promptness, then the problem is solved in O(n^4) time for every nondecreasing linear composite objective function if preemption is allowed or if total completion time outweighs maximum promptness. Key Words & Phrases: single-machine scheduling, bicriteria scheduling, composite objective function, Pareto optimal points, extreme points, total completion time, maximum cost, maximum lateness, maximum promptness.",
    author = "J.A. Hoogeveen and {Velde, van de}, S.L.",
    year = "1992",
    language = "English",
    series = "Memorandum COSOR",
    publisher = "Technische Universiteit Eindhoven",

    }

    Hoogeveen, JA & Velde, van de, SL 1992, Polynomial-time algorithms for single-machine bicriteria scheduling. Memorandum COSOR, vol. 9221, Technische Universiteit Eindhoven, Eindhoven.

    Polynomial-time algorithms for single-machine bicriteria scheduling. / Hoogeveen, J.A.; Velde, van de, S.L.

    Eindhoven : Technische Universiteit Eindhoven, 1992. 10 p. (Memorandum COSOR; Vol. 9221).

    Research output: Book/ReportReportAcademic

    TY - BOOK

    T1 - Polynomial-time algorithms for single-machine bicriteria scheduling

    AU - Hoogeveen, J.A.

    AU - Velde, van de, S.L.

    PY - 1992

    Y1 - 1992

    N2 - We address the problem of scheduling nindependent jobs on a single machine so as to minimize an objective function that is composed of total completion time and a minmax criterion. First, we show that, if the second criterion is maximum cost, then the problem is solvable in $O(n^3 \min\{n, \log n+\log \rho_{max}\})$ time, where \rho_{max} is the maximum job processing time, for every nondecreasing composite objective function. Second, we show that, if the second criterion is maximum promptness, then the problem is solved in O(n^4) time for every nondecreasing linear composite objective function if preemption is allowed or if total completion time outweighs maximum promptness. Key Words & Phrases: single-machine scheduling, bicriteria scheduling, composite objective function, Pareto optimal points, extreme points, total completion time, maximum cost, maximum lateness, maximum promptness.

    AB - We address the problem of scheduling nindependent jobs on a single machine so as to minimize an objective function that is composed of total completion time and a minmax criterion. First, we show that, if the second criterion is maximum cost, then the problem is solvable in $O(n^3 \min\{n, \log n+\log \rho_{max}\})$ time, where \rho_{max} is the maximum job processing time, for every nondecreasing composite objective function. Second, we show that, if the second criterion is maximum promptness, then the problem is solved in O(n^4) time for every nondecreasing linear composite objective function if preemption is allowed or if total completion time outweighs maximum promptness. Key Words & Phrases: single-machine scheduling, bicriteria scheduling, composite objective function, Pareto optimal points, extreme points, total completion time, maximum cost, maximum lateness, maximum promptness.

    M3 - Report

    T3 - Memorandum COSOR

    BT - Polynomial-time algorithms for single-machine bicriteria scheduling

    PB - Technische Universiteit Eindhoven

    CY - Eindhoven

    ER -

    Hoogeveen JA, Velde, van de SL. Polynomial-time algorithms for single-machine bicriteria scheduling. Eindhoven: Technische Universiteit Eindhoven, 1992. 10 p. (Memorandum COSOR).