85468

Автор(ы): 

Автор(ов): 

1

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

Тип публикации: 

Тезисы доклада

Название: 

On Dual and Inverse Problems in Single-Machine Scheduling

Электронная публикация: 

Да

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

  • 25th International conference Mathematical Optimization Theory and Operations Research (MOTOR-2026)

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

  • ABSTRACT of the 25th International conference Mathematical Optimization Theory and Operations Research (MOTOR-2026)

Город: 

  • Иркутск

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

  • ИДСТУ СО РАН

Год издания: 

2026

Страницы: 

73
Аннотация
Duality plays an important role in scheduling optimization, primarily as a source of bounds and algorithmic insights. In most scheduling problems, however, duality is used only indirectly through relaxations such as Lagrangian or LP relaxations, while explicit dual formulations for the original discrete models are rarely considered. A structural approach to this question was proposed in "On the dual and inverse problems of scheduling jobs to minimize maximum penalty" (Lazarev, Pravdivets, Werner, 2018), where dual problems were introduced for a single-machine scheduling model with release dates and the maximum penalty objective. In that framework the dual problem takes the form of a max-min problem corresponding to the original min-max objective. In this work we extend this approach to several classical single-machine scheduling models with min-sum objectives and without precedence constraints. For each problem we formulate the corresponding dual problem of the sum-min structure and study its structural properties. We prove that the dual formulations provide valid lower bounds for the original objectives (weak duality) and can be computed in polynomial time.

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

Лутовинова Н.А. On Dual and Inverse Problems in Single-Machine Scheduling / Сборник тезисов XXV Международной конференции «Теория математической оптимизации и исследование операций». Иркутск: ИДСТУ СО РАН, 2026. С. 73.