### Abstract

Original language | English |
---|---|

Place of Publication | Eindhoven |

Publisher | Technische Universiteit Eindhoven |

Number of pages | 10 |

Publication status | Published - 1992 |

### Publication series

Name | Memorandum COSOR |
---|---|

Volume | 9221 |

ISSN (Print) | 0926-4493 |

### Fingerprint

### Cite this

*Polynomial-time algorithms for single-machine bicriteria scheduling*. (Memorandum COSOR; Vol. 9221). Eindhoven: Technische Universiteit Eindhoven.

}

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

Research output: Book/Report › Report › Academic

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 -