Estimates of the absolute error and a scheme for an approximate solution to scheduling problems |
| |
Authors: | A. A. Lazarev |
| |
Affiliation: | (1) Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, ul. Profsoyuznaya 65, Moscow, 117997, Russia |
| |
Abstract: | An approach is proposed for estimating absolute errors and finding approximate solutions to classical NP-hard scheduling problems of minimizing the maximum lateness for one or many machines and makespan is minimized. The concept of a metric (distance) between instances of the problem is introduced. The idea behind the approach is, given the problem instance, to construct another instance for which an optimal or approximate solution can be found at the minimum distance from the initial instance in the metric introduced. Instead of solving the original problem (instance), a set of approximating polynomially/pseudopolynomially solvable problems (instances) are considered, an instance at the minimum distance from the given one is chosen, and the resulting schedule is then applied to the original instance. |
| |
Keywords: | scheduling theory minimization of maximum lateness absolute error estimate approximate solution |
本文献已被 SpringerLink 等数据库收录! |
|