Scheduling unit processing time jobs on a single machine with multiple criteria

We examine single machine scheduling problems when all jobs have identical processing times and there are two measures of performance. The measures of performance considered are flow-time, tardiness, number of tardy jobs, the weighted counterparts for these three measures and maximum tardiness. Using the assignment model as a basis, we provide efficient algorithms for the problem when a utility function is given, when one criterion is considered to be primary and the other one secondary. We also develop algorithms that are polynomial in the number of nondominated schedules to generate all nondominated schedules. Finally, we show that the methods can easily be extended to handle more than two criteria, as well as nonzero release dates.