# 60734

## Автор(ов):

4

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

Глава в книге

## Название:

Polynomially solvable subcases for the approximate solution of multi-machine scheduling problems

Да

## ISBN/ISSN:

978-3-030-65739-0 (eBook) 1865-0937 (electronic)

## DOI:

10.1007/978-3-030-65739-0_16

## Наименование источника:

• Communications in Computer and Information Science (Advances in Optimization and Applications)

## Город:

• Cham, Switzerland

## Издательство:

• Springer Nature

2020

## Страницы:

211-223
Аннотация
New metrics for different classes of scheduling problems are introduced. We show how approximate solutions of NP-hard problems can be obtained using these metrics. To do this, we solve the optimization problem in which the introduced metric is used as the objective function, and a system of linear inequalities of (pseudo-)polynomial solvable instances of the initial problem represents the constraints. As a result, we find a projection of the considered sub-instance onto the set of solvable cases of the problem in the introduced metric.

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

Лазарев А.А., Лемтюжникова Д.В., Правдивец Н.А., Вернер Ф.. Polynomially solvable subcases for the approximate solution of multi-machine scheduling problems / Communications in Computer and Information Science (Advances in Optimization and Applications). Cham, Switzerland: Springer Nature, 2020. С. 211-223.