Существует ли алгоритм планирования, который оптимизирует для расписаний “производителя”?
Можно быть знакомы с эссе Paul Graham, "Расписание Производителя, Расписание менеджера". Затруднение эссе - то, что для творческих и технических профессионалов, встречи являются анафемой на производительность, потому что они имеют тенденцию вести для "планирования фрагментации", разбивая свободное время в блоки, которые являются слишком маленькими для получения фокуса, должен был решить трудные проблемы.
В моей фирме мы видели значительные преимущества путем уменьшения объема вызванного разрушения, но алгоритм "в лоб", который мы используем для решения расписаний, не достаточно сложен для обработки больших групп планирования людей хорошо. (*)
То, что я ищу, - то, если существует, любые известные алгоритмы, которые минимизируют это разрушение производительности среди группы производителей N и менеджеров.
В нашей модели,
- Существуют люди N.
- Каждое пи человека является или производителем (Знак) или менеджером (Mg).
- У каждого человека есть СИ расписания.
- Общее расписание является часами H долго.
- Расписание состоит из серии неперекрывающейся СИ интервалов = [h1..., hj].
- Интервал или свободен или занят. Два смежных свободных интервала эквивалентны единственному свободному интервалу, который охватывает обоих.
- Производительность P для каждого человека является значением между 0 и 1.
- Производительность производителя максимизируется, когда количество свободных интервалов минимизировано.
- Производительность производителя равна 1 / (макс. [1, количество свободных интервалов]).
- Производительность менеджера максимизируется, когда общий отрезок свободного времени максимизируется, но им нравятся длинные фрагменты между встречами больше, чем короткие перерывы.
- Производительность менеджера равна сумме квадратов длин каждого свободного интервала как пропорция дня. Таким образом, (h1/si)2 + (h2/si)2 +..., где каждый интервал является свободным интервалом.
- Цель: Максимизируйте совокупную продуктивность команды.
Заметьте, что, при отсутствии встреч, и производители и менеджеры испытывают оптимальную производительность. Если встречи должны быть запланированы, то производители предпочитают, чтобы встречи произошли спина к спине, в то время как менеджеры не заботятся, куда встреча идет. Обратите внимание, что, потому что все разрушения рассматривают как одинаково вредные для производителей, нет никакого различия между встречей, которая длится 1 секунду и встречу, которая длится 3 часа, если она сегментирует доступное бесплатно время.
Проблема состоит в том, чтобы решить, как к расписанию M различные встречи, включающие произвольные числа людей N, куда каждый человек на данной встрече должен поместить занятый интервал в их расписание, таким образом, что это не накладывается ни с каким другим занятым интервалом. Для каждой встречи Mt время начала для занятого интервала должно быть тем же для всех сторон.
Алгоритм существует для решения этой проблемы или одного подобного ей? Моя первая мысль была то, что это выглядит действительно подобным дефрагментации (минимизируйте количество отличных блоков), и существует много алгоритмов об этом. Но дефрагментация не имеет непосредственное отношение к планированию. Мысли?
(*) Практически говорящий это не действительно проблема, потому что редко, чтобы у нас были встречи больше чем с ~5 людьми сразу, таким образом, пространство возможностей является небольшим.
4 ответа
Хорошее приближение для этого может быть получено с помощью генетического алгоритма.
Напишите функцию для создания случайных графиков из 1000 выборок, случайным образом распределяющих производителей и менеджеров.
Напишите другую функцию (функция фитнеса), которая назначает недостатки графикам с проблемами (люди работают одновременно, недостаточно производителей, недостаточно менеджеров, кто-то недостаточно работал, кто-то работал слишком много).
foreach schedule assign calculate fitness keeping a reference to the lowest scoring (best) schedule.
while (best schedule > minimum fitness value)
foreach schedule s in population of schedules
foreach time slot
if (random < .5)
choose value from best schedule
else
choose value from schedule s
end if
end foreach
score schedule s with fitness function
end foreach
end while
Пока этот метод не дает оптимального расписания и имеет возможность нахождения локальных минимумов. Он всегда будет составлять расписание, и вы всегда можете добавить дополнительные ограничения к функции фитнеса для любых условий, которые вы не хотите видеть. Этот тип алгоритма может обрабатывать множество различных типов задач удовлетворения ограничений.
Я лично использовал аналогичный алгоритм, чтобы составить график работы дошкольного учреждения Wifes Co-Op на весь год примерно за два часа на моем ноутбуке.
Эта проблема выглядит достаточно сложной, чтобы быть NP, но я думаю, что она допускает некоторые приличные приближения.
В частности, я думаю, что вы, вероятно, сможете достаточно хорошо справиться с оптимизацией размера собрания , когда вы оптимально разместите самую большую встречу (с точки зрения количества создателей, которые должны присутствовать, поскольку именно они вы пытаетесь не мешать), а затем делайте это последовательно с небольшими встречами. Чтобы разорвать связи на небольших собраниях одинаковой продолжительности, вы можете взвесить собрания, исходя из загруженности собраний организаторов, которых просят принять участие (чтобы у вас был шанс оптимизировать их и не сделать их жизнь намного хуже).
Теперь вы разбили задачу на одну встречу, так как любая запланированная встреча фактически просто сократит расписание человека.И решение довольно простое: оптимальное решение - это решение, согласованное с максимальным количеством краев графиков производителей, чтобы каждый мог успеть за это время. Вы сможете решить эту проблему даже с помощью грубой силы, например, O ((k + g) * k * n) , где k - количество производителей, g количество менеджеров и n типичное количество интервалов в расписании производителя.
Единственная проблема была бы в том, если бы такой прямой подход приводил к встречам, которые не могли быть удовлетворены. В этом случае вы можете повысить приоритет этого собрания на один или несколько слотов и попробовать еще раз.
Я помню, как реализовал нечто очень похожее на вашу проблему с Алгоритм поиска *. Вы легко найдете несколько доступных реализаций алгоритма, но для того, чтобы применить его к задаче планирования, вам нужно будет построить дистанционные и эвристические функции на основе вашей модели и разбить непрерывное время на фрагменты.
Попробуйте взглянуть на Simulated Annealing. Это похоже на генетические алгоритмы, как описывает Джереми Э., но вместо случайной генерации вашего начального набора расписаний вы начинаете с некоторого действительного, но неоптимального расписания. Идея состоит в том, чтобы сгенерировать некоего «соседа» исходного расписания путем случайного перетасовки некоторых встреч, а затем проверить пригодность перед повторением.
S' = Starting Schedule
S = S'
while( Fitness( S ) < Minimum Fitness )
{
NS = Neighbor( S )
if( Fitness( NS ) > Fitness( F ) )
{
S = NS
}
}
Return( S )
Вместо тестирования некоторого минимального уровня пригодности вы также можете указать заданное количество итераций, чтобы можно было детерминированно сказать, когда программа завершит выполнение.
Особенность этого алгоритма в том, что конечный результат имеет тенденцию выглядеть как начальное состояние, поэтому, если вы хотите взвесить, скажем, большое собрание (с точки зрения размера организаторов) в начале дня, вы можете это сделать.