Проблема планирования задания
Я работаю над приложением, где я должен автоматически запланировать задания для участников во вращающемся расписании. Я не очень хорош при объяснении правил, таким образом, вот некоторые данные для выручения:
Положения: должность, с правилами, такими как понедельники и среды еженедельно.
Категории: Ряд положений
Группы: Другой набор положений. Положения в той же группе не могут быть присвоены в тот же день
Участники: Пользователи присвоили позициям по данной дате.
Для каждой даты в месяце, участники присвоены положениям (оба в порядке возрастания). Если участник присвоен положению в одной категории, в следующий раз, когда положение в той же категории подходит, следующему участнику в алфавитном порядке (или начало списка) присваивают, например.
Участники: M1, M2, M3, M4
Положения в категории C1: P1, P2, P3
Участники в положении P1: M1, M2, M3, M4
Участники в положении P2: M1, M2, M3
Участники в положении P2: M1, M3, M4
Если M1 будет присвоен для P1, если P2 прибудет затем, то M2 будет присвоен. Дополнительный слой сложности представлен, где, если P3 прибывает затем вместо этого, M3 присвоен. Система должна отслеживать то, что M2 был 'пропущен', и присвойте M2 затем при наличии, затем присвойте M4 затем или ожидайте, пока это не добирается до положения, где M2 доступен (это становится дополнительно сложным, когда существуют многие 'пропущенные' участники).
Участник будет также пропущен, если он указал, что не будет доступен в ту дату. Система должна поместить приоритет в пропущенных участников, так или иначе определить их, когда они подходят и затем переходят следующему логическому человеку в списке. Пропуск также относится к группам из-за столкновений даты.
У меня уже есть временный файл [и грязный] решение, которое я больше не понимаю даже при том, что у меня есть много комментариев в нем, объясняя каждый шаг. Его слабые места имея дело с пропущенными участниками.
Если бы Вы собирались кодировать это, как Вы пошли бы об этом? Я реализую это в PHP, но псевдокод работал бы также.
3 ответа
Мое решение: Вам нужен PriorityQueue (который доступен в PHP в разделе SplPriorityQueue). ПриоритетQueue дает вам элементы с нисходящим приоритетом (отсортированные по значениям, наименьшим из них значение имеет наивысший приоритет).
Каждый член получает присвоенное значение. Это значение представляет собой ASCII номер с n цифрами (для удобства можно использовать 8 цифр), заполненный нулями к n позициям. После этого вы добавляете имя. Вы также добавляете к каждому члену имеющиеся позиции
Так что (n=5):
- Значение M1: 99999Albert P1,P2,P3
- Значение M2: 99999Susi P1,P2
- Значение M3: 99999Bob P1,P3
Это облегчает сортировку членов по приоритету и названию.
Подготовка:
Солнечный день. Вы извлекаете назначенные позиции и категорию для данного дня. Каждый член загружается в длинный список. Каждый член, который не появляется на работе не загружается, но получает его значение уменьшается на минус два. Боба здесь нет, поэтому его новое значение получает 99997Bob. Это означает, что Боб будет выбран автоматически в следующий раз. Все остальные члены получают уменьшенное на минус единицу их значение.
Позиция, назначенная на конкретный день, картируется (используйте SplObjectStorage):
P1->M1,M2,M3,M4 и т.д. P2-> etc.
Карта содержит только те позиции, которые должны быть назначены на этот день. После фильтра
Фильтр: Вы должны просмотреть группы и удалить все позиции на карте, которые не могут быть назначены в этот день. Описание вашей группы немного неясно.
Назначить:
- Вы выбираете позицию для назначения
- Получить список членов, которые могут заполнить позицию
- Удалить доступных членов из списка и поместить их в PriorityQueue
- Назначить позицию функцией extract() из PriorityQueue (правильное назначение сделано). автоматически). Каждому назначенному члену будет увеличено его значение на один (Так что уменьшайте и увеличивайте уровни, если вы здесь и работаете). Если вы находитесь здесь и не назначены на должность по какой-либо причине, вы получаете небольшое наказание в виде одного. Если вас здесь нет, то вы получаете штраф в два.
- После завершения, снова поместите оставшихся членов в список, очистите PQueue и Продолжайте со следующим заданием.
Caveats:
- Вы должны быть осторожны, чтобы всегда было достаточно людей для должности.
иф. Я не слежу за вашим описанием, но в подобных ситуациях я использовал sql для решения такой проблемы. если вы используете php, я думаю, у вас есть sql.
я бы посоветовал найти способ сохранить эту информацию в наборе таблиц, а затем выяснить, какой sql-запрос даст вам нужный ответ. довольно часто это намного проще сделать в sql, чем на процедурном языке.
, например, для пропущенной части у вас может быть столбец, в котором записывается, когда кто-то был последний раз назначен, а затем упорядочивается по этому (чтобы вы выбираете человека, которого давно не назначили). в качестве альтернативы, вы можете указать количество пропусков в виде столбца и упорядочить его.
Насколько я понимаю, есть "m" членов и "n" должностей.
Категория: группа должностей - член, которому назначена одна должность в категории, не может иметь другую?
Группа: группа должностей - должности в одной и той же группе должны назначаться в разные дни.
Последнее, позиция имеет список членов, которые могут ее заполнить.
Рассматривая это с точки зрения структуры данных, поместите членов в связанный список - каждый член должен иметь дополнительный список [позиция, день], который им, наконец, назначен. Затем, для каждой позиции, иметь список ссылок на членов, которые могут заполнить эту позицию. Реализуйте категории как еще один список ссылок на позицию, в каких категориях она находится.
Реальное назначение: имейте счетчик дней = 0, и итерацию по позициям. Для каждой позиции P выполнить итерацию через членов, которые могут ее заполнить. Член M может заполнить позицию, если:
- Любая позиция, которую он заполнил P2, не делит категорию с P.
- Любая позиция, которую он заполнил P2 днем = счетчик дней, не делит группу с P.
Если он может заполнить позицию, то к члену добавляется пара [позиция, день], и узел члена перемещается в END списка (поэтому необходимы ссылки - все ссылки все равно действительны, даже если узел перемещается). Это гарантирует, что "пропущенные" члены будут иметь наивысший приоритет, а члены, которые не были достигнуты, получат следующий наивысший приоритет.
Как только позиция заполнена, переходите на следующую позицию. Если позиция разделяет группу с уже назначенной позицией, пропустите ее, пропуская через все позиции, пока не сможете назначить как можно больше позиций на 1-й день. Затем прибавите счетчик дней и повторите на второй день. Это должно дать вам максимальное задание (не уверен насчет максимума) для всех заданий.
Совет: при перемещении члена в конец списка, чтобы избежать необходимости пересекать список, держите ссылку на конец - для следующей позиции, вам все равно нужно начинать с начала, так что нет смысла проходить через все это.
.