**:** . .,

. .,

. .
**:**
**:** 57
**:** -
**:** 2015
**:** . ., . ., . . / . 57. .: , 2015. .123-137.

** :** , , NP-,

** (.):** scheduling theory, approximation algorithms, NPhardness, metrics

**:** NP- 1|rj|PTj . , , . .

** (.):** We consider the NP-hard 1|rj|PTj scheduling problem and suggest the polynomial time algorithm to find its approximate solution with the guaranteed absolute error. The algorithm employs the metric introduced in the parameter space. We also consider possible application of such an approach to the other scheduling problems.

PDF -
: 3078, : 1058, : 3.