Бизнес-портал для руководителей, менеджеров, маркетологов, экономистов и финансистов

Поиск на AUP.Ru


Объявления

А.В. Катаев Т.М. Катаева
Управление проектами на базе динамической сети партнеров. Монография.

Предыдущая

3.2. Механизмы поиска оптимального распределения проектных работ по исполнителям

Проблемы оптимального распределения работ (заказов, проектов, задач) по совокупности исполнителей (агентов, партнеров) математически могут быть сформулированы в виде различных задач о назначениях.
Классическая постановка однокритериальной задачи о назначениях в исследовании операций  состоит в нахождение пар «Исполнитель – Работа», которые обеспечивают минимум суммарных затрат на выполнение всех работ, причем каждый исполнитель выполняет только одну работу и для одной работы требуется только один исполнитель. То есть исполнители не делимы между работами, а работы не делимы между исполнителями. Таким образом, задача о назначениях является частным случаем транспортной задачи. Задачи о назначениях имеют место при назначении людей на должности или работы, бригад ни строительные объекты, автомашин на маршруты, водителей на автомобили и т.п.
В табл. 3.1 приведена матрица задачи о назначениях по типу транспортной задачи.
Таблица 3.1
Общий вид матрицы задачи о назначениях


Исполнители,

Работы,

Количество исполнителей,

1

1

1

Количество работ,

1

1

1

f11
      f12             
Пример задачи:
Необходимо распределить заказы по партнерам, чтобы суммарная стоимость (цена, внутренняя стоимость) выполнения совокупности заказов (задач) была минимальна. Решение данной задачи предполагает, что:
- сроки, объемы и качество  выполнения фиксированы для каждого заказа (устанавливаются заказчиком либо менеджером как необходимое требование);
- возможность выполнения и стоимость  (внутренняя стоимость) выполнения определенного заказа  сообщается каждым партнером после предоставления требований и условий заказа (можно через аукционы) либо известна заранее по каждому партнеру для типовых заказов (например, тарифы для перевозок груза, цена на размещения рекламных сообщений, расценки по аренде помещений и т.п.);
Следует заметить, что для решения данной задачи с помощью модели (3.21) n должно равняться m. В случае несовпадения количества исполнителей и работ, необходимо ввести либо фиктивные работы, либо фиктивных исполнителей с присвоением  заведомо больших значений (запрет) – больше максимального  не фиктивных значений.
Задача о назначениях в таком виде может быть решена с помощью венгерского метода, симплекс-метода и др. В некоторых случаях, например, когда  – это компетентность, опыт работы,  или квалификация работников, условие задачи может требовать максимизации ЦФ. В этом случае ЦФ  заменяется на  и решают задачу с ЦФ , что равносильно решению задачи с ЦФ .

f13

f14
f15
.
f20

f21
К недостаткам модели и метода решения, предложенного Ларичевым О.И., можно отнести следующее:
1. Для упорядочения претендентов используется грубая порядковая шкала. На практике же критерии могут иметь численные значения и измеряться в интервальной шкале. В этом случае интересует не только число имеющихся совпадений значений, но и величина несовпадения.
2. Предполагается однородность оценок несовпадения. Как правило, критерии разнородны и нуждаются в нормализации.
3. Предполагается равная значимость критериев в векторах xi и yj. На практике критерии, характеризующие возможности исполнителя и требования со стороны работы, как правило, неравноценны. То есть необходимо учитывать значимость (важность) этих критериев.
4. Ориентация только на совпадение предложений с требованиями с заданием точечных значений. В случае если есть исполнитель, который полностью соответствует требованиям, и исполнитель с характеристиками выше требований, то предпочтение будет отдано первому, а не второму.
Перечисленные недостатки сужают область применения данной модели и метода решения. Они могут быть использованы только в частных случаях задачи распределения заказов в рамках виртуального предприятия.
Задачи распределения заказов, сформулированных в виде задач целочисленного линейного программирования, могут быть так же сформулированы на случай множества критериев оптимальности. Ниже рассмотрим некоторые подходы и примеры решения многокритериальных задач (задач многокритериального выбора).
Для решения многокритериальных задач оптимизации известен ряд методов, которые можно условно разделить на четыре группы:
1. Сведение многих критериев к одному, например, путем аддитивной свертки с применением весовых коэффициентов важности для каждого критерия.
2. Минимизация абсолютных или относительных отклонений от наилучших значений по всем критериям.
3. Оптимизация только одного критерия, а остальные критерии выступают в роли дополнительных ограничений.
4. Ранжирование множества критериев и последовательная оптимизация по каждому из них. Например, для первого по важности критерия находится оптимальное значение целевой функции, которое становится дополнительным ограничением при поиске оптимального решения по второму критерию и так далее.
f17
Учитывая, что значения критериев имеют различные единицы измерения, они приведены к безразмерному виду и произведена их свертка с учетом важности каждого критерия. В результате получена матрица интегральных коэффициентов (суперкритериев) D, элементы которой можно получить по следующей формуле:
f18
В модели (3.28) учтены в виде ограничений выдвигаемые заказчиком или руководством требования по стоимости заказа, времени и качеству выполнения каждого заказа. В модели не требуется совпадение количества исполнителей и работ.
В (3.28) могут быть добавлены, к примеру, следующие условия:
- ограничения на количество типовых заказов ki, которые может взять каждый партнер:
f19
- учет невозможности выполнения работы j партнером i с помощью присвоения соответствующим  заведомо больших значений (больше максимального ) либо путем прямого введения в модель дополнительного ограничения вида
;                                                 
- учет принятого ранее решения по закреплению конкретной  работы j за определенным исполнителем i путем присвоения соответствующему  значений меньше минимального либо заданием условия вида
.                                                  
Однокритериальные и многокритериальные задачи о назначениях могут ставиться  с рядом других целевых функций и дополнительных условий, часть из которых будет рассмотрена далее.


[1] D.R. Fulkerson, I. Glicksberg, and O. Gross. A production line assignment problem. Tech. Rep. RM-1102, The Rand Corporation, Santa Monica, CA, 1953.

[2] R. Garfinkel. An improved algorithm for the bottleneck assignment problem. Oper. Res., 19:1747–1751, 1971.

[3] O. Gross. The bottleneck assignment problem. Tech. Rep. P-1630, The Rand Corporation, Santa Monica, CA, 1959.

[4] Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в волшебных странах. М.: Логос, 2003. 392 с.

[5] Микони С.В. Теория и практика рационального выбора: монография. М.: Маршрут, 2004. 463 с.

[6] Черняк Л., Сердечкина Н., Кожухаров А., Патрикеева Т. Модель процесса подготовки рукописи в издательстве // Алгоритмы и модели управления в технических и организационных системах. М., 1976.

[7] Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в волшебных странах. М.: Логос, 2003. 392 с.

[8] Катаев А.В. Информационные системы и модели оптимизации распределения заказов в партнерской сети виртуального предприятия // Прикладная информатика. 2007. № 5 (11). С. 11-22.


 

Предыдущая

Объявления