Алгоритм фильтрации перестановки/ограничения рабочего/Временного интервала
Что относительно .mp3 образца Розового Шума на повторении?
3 ответа
Хорошо, я не знаю о конкретном алгоритме, но вот что я хотел бы принять во внимание.
Оценка
Независимо от метода, вам понадобится функция для оценки того, как ваше решение удовлетворяет ограничениям. Вы можете использовать подход «сравнения» (нет общей оценки, но способ сравнить два решения), но я бы рекомендовал оценку.
Было бы действительно хорошо, если бы вы могли получать оценку за более короткий промежуток времени, например, ежедневно , это действительно полезно для алгоритмов, если вы можете «предсказать» диапазон окончательной оценки на основе частичного решения (например, только первые 3 дня из 7). Таким образом, вы можете прервать вычисление на основе этого частичного решения, если оно уже слишком мало, чтобы оправдать ваши ожидания.
Симметрия
Вероятно, что среди этих 200 человек у вас схожие профили: то есть люди с одинаковыми характеристиками (доступность, опыт, готовность, ...). Если вы возьмете двух человек с одинаковым профилем, они будут взаимозаменяемыми:
- Решение 1: (смена 1: Джо) (смена 2: Джим) ... только другие работники ...
- Решение 2: (смена 1: Джим) (смена 2: Джо) ... только другие работники ...
на самом деле такое же решение с вашей точки зрения.
Хорошо то, что обычно у вас меньше профилей, чем человек, что очень помогает с затратами времени на вычисления!
Например, представьте, что вы сгенерировали все решения на основе решения 1, тогда нет необходимости вычислять что-либо на основе решения 2.
Iterative
Вместо того, чтобы создавать сразу все расписание, вы можете рассмотреть возможность создания его постепенно (скажем, 1 неделю за раз). Чистая выгода состоит в том, что сложность на неделю снижается (меньше возможностей).
Затем, когда у вас есть эта неделя, вы вычисляете вторую, стараясь принять во внимание первое для ваших ограничений конечно.
Преимущество заключается в том, что вы явно разрабатываете свой алгоритм с учетом уже использованного решения, таким образом, при следующем создании расписания он не заставит человека работать 24 часа подряд!
Сериализация
Вам следует подумать о сериализации ваших объектов решения (выберите ваш выбор, pickle вполне подходит для Python). При создании нового вам понадобится предыдущее расписание, и я уверен, что вы не стали бы вводить его вручную для 200 человек.
Исчерпывающий
Теперь, после всего этого,
Я пробовал реализовать это с помощью генетического алгоритма, но, похоже, не может настроить его правильно, поэтому, хотя основной принцип, кажется, работает в одну смену, он не может решить даже простые дела с несколькими сменами и несколькими рабочими.
Короче говоря, не надо! Если у вас нет большого опыта работы с генетическими алгоритмами, вы не поймете это правильно.
- Это приблизительные методы, которые не гарантируют сходимость к работоспособному решению.
- Они работают, только если вы можете достаточно хорошо определить качество вашего текущего решения (т. Е. Количество невыполненных критериев).
- Их качество в значительной степени зависит от качества операторов, которые вы используете для комбинирования / преобразования предыдущих решений в новые.
Трудно разобраться в небольшой программе на Python, если у вас почти нулевой опыт работы с GA. Если у вас небольшая группа людей, исчерпывающий поиск - неплохой вариант. Проблема в том, что это может работать правильно для n человек, будет медленным для n + 1 человек и будет невыносимо медленным для n + 2 , и вполне может быть, что ваш n в конечном итоге окажется ниже 10.
Вы работаете над NP-полной проблемой, и нет простых выигрышных решений. Если сложная задача планирования расписания по вашему выбору не работает достаточно хорошо, очень маловероятно, что у вас будет что-то лучше с вашим скриптом python.
Если вы настаиваете на том, чтобы делать это через свой собственный код, это много легче получить результаты с минимальным и максимальным отжигом или имитацией отжига.
У меня нет выбора алгоритма, но я могу поделиться некоторыми практическими соображениями.
Поскольку алгоритм имеет дело с отменами, он должен запускаться всякий раз, когда возникает исключение расписания, чтобы перенести всех.
Учтите, что некоторые алгоритмы не очень линейны и могут радикально изменить расписание всех с этого момента. Вы, вероятно, захотите этого избежать, люди любят знать свое расписание заранее.
Вы можете иметь дело с некоторыми отменами без повторного запуска алгоритма, потому что он может заранее запланировать следующего доступного человека или двух.
Может оказаться невозможным или нежелательным всегда генерировать наиболее оптимальное решение, но вы можете вести постоянный подсчет «неоптимальных» событий на одного рабочего и всегда выбирать рабочего с наименьшим количеством, когда вам нужно назначить другой "