Improved Bounds for the Range of Lateness on a Single Machine

In a recent article, Gupta and Sen have developed an algorithm to minimize the range of lateness on a single machine. The algorithm is based on the branch-and-bound approach suggested by Townsend for single-machine problems with quadratic penalty functions of completion times. In this paper, a simple general result for regular composition of cost functions is presented, application of which improves the Gupta and Sen procedure.