Zurück zu den Preprints des Jahres 2015


2015-03

Finding the Pareto Set for a Bi-criteria Scheduling Problem on a Single Machine with Equal Processing Times

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