?
Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan
The following special case of the classical NP-hard scheduling problem (Formula presented.) is considered. There is a set of jobs (Formula presented.) with identical processing times (Formula presented.) for all jobs (Formula presented.). All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness (Formula presented.). We analyze algorithms for the makespan problem (Formula presented.), presented by Garey et al. (SIAM J Comput 10(2):256–269, 1981), Simons (A fast algorithm for single processor scheduling. In: 19th Annual symposium on foundations of computer science (Ann Arbor, Mich., 1978, 1978) and Benson’s algorithm (J Glob Optim 13(1):1–24, 1998) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria (Formula presented.) and (Formula presented.). The complexity of the presented algorithms is (Formula presented.) and (Formula presented.), respectively, where (Formula presented.) is the accuracy of the input-output parameters. © 2016 Springer-Verlag Berlin Heidelberg