2173

Автор(ов):

1

Параметры публикации

Доклад

Название:

An Approximation Method for Estimating Optimal Value of Minimizing Scheduling Problems

Наименование конференции:

• European Chapter on Combinatorial Optimization (ECCO).

• Jerusalem

• -

2009

Страницы:

p.13-13
Аннотация
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.

Библиографическая ссылка:

Лазарев А.А. An Approximation Method for Estimating Optimal Value of Minimizing Scheduling Problems / . Jerusalem: -, 2009. С. p.13-13.