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

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

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

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

4 4 Decomposition approach

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

6 6

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

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

9 9

10 10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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