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

Ответ 1

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

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

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

Ответ 2

Эта проблема может быть смоделирована как Проблема максимального потока.

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

С помощью (очень) тщательно обработанного графика мы можем найти назначение, отвечающее вашим требованиям, от максимального потока.

Позвольте мне указать требования.

Требуется:

1. Workers are assigned no more than their maximum assignments.
2. Tasks can only be assigned to workers that match one of the task interests.
3. Every task must be assigned to 3 workers.
4. Every worker must be assigned to at least 1 task.

Дополнительно:

5. Each worker should be assigned a number of tasks proportional to that worker maximum assignments
6. Each worker should be assigned a variety of tasks.

Я предполагаю, что максимальный поток найден с использованием Алгоритм Эдмондса-Карпа.

Сначала найдите график, соответствующий требованиям 1-3.

Изобразите график как 4 столбца узлов, где ребра переходят только от узлов в столбце к узлам соседнего столбца вправо.

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

В третьем столбце для каждой задачи существует node. От каждого работника во втором столбце есть край каждой задачи, которую интересует этот работник с емкостью 1 (рабочий заинтересован в задаче, если пересечение их интересов не пусто). Это обеспечит выполнение требования 2. Емкость 1 гарантирует, что каждый рабочий занимает только 1 из 3 слотов для каждой задачи.

В четвертой колонке у нас есть раковина. Существует край от каждой задачи к раковине с емкостью 3. Это обеспечит выполнение требования 3.

Теперь мы найдем максимальный поток на этом графе, используя алгоритм Эдмондса-Карпа. Если этот максимальный поток меньше, чем 3 * (# of tasks), тогда нет требований к назначению 1-3. Если нет, есть такое задание, и мы можем найти его, изучив окончательный расширенный график. В увеличенном графе, если есть край от задачи для рабочего с емкостью 1, тогда этому работнику назначается эта задача.

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

Во-первых, позвольте удовлетворить требование 4. Это потребует небольшого изменения алгоритма. Сначала установите все возможности от источника к рабочим до 1. Найдите максимальный поток на этом графике. Если поток не равен числу рабочих, то не существует требования для выполнения задания 4. Теперь, в вашем конечном остаточном графе, для каждого работника край от источника до этого работника имеет емкость 0, а обратный край имеет емкость 1. Измените их на that worker maximum assignments - 1 и 0, соответственно. Теперь продолжайте алгоритм Эдмондса-Карпа, как и раньше. В основном то, что мы сделали, сначала нахожу назначение таким образом, что каждому работнику присваивается ровно одна задача. Затем удалите обратный край из этой задачи, чтобы рабочий всегда был назначен хотя бы одной задаче (хотя это может быть не тот, который был назначен в первый проход).

Теперь давайте выполним требование 5. Строго говоря, это требование просто означает, что мы разделим каждое максимальное число рабочих заданий на sum of all worker maximum assignments / number of tasks. У этого вполне возможно не будет удовлетворительного задания. Но это нормально. Инициализируйте наш график с помощью этих новых максимальных назначений. Запустите Эдмондс-Карп. Если он найдет поток, который насыщает края от задач до потолка, мы закончили. В противном случае мы можем увеличить мощности от раковины до работников на остаточном графике и продолжить работу с Edmonds-Karp. Повторяйте, пока мы не насытим края в раковину. Не увеличивайте возможности настолько, чтобы работнику было назначено слишком много задач. Кроме того, технически, прирост для каждого работника должен быть пропорционален максимальным назначениям работника. Это легко сделать.

Наконец, позвольте удовлетворить требование 6. Это немного сложно. Во-первых, добавьте столбец между рабочими и задачами и удалите все грани от рабочих к задачам. В этом новом столбце для каждого рабочего добавить node для каждого из этих интересов работников. От каждого из этих новых узлов добавьте ребро к каждой задаче с соответствующим интересом с емкостью 1. Добавьте край от каждого работника к каждому из своих узлов интереса с емкостью 1. Теперь поток на этом графике будет обеспечивать, чтобы, если рабочий присваивается n задачам, то пересечение объединения этих задач с интересами этого рабочего имеет размер как минимум n. Опять же, возможно, что это задание выполняется без этого задания, но с ним нет ни одного. Мы можем справиться с этим так же, как и требование 5: запустить Edmonds-Karp до завершения, если нет удовлетворительного назначения, увеличить возможности от рабочих до их узлов интереса и повторить.

Обратите внимание, что на этом измененном графике мы больше не удовлетворяем требованию 3, так как одному работнику может быть присвоено несколько/все слоты задачи, если пересечение их интересов имеет размер больше 1. Мы можем это исправить. Добавьте новый столбец узлов между узлами интереса и узлами задачи и удалите ребра между этими узлами. Для каждого сотрудника в новом столбце вставьте node для каждой задачи (так что каждый сотрудник имеет свой node для каждой задачи). От этих новых узлов к их соответствующей задаче справа добавьте ребро с емкостью 1. От каждого рабочего интереса node к этим рабочим узлам задачи добавьте кромку с емкостью 1 от каждого интереса к каждой заданной задаче.

-

РЕДАКТИРОВАТЬ: Позвольте мне немного прояснить это. Пусть -(n)-> - ребро с n-емкостью.

Раньше у нас была worker-(1)->task для каждой пары рабочих-рабочих с соответствующим интересом. Теперь мы имеем worker-(k)->local interest-(1)->local task-(1)->global task. Теперь вы можете подумать о задаче, сопоставляемой с парой рабочих интересов. Первый край говорит, что для рабочего каждый из его интересов может быть сопоставлен с задачами k. Второй край говорит, что каждый из рабочих интересов может быть сопоставлен только один раз для каждой работы. Третий край говорит, что каждая задача может быть назначена только каждому работнику. Обратите внимание, что вы можете направить несколько потоков от рабочего на локальную задачу (равную размеру пересечения их интересов), но только 1 поток от рабочего до глобальной задачи node из-за третьего края.

-

Также обратите внимание, что мы не можем корректно смешивать это приращение с правилом 1 для требования 5. Тем не менее, мы можем запустить весь алгоритм один раз для каждой емкости {1,2,..., r} для рабочих- > краев интереса. Затем нам нужен способ ранжировать задания. То есть, поскольку мы расслабляем требование 5, мы можем лучше удовлетворить требование 6 и наоборот. Однако есть еще один подход, который я предпочитаю для ослабления этих ограничений.

Лучший подход к релаксации требований (вдохновленный/взятый из templatetypedef)

Когда мы хотим уметь смягчать несколько требований (например, 5 и 6), мы можем моделировать его как проблему минимального расхода min-cost. Это может быть проще, чем инкрементный поиск, описанный выше.

Например, для требования 5 задайте все затраты на фронт равным 0. Мы имеем начальное ребро от источника к рабочему с емкостью, равной worker maximum assignments / (sum of all worker maximum assignments / number of tasks) и со стоимостью 0. Тогда вы можете добавить другое ребро с помощью оставшаяся емкость для этого работника и стоимость 1. Еще одна возможность заключалась бы в использовании каких-то прогрессивных затрат, так что при добавлении задач к работнику расходы на добавление другой задачи к этому пользователю повышаются. Например. вместо этого вы могли бы разделить оставшуюся рабочую нагрузку на отдельные края с затратами 1,2,3,4,....

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

Этот метод также достаточен для обеспечения соблюдения требований 4. Кроме того, вероятно, должны быть сделаны затраты на требование 5, чтобы они были пропорциональны максимальным назначениям работника. Тогда назначение 1 дополнительной задачи для работника с максимальным значением 100 не будет стоить столько же, сколько назначить дополнительный работнику с макс. 2.

Анализ сложности

Пусть n = # of employees, m = # of tasks, k = max interests for a single task/worker, l = # of interests, j = maximum of maximum assignments.

Требование 3 подразумевает, что n = O (m). Предположим также, что l = O(m) и j = O(m).

В меньшем графе (перед изменением для 6) граф имеет n + m + 2 = O(m) вершины и не более n + m + k*min(n, m) = O(km) ребер.

После изменения у него есть 2 + n + n * l + n * m + m = O(nm) вершины и n + k * n + k * m * n + n * m + m = O(kmn) ребра (технически нам может понадобиться j * n + j * l больше узлов и ребер, чтобы не было нескольких ребер от одного node к другому, но это не изменилось бы асимптотическая оценка). Также обратите внимание, что никакая граница не нуждается в емкости > j.

Используя формулу минимального расхода макс-потока, мы можем найти решение в O(VEBlogV), где V = # vertices, E = # edges и B = max capacity on a single edge. В нашем случае это дает O(kjn^2m^2log(nm)).

Ответ 3

Для задач, где найти прямое решение сложно, может быть хорошей идеей использовать алгоритм аппроксимации, функцию evaulation и метод улучшения решения. Существует множество подходов, таких как генетические алгоритмы и имитированный отжиг.

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

С помощью генетических алгоритмов генерируется и оценивается группа из 100 случайных решений, и лучшие сохраняются и "разводятся" для создания решений нового поколения с характеристиками, аналогичными предыдущим поколениям, но с некоторыми случайными мутациями.

При моделированном отжиге вероятность принятия немного худших решений вначале высока, но со временем уменьшается. Это снижает риск застревания на локальном оптимизме на раннем этапе.

Ответ 4

Итак, я подумал об этой проблеме, и я думаю, что вы можете получить хорошее решение (для некоторого определения "хорошего" ), уменьшив его до экземпляра max-cost max-flow (см. this, например). Идея такова. Предположим, что вам предоставлен входной набор заданий J, каждый из которых имеет необходимый набор навыков, а также набор рабочих W, каждый из которых обладает набором талантов. Вы также даете каждому работнику постоянный k_i, который говорит, сколько заданий вам нужно сделать, а также константу m_i, в которой указано максимальное количество заданий, которые вы можете им выделить. Ваша цель - назначить рабочие места работникам таким образом, чтобы каждая работа выполнялась работником, обладающим навыками, ни один работник не выполнял больше заданий m_i, а количество "лишних" работ, выполняемых работниками, сводилось к минимуму, Например, если пять рабочих, каждый из которых хочет выполнить четыре задачи, а загрузка сбалансирована, чтобы два работника выполняли четыре задания, каждый третий, а один - пять, общий избыток один, поскольку один работник сделал еще один чем ожидалось.

Сокращение выглядит следующим образом. На данный момент мы проигнорируем требование балансировки и просто посмотрим, как уменьшить его до максимального потока; мы добавим балансировку нагрузки в конце. Построить граф G с заданным началом node s и потоком node t. Добавьте к этому графику node для каждого задания j и каждого рабочего w. Будет ребро от s до каждого из этих j узлов нулевой стоимости и емкости единицы. Также будет край от каждого w node до t с нулевой стоимостью и емкостью m_i. Наконец, для каждого задания j и рабочего w, если у работника w есть таланты, необходимые для завершения работы j, есть край от j до w с нулевой стоимостью и емкостью один.

Идея состоит в том, что мы хотим направить поток от s до t через узлы j и w таким образом, чтобы каждый поток потока, проходящий через некоторый j node, до w node, означал, что задание j должно быть дано рабочему w. Ограничения емкости на краях от s до j узлов гарантируют, что не более одной единицы потока поступает в j node, поэтому задание назначается не более одного раза. Ограничение емкости на краях от узлов w до node t не позволяет каждому работнику назначаться слишком много раз. Поскольку все емкости являются интегральными, от s до t существует интегральный максимальный поток, и поэтому максимальный поток на этом графе соответствует присвоениям рабочих мест, которые являются законными и не превышают максимальной рабочей нагрузки рабочего. Вы можете проверить, назначены ли все задания, просмотрев общий поток на графике; если он равен количеству заданий, все они были назначены.

Однако эта конструкция не позволяет балансировать нагрузки на рабочую силу. Чтобы исправить это, мы немного изменим конструкцию. Вместо того, чтобы иметь ребро от каждого w node до t, вместо этого для каждого w node добавьте два узла к графу c и e и соедините их следующим образом. Существует край от w_i до c_i с пропускной способностью k_i и нулевой стоимостью, а также идентичный край от c_i до t. Существует также край от w_i до e_i со стоимостью 1 и мощностью m_i - k_i. Существует также край от e_i до t с равной пропускной способностью и нулевой стоимостью.

Интуитивно мы не изменили объем потока, который оставляет какой-либо w node, но мы изменили стоимость этого расхода. Поток, шунтированный на t через c node, свободен, и поэтому рабочий может выполнять задания k_i без каких-либо затрат. Любые задания после этого должны быть проложены через e, что стоит по одному для каждой единицы потока, пересекающего его. Поиск максимального потока в этом новом графике по-прежнему определяет назначение, но обнаружение min-cost max-flow в графе находит назначение, которое минимизирует избыточные задания, разворачиваемые до рабочих.

Потоки минимальной стоимости могут быть решены в полиномиальное время несколькими известными алгоритмами, поэтому, надеюсь, это полезный ответ!