by Lazarev, A.; Arkhipov, D. I.; Werner, F..

**Series:** 2015-03, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic
- 90C29 Multi-objective and goal programming

**Abstract:**

The following special case of the classical NP-hard scheduling problem $1|r_j|L_{max}$ is considered. There is a set of jobs $N= { 1, 2, ldots, n }$ with identical processing times $p_j=p$

for all jobs $j in N$. All jobs have to be processed on a single machine. The

{bf Abstract:} The following special case of the classical NP-hard scheduling problem $1|r_j|L_{max}$ is considered. There is a set of jobs $N= { 1, 2, ldots, n }$ with identical processing times $p_j=p$

for all jobs $j in N$. All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness $L_{max}$. We analyze algorithms for the makespan problem $1|r_j|C_{max}$, presented by Garey et al. (1981) and Simons (1978) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria $L_{max}$ and $C_{max}$. The complexity of the presented algorithms is $O(Q cdot n log n )$ and $O(n^2 log n)$, respectively, where $10^{-Q}$ is the accuracy of the input-output parameters.

**Keywords:**

scheduling, single machine, equal processing times, polynomial algorithms, bi-criteria problem