We consider the following single-machine bicriteria scheduling problem. A set of n independent jobs has to be scheduled on a single machine that can handle only one job at a time and that is available from time zero onwards. Each job Jj requires processing during a given positive uninterrupted time pj, and has a given target time sj and due date dj with A≤dj–sj≤A+pj for some constant A. For each job Jj(j=1,…,n), its promptness Pj is defined as the difference between the target start time and the actual start time, and its lateness Lj as the difference between the completion time and the due date. We consider the problem of finding a schedule that minimizes a function F of maximum promptness Pmax=max1≤j≤nPj and maximum lateness Lmax=max1≤j≤nLj; we assume that F is nondecreasing in both arguments. We present an O(n2) algorithm for the variant in which idle time is not allowed and an O(n2 log n) algorithm for the special case in which the objective function is linear. We prove that the problem is NP-hard if neither of these restrictions is imposed. As a side result, we prove that the special case of minimizing maximum lateness subject to release dates that lie in the interval [dj–pj–A, dj–A], for all j=1,…,n and for some constant A, is solvable in O(n log n) time if no machine idle time is allowed and in O(n2 log n) time if machine idle time is allowed.
