Задача о назначениях

В процессе управления производством зачастую возникают задачи назначения исполнителей на различные виды работ, например, подбор кадров и назначение кандидатов на вакантные, распределение источников капиталовложений между различными проектами научно-технического развития, распределения экипажей самолетов между различными авиалиниями.

Задачу о назначениях можно сформулировать следующим образом. Необходимо выполнить n различных работ. Для их выполнения можно привлечь n рабочих. Каждый рабочий за определенную плату готов выполнить любую работу.

Требуется так распределить работы между рабочими, чтобы общие затраты на выполнение всех работ были бы минимальными.

Обозначения:

c_ij – мера эффективности назначения, то есть использования i-го рабочего на j-й работе;

x_ij – переменная задачи;

x_ij – 1 (если i-й рабочий используется на j-й работе) или 0 (в любом другом случае).

Модель задачи о назначениях:

(1)

(2а)

(2б)

(3)

(1) – целевая функция (максимум эффекта);

(2) – ограничения, отражающие следующие условия:

а) каждая работа должна быть выполнена;

б) каждый рабочий может использоваться только на одной работе.

Если количество работ m меньше числа исполнителей n, задачу необходимо привести к каноническому виду, когда эти величины совпадают. Для этого вводят дополнительные работы m+1,...,n. Соответствующие коэффициенты матрицы назначений с_ij, i=1,…,n; j=m+1,…,n, можно положить равными нулю.

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

Задача о назначениях является частным случаем транспортной задачи.

-20-

Задача 6

Цеху металлообработки предложено выполнить срочный заказ на производство партии деталей. Для производства детали необходимо выполнить операции на четырех станках. В настоящее время в цехе работают четыре слесаря высокой квалификации, каждый из которых может работать на любом станке, но с разным процентом брака. Процент брака при обработке детали известен из документации ОТК.

Каким образом мастеру следует распределить работу на станках, чтобы минимизировать процент брака (предполагается, что ОТК проверяет готовую деталь, то есть общий процент брака определяется как сумма процентов брака, допущенного всеми рабочими)?