Общая математическая формулировка решаемой задачи

Задача оптимального закрепления операций за станками часто встречается в практике руководителей. С ее помощью можно получить ответы следующего типа:

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

. Как распределить операции за станками так, чтобы общая выработка была максимальной

Математически такие задачи относятся к тому же типу задач, что транспортные, но со следующими особенностями:

· В этих задачах объемы требующихся и наличных ресурсов равны 1 (Аj = Вj = 1)

Например: 10 операций по 10 станкам

· Все переменные хij =1, если операция закреплена за станком, либо хij =0 в любых других случаях.

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

Общая постановка задачи состоит в определении оптимального плана распределения некоторого количества операций по имеющимся в наличии станках. Таким образом, учитывая, что в решении задач может применяться транспортная модель мы имеем, что на предприятии имеется m видов станков, каждый из которых может выполнить n видов операций. При этом Аi - максимальное время работы станка i-го вида, Вj - время выполнения j-й операции, Сij -производительность i-го станка при выполнении j-й операции (число деталей в единицу времени), хij - время работы i-го станка на j-й операции. Сij хij - количество j -x деталей, обработанных на i-м станке.

Тогда целевая функция (количество деталей, обработанных на всех станках) будет иметь вид:

Так как ограничено время отведённое на выполнение - операции величиной , то получаем

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

Поскольку переменные xij удовлетворяют системам линейных уравнений и условию неотрицательности (x), обеспечиваются назначение каждой операции на каждый из имеющихся станков. В ходе решения задачи нам необходимо определить, сколько времени и на какой операции нужно использовать каждый станок, чтобы обработать максимальное количество деталей при минимальной затрате временного ресурса.

Всякое неотрицательное решение систем линейных уравнений (время отведённое на выполнение - операции величиной и максимальное время каждой операции), то получаем определяемое матрицей , называется планом задачи оптимального закрепления операций за станками.