Polynomial-time algorithms for single-machine bicriteria scheduling

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.