Планирование загрузки оборудования с учетом максимальной производительности станков

 

Рассмотрим следующую задачу.

На предприятии пять станков различных видов, каждый из которых может выполнять пять различных операций по обра­ботке деталей. Известна производительность каждого станка при выполнении каждой операции, заданная матрицей

 

 

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

Решение. Так как в задаче требуется определить max, a алгоритм метода дан для задач на min, умножим матрицу С на (—1). Сложим полученную матрицу, имеющую отрицатель­ные коэффициенты, с положительным числом, например с чис­лом 10. Получим

 

 

Минимальные элементы в строчках есть 3, 4, 4, 6, 4. Выч­тем их из соответствующих элементов матрицы, получим

 

 

Так как назначение не получено, вычеркиваем строку 2, столбцы 2, 4, 5:

 

 

Минимальный элемент равен 1. Вычитаем его из всех не­вычеркнутых элементов и складываем со всеми элементами, расположенными на пересечении двух линий. Получаем

 

 

Оптимальное решение, соответствующее последней матри­це, равно

 

 

Суммарная производительность: 6 + 6 + 3 + 6 + 7= 28.

Таким образом, на первом станке надо делать 5-ю опера­цию, на втором — 1-ю операцию, на третьем — 4-ю операцию, на четвертом — 3-ю операцию, на пятом станке — 2-ю опе­рацию. Суммарная производительность: 28 деталей в единицу времени.