Задача о назначениях - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов

Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й задачи на j-м машине. Задачи решаются одновременно с некоторого момента t0. Найти такое распределение задач по вычислительным машинам, чтобы общее время решения всех задач было бы минимальным при условии что на одной машине может решаться только одна задача.

Решение. Исходная матрица имеет вид:

Табл. 9

5

5

M

2

2

7

4

2

3

1

9

3

5

M

2

7

2

6

7

8

Для устранения дисбаланса добавляем дополнительные строки.

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Табл. 10

3

3

M

0

0

2

6

3

1

2

0

1

7

1

3

M

0

2

5

0

4

5

6

2

0

0

0

0

0

0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

Табл. 11

3

3

M

0

0

6

3

1

2

0

7

1

3

M

0

5

0

4

5

6

0

0

0

0

0

0

0

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

Табл. 12

3

3

M

[0]

[-0-]

6

3

1

2

[-0-]

7

1

3

M

[-0-]

5

[0]

4

5

6

[-0-]

[-0-]

[-0-]

[-0-]

[0]

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 3), то решение недопустимое.

3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 5, строку 1,столбец 2.

Получаем сокращенную матрицу:

Табл. 13

3

3

M

0

0

6

3

1

2

0

7

1

3

M

0

5

0

4

5

6

0

0

0

0

0

Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:

Табл. 14

3

3

M

0

0

5

3

0

1

0

6

1

2

M

0

4

0

3

4

6

0

0

0

0

0

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

Табл. 15

3

4

M

0

1

5

3

0

1

0

6

1

2

M

0

4

0

3

4

6

0

1

0

0

1

1. Проводим редукцию матрицы по строкам.

В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Табл. 16

3

4

M

0

1

0

5

3

0

1

0

0

6

1

2

M

0

0

4

0

3

4

6

0

0

1

0

0

1

0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

Табл. 17

3

4

M

0

1

5

3

0

1

0

6

1

2

M

0

4

0

3

4

6

0

1

0

0

1

0

0

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

Табл. 18

3

4

M

[0]

1

5

3

[0]

1

[-0-]

6

1

2

M

[0]

4

[0]

3

4

6

[0]

1

[-0-]

[-0-]

1

В результате получаем эквивалентную матрицу Сэ:

Табл. 19

3

4

M

0

1

5

3

0

1

0

6

1

2

M

0

4

0

3

4

6

0

1

0

0

1

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

Табл. 20

3

4

M

[0]

1

5

3

[0]

1

[-0-]

6

1

2

M

[0]

4

[0]

3

4

6

[0]

1

[-0-]

[-0-]

1

Cmin = 2 + 2 + 2 + 2 + 0 = 8

Похожие статьи




Задача о назначениях - Особенности математического моделирования задач, связанных с календарным планированием производственных процессов

Предыдущая | Следующая