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 -