МФТИ, курс по выбору1 МФТИ весенний семестр 2006 г. Теория расписаний. Алгоритмический подход.

МФТИ, курс по выбору2 MINIMIZING TOTAL TARDINESS ON A SINGLE MACHINE Only one job at a time Without preemptions Jobs are available at time 0

МФТИ, курс по выбору3

4 Decomposition approach

МФТИ, курс по выбору5

6

7 2n – dimension space (d 1, d 2,…, d n, p 1, p 2, …,p n )

МФТИ, курс по выбору8

9

10

МФТИ, курс по выбору11

МФТИ, курс по выбору12 Partitioning procedure

МФТИ, курс по выбору13 Algorithms for the special case

МФТИ, курс по выбору14

МФТИ, курс по выбору15

МФТИ, курс по выбору16

МФТИ, курс по выбору17

МФТИ, курс по выбору18

МФТИ, курс по выбору19

МФТИ, курс по выбору20

МФТИ, курс по выбору21

МФТИ, курс по выбору22

МФТИ, курс по выбору23

МФТИ, курс по выбору24

МФТИ, курс по выбору25

МФТИ, курс по выбору26

МФТИ, курс по выбору27 Polynomial reduction scheme

МФТИ, курс по выбору28 Solution Algorithm

МФТИ, курс по выбору29 Example

МФТИ, курс по выбору30

МФТИ, курс по выбору31

МФТИ, курс по выбору32

МФТИ, курс по выбору33

МФТИ, курс по выбору34

МФТИ, курс по выбору35

МФТИ, курс по выбору36

МФТИ, курс по выбору37

МФТИ, курс по выбору38

МФТИ, курс по выбору39

МФТИ, курс по выбору40

МФТИ, курс по выбору41

МФТИ, курс по выбору42

МФТИ, курс по выбору43

МФТИ, курс по выбору44

МФТИ, курс по выбору45

МФТИ, курс по выбору46

МФТИ, курс по выбору47

МФТИ, курс по выбору48 Алгоритмы решения проблемы 1|| T j Lawler (1977) алгоритм трудоёмкости O(n 4 p j ) Szwarc et al., Chang et. al., Lazarev (подходящие позиции) Croce & Grosso погрешность эвристических алгоритмов n

МФТИ, курс по выбору49 Правила исключения 1-3 Правило исключения 4 (Chang)

МФТИ, курс по выбору50

МФТИ, курс по выбору51 Алгоритм «Муравьиные колонии» m муравьёв (итераций) 1 муравей строит 1 расписание

МФТИ, курс по выбору52 Муравей выполняет последовательность шагов

МФТИ, курс по выбору53 Корректировка накопленной статистической информации Трудоемкость без лок. поиска O(mn 2 ). Трудоемкость с лок. Поиском не меньше O(mn 3 ).

МФТИ, курс по выбору54 Гибридный алгоритм Использует идеи алгоритма «Муравьиные колонии» и комбинаторные свойства Подходящих позиций

МФТИ, курс по выбору55

МФТИ, курс по выбору56

МФТИ, курс по выбору57 Трудоемкость без лок. поиска O(mn 2 ). Трудоемкость с лок. Поиском не меньше O(mn 3 ).

МФТИ, курс по выбору58 Экспериментальное сравнение эффективности алгоритмов Тестовые примеры Поттса и Вассенхова n = 4,5, …, 70, 100. По 2500 примеров для каждого n. См. таблицы в pdf файле

МФТИ, курс по выбору59 Эффективность алгоритмов для примеров случая B-1 n = 4,5, …,100. По 1000 примеров для каждого n. См. таблицы в pdf файле

МФТИ, курс по выбору60 Эффективность алгоритмов для канонических DL-примеров Примеры NP-полной проблемы Чётно-Нечётного Разбиения (ЧНР) канонические DL-примеры См. таблицы в pdf файле

МФТИ, курс по выбору61 ВЫВОДЫ

МФТИ, курс по выбору62 Objective function:

МФТИ, курс по выбору63

МФТИ, курс по выбору64

МФТИ, курс по выбору65

МФТИ, курс по выбору66 Linear programming problem

МФТИ, курс по выбору67

МФТИ, курс по выбору68

МФТИ, курс по выбору69

МФТИ, курс по выбору70

МФТИ, курс по выбору71

МФТИ, курс по выбору72

МФТИ, курс по выбору73

МФТИ, курс по выбору74

МФТИ, курс по выбору75

МФТИ, курс по выбору76

МФТИ, курс по выбору77

МФТИ, курс по выбору78

МФТИ, курс по выбору79

МФТИ, курс по выбору80

МФТИ, курс по выбору81

МФТИ, курс по выбору82

МФТИ, курс по выбору83

МФТИ, курс по выбору84

МФТИ, курс по выбору85

МФТИ, курс по выбору86

МФТИ, курс по выбору87

МФТИ, курс по выбору88

МФТИ, курс по выбору89

МФТИ, курс по выбору90

МФТИ, курс по выбору91

МФТИ, курс по выбору92

МФТИ, курс по выбору93

МФТИ, курс по выбору94

МФТИ, курс по выбору95

МФТИ, курс по выбору96

МФТИ, курс по выбору97

МФТИ, курс по выбору98

МФТИ, курс по выбору99

МФТИ, курс по выбору100

МФТИ, курс по выбору101

МФТИ, курс по выбору102

МФТИ, курс по выбору103

МФТИ, курс по выбору104

МФТИ, курс по выбору105

МФТИ, курс по выбору106

МФТИ, курс по выбору107

МФТИ, курс по выбору108

МФТИ, курс по выбору109 Алгоритм динамического программирования для задачи о рюкзаке

МФТИ, курс по выбору110

МФТИ, курс по выбору111 Графический алгоритм для задачи о рюкзаке

МФТИ, курс по выбору112 Шаг 1

МФТИ, курс по выбору113 Шаг 2 Рассматриваем 4 точки: 0, 2, 0+3, 2+3

МФТИ, курс по выбору114 Шаг 3 Рассматриваем 7 точек: 0, 2, 3, 5, 0+5, 2+5, 3+5. Точка 5+5 > 9 не рассматривается

МФТИ, курс по выбору115 Шаг 4

МФТИ, курс по выбору116 Трудоёмкость алгоритмов Трудоёмкость алгоритма динамического программирования O(nA). В примере рассмотрено точек 4*9 = 36 Трудоёмкость графического алгоритма зависит от количества точек «излома графика». Для целочисленных примеров количество таких точек не превосходит А. Трудоёмкость алгоритма не превосходит O(nA). В примере рассмотрено точек = 18 В графическом алгоритме учитываются некоторые свойства задачи. На 4-м шаге примера заведомо «невыгодный» предмет с номером 4, у которого наименьшая удельная стоимость (цена/вес) не оказал влияние на график функции. Графический алгоритм позволяет решить пример и в случае когда a i или A не целые.

МФТИ, курс по выбору117 Задача Разбиения (в оптимизационной постановке)

МФТИ, курс по выбору118 Идея графического алгоритма

МФТИ, курс по выбору119 Шаг 1 Храним результат:

МФТИ, курс по выбору120 Шаг 2

МФТИ, курс по выбору121 Шаг 2

МФТИ, курс по выбору122 Шаг 3

МФТИ, курс по выбору123 Трудоемкость графического алгоритма Несложно показать, что количество точек «излома функции» растет экспоненциально для некоторых примеров. Но для целочисленных примеров количество таких точек не превосходит b j. То есть трудоёмкость не превосходит трудоёмкости алгоритма динамического программирования O(nb j ). Трудоёмкость для нецелочисленных примеров экспоненциальна. По результатам экспериментов для 99% целочисленных примеров трудоёмкость полиномиальна.

МФТИ, курс по выбору124

МФТИ, курс по выбору125

МФТИ, курс по выбору126

МФТИ, курс по выбору127

МФТИ, курс по выбору128

МФТИ, курс по выбору129

МФТИ, курс по выбору130

МФТИ, курс по выбору131

МФТИ, курс по выбору132

МФТИ, курс по выбору133

МФТИ, курс по выбору134

МФТИ, курс по выбору135

МФТИ, курс по выбору136

МФТИ, курс по выбору137

МФТИ, курс по выбору138

МФТИ, курс по выбору139

МФТИ, курс по выбору140

МФТИ, курс по выбору141

МФТИ, курс по выбору142

МФТИ, курс по выбору143

МФТИ, курс по выбору144 Обозначения P-параллельные идентичные приборы; Q- параллельные приборы разной производительности; R- параллельные различные приборы; prec- заданы отношения предшествования; pmtn- разрешены прерывания при обслуживании требований; tree- древовидный граф; chain- набор цепей; s-p- последовательно-параллельные графы;

МФТИ, курс по выбору145

МФТИ, курс по выбору146

МФТИ, курс по выбору147

МФТИ, курс по выбору148

МФТИ, курс по выбору149

МФТИ, курс по выбору150

МФТИ, курс по выбору151

МФТИ, курс по выбору152

МФТИ, курс по выбору153

МФТИ, курс по выбору154

МФТИ, курс по выбору155

МФТИ, курс по выбору156