Проблема планирования работы

Question

Я работаю над приложением, в котором мне нужно автоматически планировать задания для участников по чередующемуся графику. Я не очень хорош в объяснении правил, поэтому вот некоторые данные, которые могут вам помочь:

Должности: должность, с такими правилами, как понедельник и среда еженедельно.
Категории: Набор позиций
Группы: еще один набор позиций. Позиции в одной группе не могут быть назначены в один и тот же день
Члены: пользователи, назначенные на должности на определенную дату.

Для каждой даты месяца члены назначаются на позиции (обе в порядке возрастания). Если член назначен на позицию в одной категории, в следующий раз, когда появится позиция в той же категории, назначается следующий член в алфавитном порядке (или начало списка), например.

Члены: 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, но псевдокод также будет работать.

Answer 1

Мое решение: Вам нужен PriorityQueue (который доступен в PHP под SplPriorityQueue). PriorityQueue дает вам элементы с нисходящим приоритетом (отсортированы по значениям, наименьшее значение имеет наивысший приоритет).

Каждый член получает назначенное значение. Это значение представляет собой число ASCII с n цифрами (для удобства можно использовать 8 цифр), заполненное нулями до n позиций. После этого вы добавляете имя. Вы также добавляете к каждому члену доступные позиции

Итак (n = 5):

• Значение M1: 99999Альберт P1, P2, P3
• Значение M2: 99999Susi P1, P2
• Значение M3: 99999Bob P1, P3

Это упрощает сортировку членов по приоритету и имени.

Приготовление:

Солнечный день. Вы получаете назначенные позиции и категорию для данного дня. Каждый участник загружается в длинный список. Каждый участник, который не появляется на работе, не загружается, но его значение уменьшается на минус два. Боба здесь нет, поэтому его новое значение получает 99997 Боб. Это означает, что Боб будет выбран автоматически в следующий раз. У всех остальных участников их ценность уменьшается на минус один.

Отображаются позиции, назначенные для определенного дня (используйте SplObjectStorage):

P1-> M1, M2, M3, M4 и т. Д. P2-> и т. Д.

Карта содержит только позиции, которые должны быть назначены в этот день. После

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

Назначение:

• Вы выбираете позицию для назначения
• Получить список членов, которые могут заполнить позицию
• Удалить доступных участников из списка и поместить их в PriorityQueue
• Назначить позицию извлечением () из PriorityQueue (правильное назначение сделано переключающийся автоматически). Каждый член, которому назначена воля, получает свою ценность, увеличенную на один (так что уменьшайте и увеличивайте уровни, если вы здесь и работаете). Если вы находитесь здесь и не назначены на должность по какой-либо причине, вы получите небольшое наказание один. Если вы не здесь, вы получите штраф в два раза.
• После завершения снова оставьте остальных участников в списке, очистите PQueue и продолжить со следующим заданием.

Предостережения:

• Вы должны быть осторожны, чтобы на должность всегда было достаточно людей.

Answer 2

уфф. Я не следую вашему описанию, но в подобных ситуациях я использовал sql для решения такого рода проблем. если вы используете php, я думаю, у вас есть sql доступны.

Я хотел бы предложить найти способ хранения этой информации в виде набора таблиц, а затем выяснить, какой SQL-запрос даст вам желаемый ответ. довольно часто это проще сделать в sql, чем на процедурном языке.

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

Answer 3

Что я понимаю, так это «m» членов и «n» позиций.

Категория: группа позиций - член, которому назначена одна позиция в категории, не может иметь другую?

Группа: группа позиций - позиции в одной и той же группе должны назначаться в разные дни.

И последнее, у Позиции есть список членов, которые могут ее заполнить.

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

Фактическое назначение: иметь счетчик дней = 0 и выполнять итерацию по позициям. Для каждой позиции P итерируйте элементы, которые могут ее заполнить. Член М может заполнить позицию, если:

• Любая позиция, которую он занимал, P2 не делит категорию с P.
• Любая позиция, которую он заполнил P2 днем ​​= daycounter, не делит группу с P.

Если он может заполнить позицию, пара [позиция, день] добавляется к члену, и узел члена перемещается в КОНЕЦ списка (именно поэтому ссылки необходимы - все ссылки по-прежнему действительны хотя узел переехал). Это гарантирует, что «пропущенным» участникам будет предоставлен самый высокий приоритет, а участникам, которые не были достигнуты, будет присвоен следующий самый высокий приоритет.

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

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