# Polynomial-time algorithms for single-machine bicriteria scheduling

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

### 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 language English Eindhoven Technische Universiteit Eindhoven 10 Published - 1992

### Publication series

Name Memorandum COSOR 9221 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).

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).