Генетический алгоритм или имитация отжига для планирования и оптимизации рабочих проектов

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

Я хотел бы быть более точным в этом процессе, поэтому я начал изучать оптимизацию с помощью таких ресурсов, как проблема стабильного брака. В конце концов, я наткнулся на «Генетические алгоритмы» и «Смоделированный отжиг» из задачи Job-Shop, потому что я считаю, что моя проблема оказывается немного сложнее, чем проблема брака с несколькими совпадениями, но я могу ошибаться.

Моя основная проблема настроена как задача оптимизации с множеством ограничивающих критериев.

Рабочие: Джон, Джейн, Дейл и т. д.
Все они также могут иметь несколько ролей (Джон может быть менеджером или рабочим).

Проекты: проект A, проект B, проект C и т. д.
У проектов есть даты начала и окончания.
В идеале у меня есть даты начала и окончания для разных этапов проектов, которые Я хотел бы ограничиться, но подойдет и общая дата начала/окончания. Эти дополнительные даты включают часы, необходимые для каждого типа роли (менеджер 8 часов, рабочий 20 часов и т. д.)

Часы: не более 45 часов на одного сотрудника.

Мой вопрос заключается в том, действительно ли мне нужно использовать GA или симулированный отжиг, или есть более простой процесс. Кроме того, мне не удалось найти псевдокод ни для одного из этих процессов в R.

Спасибо за любую помощь, и я буду рад разъяснить всем, если потребуется дополнительная информация!


person medavis6    schedule 22.10.2015    source источник


Ответы (1)


Вы можете попытаться смоделировать ее как смешанную целочисленную программу, используя, например, пакет lpSolve. У вас будут такие переменные, как john_manager_project_A_week_1 (количество часов, которое Джон работает над проектом А в качестве менеджера в неделю 1), которые должен определить решатель, и линейные ограничения, такие как

john_manager_project_A_week_1 + john_manager_project_B_week_1 + ... <= 45
john_manager_project_A_week_1 + jane_manager_project_A_week_1 + ... >= 8

Эта структура кажется несколько ограниченной, но с помощью некоторых приемов моделирования вы также можете выразить такие условия, как «Джон не может работать одновременно как менеджер и как рабочий над проектом А в течение недели 1».

Решение этих проблем NP-сложно, но решатели, как правило, довольно хороши, и если у вас всего несколько десятков человек, проектов и временных интервалов, это должно быть решаемо. Вы даже можете иметь линейную целевую функцию, которую нужно оптимизировать (например, замените «45» выше на max_work_hours и минимизируйте это).

person Falk Hüffner    schedule 23.10.2015