# 7039

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

3

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

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

Книга (брошюра, монография, стандарт)

## Название:

Classical Combinatorial and Single Machine Scheduling Problems With Opposite Optimality Criteria

• Magdeburg

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

• Otto-von-Guericke Universitaet

2010

## Объём, стр.:

15
Аннотация
In this paper, we consider some scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. We present some complexity results for such maximization problems with classical objective functions (e.g. total tardiness, number of tardy jobs and total completion time) and various additional constraints (e.g. deadlines, weights and/or release dates of jobs may be given). As a generalization, we consider a classical combinatorial problem with an opposite optimization criterion, namely a minimization version of the knapsack problem, for which we give an NP-hardness proof and an exact pseudo-polynomial algorithm.

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

Гафаров Е.Р., Лазарев А.А., Werner F. Classical Combinatorial and Single Machine Scheduling Problems With Opposite Optimality Criteria. Magdeburg: Otto-von-Guericke Universitaet, 2010. – 15 с.