Dual and Reverse Problems to Minimize Maximum Penalty Scheduling Problems

Лазарев А. А.

We study the classical NP-hard non-preemptive single machine scheduling problem to minimize the maximum penalty with release dates. Penalty of each job is a monotone and non-decreasing function of its completion time. We propose polynomial algorithms for the dual and inverse problems where the minimum penalty is maximized. Both algorithms run in quadratic time. Note that the solution values of the inverse and dual problems are valid lower bounds for the original problem. Therefore, our algorithms can be used within the branch-and-bound scheme when solving the original NP-hard problem.

Ключевые слова: оптимизация, optimization, модели, models, scheduling theory, теория расписаний, приближенные алгоритмы, approximation algorithms

В книге

European Conference on Operational Research - 2010

Lisbon: [б.и.], 2010.