# 8664

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

3

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

Доклад

## Название:

Polynomially Solvable Case of the NP-Hard Problem 1|r_j|L_{max}

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

• International Conference on Project Management and Scheduling

• Tours

• -

2010

## Страницы:

C. 289-293
Аннотация
We consider the classical NP-hard scheduling problem in strong sense $1|r_j|L_{max}$. New properties of optimal schedules are found. Polynomially case is found when the release times $(r_j)$, the processing times $(p_j)$ and due dates $(d_j)$ of jobs satisfy the relationships: $d_j=\altha p_j+\beta r_j+C$, $p_j\leq 0$, $\alpha\in[0,1]$, $\beta \in [1,+\infty)$, $C$ -- constant. An algorithm finds Pareto-optimal sets of schedules for objective functions $L_{max}$ and $C_{max}$ that contains no more than $n$ schedules. The machine can process at most one job at any time, and preemptions of the processing of a job are forbidden.

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

Лазарев А.А., Архипов Д.И., Карпов И.В. Polynomially Solvable Case of the NP-Hard Problem 1|r_j|L_{max} / . Tours: -, 2010. С. C. 289-293.