Котов В. М. Алгоритмы для задач разбиения и упаковки. Мн.: БГУ, 2001. - 99 с. 

ISBN 985-445-611-0

Работа посвящена вопросам построения приближенных алгоритмов с гаран­тированными оценками точности для двух модельных задач дискретной оптимизации — разбиения и упаковки. Эти задачи широко используются в теории расписа­ний, раскроя и размещения, распределения ресурсов.

Наряду с традиционными версиями задач в работе рассматриваются on - line и semi on - line версии.

Предлагаются новые способы вычисления нижних границ значений оптимальных решений, что позволило автору получить рекордные на сегодняшний день приближенные алгоритмы.

Оглавление

ПРЕДИСЛОВИЕ

3

Глава 1. ЗАДАЧА k -РАЗБИЕНИЯ

4

1.1. Введение

1.2. Оценка величины оптимального значения задачи k - разбиения

6

1.3. Приближенные методы для задачи k -разбиения

11

1.3.1. Алгоритмы свертки

11

1.3.2. Алгоритмы типа "В минимально загруженный"

14

1.3.3. Обменный алгоритм

15

1.3.4. Прямо-двойственный подход

18

Глава 2. ЗАДАЧА 3-РАЗБИЕНИЯ И ЕЕ ПРИЛОЖЕНИЯ

30

2.1. Введение

30

2.2. Описание алгоритма

32

2.3. Приложения в теории расписаний

38

Глава 3. ЗАДАЧА О РАЗБИЕНИИ

41

3.1. Введение

41

3.2. Описание алгоритмов

43

3.3. Доказательство теоремы 9

45

3.4. Доказательство теоремы 10

50

Глава 4. SEMI ON - LINE ВЕРСИЯ ЗАДАЧИ РАЗБИЕНИЯ

54

4.1. Введение

54

4.2. Буфер данной длины

56

4.3. Два параллельных процессора

61

4.4. Известная общая сумма

65

4.5- Semi on - line алгоритм для задачи теории расписаний с заданной

суммарной длительностью работ

66

4.6- Анализ точности алгоритма

69

Глава 5. ON - LINE АЛГОРИТМЫ ДЛЯ УПАКОВКИ С ОГРАНИЧЕНИЯМИ

73

5.1. Введение

73

5.2. Алгоритм А ₁

75

5.3. Алгоритм А ₂

85

5.4. Наилучший алгоритм для задачи ( о2ВР )

88

5.4.1. Нижняя граница

91

5.5. Приближенный алгоритм для задачи ( оЗВР )

93

ЛИТЕРАТУРА

94