Назначение-роблем, если задание доступно не один раз

Question

У меня проблема с нормальным назначением, где я хочу сопоставить работников с заданиями. Но есть несколько видов заданий, каждый из которых имеет заданное количество позиций. Так, например, мне понадобилось бы 10 000 строителей, 5000 сварщиков и т. Д. Разумеется, каждый рабочий имеет одинаковое предпочтение для каждой позиции того же вида работы.

Моим нынешним подходом является использование венгерского алгоритма и просто расширение столбцов матрицы для учета этого. Так, например, у него будет 10 000 столбцов-строителей, 5000 сварщиков и т. Д. Конечно, с O (n^3) и большой матрицей, получение результатов может занять некоторое время.

Есть ли вариации венгерского алгоритма или другого, который использует тот факт, что может быть несколько соединений с одним узлом задания? Или лучше изучить алгоритмы дерева Монте-Карло или генетического поиска?

редактировать:

Формальное описание, как Sascha предложил:

Набор Вт для рабочих, J для рабочих мест, весовой функции для предпочтения, функция на сумму рабочих мест

So функция Я хочу, чтобы свести к минимуму будет:

где

Ограничения будут:

и

, как спросил Yay, это было бы хорошо, если он побежал за день или два на обычной потребительской машине. Сейчас работают 50 тыс. Человек с 10 видами рабочих мест и 50 тыс. Рабочих мест. Таким образом, матрица 50k x 50k (расширенная) в случае алгоритма, который я использую сейчас, или 50k x 10 для LP с дополнительным ограничением , тогда как и значения предпочтений в матрице будут идти от 0-100 ,

Answer 1

Это на самом деле называется транспортной проблемой. Транспортная проблема аналогична задаче назначения, поскольку они имеют источники и адресаты, но проблема транспортировки имеет еще два значения: каждый источник имеет поставку, и каждый пункт назначения имеет спрос. Задача назначения - это упрощение транспортной проблемы, при которой поставка каждого источника и требование каждого пункта назначения равны 1.

В вашем случае у вас есть 50 000 источников (ваших работников), каждый из которых снабжен 1 (каждый работник может работать только на одну работу). У вас также есть 10 пунктов назначения (типы заданий) с некоторым количеством запросов (количество отверстий для этого типа).

Транспортная проблема традиционно решена с помощью симплексного алгоритма. Я не мог рассказать вам, как это работает с моей головы, но в Интернете есть много информации о том, как это сделать. Я бы порекомендовал эти два видео: first, second.

 

В качестве альтернативы, транспорт может фактически быть также решена с помощью венгерского алгоритма.Идея состоит в том, чтобы отслеживать ваш спрос и предложение отдельно, а затем использовать Венгерский алгоритм (или любой другой алгоритм для Задачи назначения) для его решения, как если бы спрос и предложение составляли 1 (это может быть невероятно быстрым, когда это как однобокое как 50 000 источников до 10 пунктов назначения, как в вашем случае). После того, как вы его однажды решили, используйте результаты, чтобы соответствующим образом уменьшить спрос и предложение назначенного решения. Повторяйте до тех пор, пока сумма ни подачи, ни спроса не будет равна нулю.

Однако, все это может быть необходимо. Несколько лет назад я написал свой собственный решатель задач Assignment на C++, и, несмотря на использование 2,5 ГБ ОЗУ, он может решить проблему назначения 50000 на 50 000 менее чем за 5 секунд. Трюк состоит в том, чтобы написать свое. Прежде, чем я написал свою книгу, я взглянул на то, что было доступно в Интернете, и все они были довольно плохими, часто с явными ошибками. Если вы собираетесь написать свой собственный код для этого, то лучше использовать Алгоритм Simplex, как описано в видеороликах, которые были связаны выше. Я не знаю, что один быстрее, чем другой, но венгерский алгоритм не был создан для проблемы транспортировки.

 

пс: Тот же человек, который сделал две лекции я связан выше, также сделал один на Assignment Problem and the Hungarian Algorithm.