An Approximation Method for Estimating Optimal Value of Minimizing Scheduling Problems

P. 13–13.

Lazarev A. A.

In this paper, for $NP$-hardness single and multi-machine scheduling problems with the criterion of minimization maximum lateness the metrics $\rho$ has been used. We consider some approaches finding of the approximate solution for the problems. The idea of approaches consists in construction to a initial instance $A$ such instance $B$ (with the same number of jobs) with minimum of estimation of absolute error that$$0\le L_{max}^A(\pi^B)-L_{max}^A(\pi^A)\le \rho_d(A,B)+ \rho_r(A,B)+\rho_p(A,B),$$ where $\rho_d(A,B)=\max\limits_{j\in N}\{d_j^A-d_j^B\}-\min\limits_{j\in N}\{d_j^A-d_j^B\},$ $ \rho_r(A,B)=\max\limits_{j\in N}\{r_j^A-r_j^B\}-\min\limits_{j\in N}\{r_j^A-r_j^B\}$ and$\rho_p(A,B)=\sum\limits_{j\in N}|p_j^A-p_j^B|,$ and $\pi^A, \pi^B$ -- optimal schedules for instances $A$ and $B$,respectively. Besides $\rho(A,B)=\rho_d(A,B)+ \rho_r(A,B)+\rho_p(A,B)$ satisfies to properties of the metrics in$(3n-2)$-dimensional space $\{(r_j,p_j,d_j)\,|\,j\in N\}$ with fixed in two parameters.

Keywords: оптимизация, optimization, модели, models, scheduling theory, теория расписаний, приближенные алгоритмы, approximation algorithms

In book

European Chapter on Combinatorial Optimization (ECCO 2009)

Jerusalem: [б.и.], 2009.