Polynomial-time algorithms for single-machine bicriteria scheduling

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

    Research output: Book/ReportReportAcademic

    66 Downloads (Pure)


    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
    ISSN (Print)0926-4493


    Dive into the research topics of 'Polynomial-time algorithms for single-machine bicriteria scheduling'. Together they form a unique fingerprint.

    Cite this