Задача о назначении. Венгерский алгоритм.
Пусть существуют несколько заданий (Job’s) и процессоров (Processor’s). Известно время выполнения каждого задания каждым процессором.
|
Job 1 |
Job 2 |
Job 3 |
Job 4 |
Job 5 |
|
|
|
|
|
|
Processor 1 |
2 |
1 |
6 |
∞ |
9 |
|
|
|
|
|
|
Processor 2 |
2 |
7 |
2 |
14 |
2 |
|
|
|
|
|
|
Processor 3 |
7 |
6 |
1 |
14 |
15 |
|
|
|
|
|
|
Processor 4 |
6 |
12 |
2 |
18 |
11 |
|
|
|
|
|
|
Processor 5 |
1 |
7 |
∞ |
2 |
7 |
|
|
|
|
|
|
Необходимо распределить задания между процессорами так, чтобы суммарное время выполнения было минимальным.
Это задача линейного назначения.
Будем решать задачу с помощью венгерского алгоритма. Процедура 1. Получение 0 в каждой строке и столбце матрицы.
|
Job 1 |
Job 2 |
Job 3 |
Job 4 |
Job 5 |
MIN |
|
|
|
|
|
|
|
Processor 1 |
2 |
1 |
6 |
∞ |
9 |
- 1 |
|
|
|
|
|
|
|
Processor 2 |
2 |
7 |
2 |
14 |
2 |
- 2 |
|
|
|
|
|
|
|
Processor 3 |
7 |
6 |
1 |
14 |
15 |
- 1 |
|
|
|
|
|
|
|
Processor 4 |
6 |
12 |
2 |
18 |
11 |
- 2 |
|
|
|
|
|
|
|
Processor 5 |
1 |
7 |
∞ |
2 |
7 |
- 1 |
|
|
|
|
|
|
|
Найдем минимальный элемент (MIN) в каждой строке и вычтем его из всех элементов строки.
Проверим, есть ли 0 в каждом столбце таблицы. Если нет, поступим аналогично строкам.
|
Job 1 |
Job 2 |
Job 3 |
Job 4 |
Job 5 |
|
|
|
|
|
|
Processor 1 |
1 |
0 |
5 |
∞ |
8 |
|
|
|
|
|
|
Processor 2 |
0 |
5 |
0 |
12 |
0 |
|
|
|
|
|
|
Processor 3 |
6 |
5 |
0 |
13 |
14 |
|
|
|
|
|
|
Processor 4 |
4 |
10 |
0 |
16 |
9 |
|
|
|
|
|
|
Processor 5 |
0 |
6 |
∞ |
1 |
6 |
|
|
|
|
|
|
MIN |
|
|
|
- 1 |
|
|
|
|
|
|
|
Получилась матрица, в каждой строке и в каждом столбце которой есть 0.
|
Job 1 |
Job 2 |
Job 3 |
Job 4 |
Job 5 |
|
|
|
|
|
|
Processor 1 |
1 |
0 |
5 |
∞ |
8 |
|
|
|
|
|
|
Processor 2 |
0 |
5 |
0 |
11 |
0 |
|
|
|
|
|
|
Processor 3 |
6 |
5 |
0 |
12 |
14 |
|
|
|
|
|
|
Processor 4 |
4 |
10 |
0 |
15 |
9 |
|
|
|
|
|
|
Processor 5 |
0 |
6 |
∞ |
0 |
6 |
|
|
|
|
|
|
Процедура 2. По нулям матрицы построим простой граф.
Простой граф: два множества вершин (X и Y) и отображение G.
|
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
|
|
|
|
|
|
X1 |
1 |
0 |
5 |
∞ |
8 |
|
|
|
|
|
|
X2 |
0 |
5 |
0 |
11 |
0 |
|
|
|
|
|
|
X3 |
6 |
5 |
0 |
12 |
14 |
|
|
|
|
|
|
X4 |
4 |
10 |
0 |
15 |
9 |
|
|
|
|
|
|
X5 |
0 |
6 |
∞ |
0 |
6 |
|
|
|
|
|
|
X1 |
Y1 |
X2 |
Y2 |
X3 |
Y3 |
X4 |
Y4 |
X5 |
Y5 |
Число дуг равно числу нулей!!!
Процедура 3. Построим максимальное паросочетание.
Паросочетание: множество дуг не имеющих общих вершин.
|
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
|
|
|
|
|
|
X1 |
1 |
0 |
5 |
∞ |
8 |
|
|
|
|
|
|
X2 |
0 |
5 |
0 |
11 |
0 |
|
|
|
|
|
|
X3 |
6 |
5 |
0 |
12 |
14 |
|
|
|
|
|
|
X4 |
4 |
10 |
0 |
15 |
9 |
|
|
|
|
|
|
X5 |
0 |
6 |
∞ |
0 |
6 |
|
|
|
|
|
|
X1 |
Y1 |
X2 |
Y2 |
X3 |
Y3 |
X4 |
Y4 |
X5 |
Y5 |
Если не все вершины Х отобразились в Y, перейдем к процедуре 4. Вспомним задачу нахождения максимального потока в транспортной сети!!!
Процедура 4. Перестановка нулей. Найдем min опору графа.
Опора: минимальное множество вершин, инцидентных всем дугам.
Из «худой» |
|
|
|
|
Число вершин в |
|
|
|
|
|
минимальной опоре |
||
вершины идем |
|
X1 |
Y1 |
|
||
|
|
равно числу дуг в |
||||
вперед по |
|
|
|
|
максимальном |
|
«худым» дугам, |
|
|
|
|
||
|
X2 |
Y2 |
|
паросочетании !!! |
||
назад по |
|
|
||||
|
|
Если из «худой» вершины |
||||
«жирным» и |
|
|
|
|
||
помечаем |
α |
X3 |
Y3 |
α |
Х пришли в «худую» Y, то |
|
делаем инверсию дуг |
||||||
вершины |
||||||
индексом α. |
α |
|
|
|
|
|
|
X4 |
Y4 |
|
|
||
«Худая» вершина |
|
X5 |
Y5 |
|
|
|
|
|
|
|
В опору войдут вершины Х не помеченные α и
вершины Y помеченные α. Опора: X1,X2,X5,Y3
Вычеркнем из матрицы строки и столбцы опоры.
|
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
|
|
|
|
|
|
|
|
|
|
X1 |
1 |
0 |
5 |
∞ |
8 |
|
|
|
|
|
|
|
|
|
|
X2 |
0 |
5 |
0 |
11 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X3 |
6 |
5 |
0 |
12 |
14 |
|
Опора: |
|
X1,X2,X5,Y3 |
||||||
|
|
|
|
|
|
|
|
X4 |
4 |
10 |
0 |
15 |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X5 |
0 |
6 |
∞ |
0 |
6 |
|
|
|
|
|
|
|
|
|
|
В оставшейся подматрице найдем минимальный элемент (у нас это 4).
Перестановка нулей.
|
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
|
|
Вычтем найденный |
||
|
|
|
минимум из |
|||||||
|
|
|
|
|
|
|
|
|||
X1 |
1 |
0 |
9 |
∞ |
8 |
+4 |
|
столбцов не опоры и |
||
|
прибавим к строкам |
|||||||||
|
|
|
|
|
|
|
|
опоры. |
||
X2 |
0 |
5 |
4 |
11 |
0 |
+4 |
||||
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
X3 |
2 |
1 |
0 |
8 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X4 |
0 |
6 |
0 |
11 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X5 |
0 |
6 |
∞ |
0 |
6 |
+4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
-4 |
-4 |
|
-4 |
-4 |
|
Получились новые нули! |
|
||