Существует ли алгоритм планирования, который оптимизируется для "составления расписаний"?

Возможно, вы знакомы с эссе Пола Грэма, Расписание производителей, расписание диспетчеров. Суть эссе заключается в том, что для творческих и технических специалистов встречи являются анафемой производительности, потому что они, как правило, приводят к" фрагментации графика", разбивая свободное время на куски, которые слишком малы, чтобы получить фокус, необходимый для решения сложных проблем.

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

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

В нашей модели

Есть люди N.
Каждый человек p _i является либо создателем (Mk), либо менеджером (Mg).
У каждого человека есть расписание s _i.
Все расписание длится H часов.
Расписание состоит из серии неперекрывающихся интервалов s _i= [h ₁,..., h _j].
Интервал является свободным или занятым. Два соседних свободных интервала эквивалентны одному свободному интервалу, который охватывает оба.
Производительность P для каждого человека - это значение от 0 до 1.
- Производительность производителя максимизируется, когда количество свободных интервалов минимизируется.
- Производительность производителя равна 1/(max [1, количество свободных интервалов]).
- Производительность менеджера максимизируется, когда общая длина свободного времени максимизируется, но они любят длинные отрезки между встречами больше, чем короткие перерывы.
- Производительность менеджера равна сумме квадратов длин каждого свободного интервала как часть дня. То есть, (h ₁/s _i) ² + (h ₂/s _i) ² +..., где каждый интервал является свободным интервалом.
Цель: максимизировать общую производительность команды.

Обратите внимание: если нет встреч, как производители, так и менеджеры получают оптимальную производительность. Если встречи должны быть запланированы, тогда производители предпочтут, чтобы встречи проходили параллельно друг другу, а менеджерам все равно, куда идет собрание. Обратите внимание, что, поскольку все сбои рассматриваются как одинаково вредные для создателей, нет разницы между собранием, которое длится 1 секунду и собрание, которое длится 3 часа, если оно сегментирует свободное время.

Задача состоит в том, чтобы решить, как планировать M разных встреч с произвольными числами N людей, где каждый человек на заданном собрании должен помещать занятый интервал в свое расписание таким образом, чтобы он не пересекался с каким-либо другим интервалом занятости. Для каждой встречи M _t время начала интервала занятости должно быть одинаковым для всех сторон.

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

(*) Практически это не проблема, потому что редко встречаются встречи с более чем 5 людьми одновременно, поэтому пространство возможностей невелико.

Ответ 1

Хорошее приближение для этого можно получить с помощью генетического алгоритма.

Напишите функцию для создания 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 в течение всего года примерно через два часа на моем ноутбуке.

Ответ 2

Эта проблема выглядит достаточно сложно, чтобы быть NP, но я думаю, что она допускает некоторые приличные аппроксимации.

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

Теперь вы нарушили проблему, чтобы запланировать единую встречу, поскольку любое запланированное собрание фактически просто сократит расписание для пользователя. И решение довольно просто: оптимальным решением является тот, который выровнен с максимальным количеством ребер графиков разработчиков, чтобы каждый мог сделать это время. Вы должны решить эту проблему даже с грубой силой примерно в O((k+g)*k*n), где k - количество создателей, g количество менеджеров и n типичное количество интервалов в расписании производителя.

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

Ответ 3

Попробуйте взглянуть на Simulated Отжиг. Он похож на генетические алгоритмы, описанные Джереми E, но вместо случайного создания стартового набора расписаний вы начинаете с некоторого действительного, но не оптимального графика. Идея состоит в том, чтобы сгенерировать некоторый "сосед" исходного расписания, случайным образом перетасовывая вокруг некоторого времени встречи, а затем тестируя фитнес перед итерацией.

S' = Starting Schedule
S = S'    
while( Fitness( S ) < Minimum Fitness ) 
{
    NS = Neighbor( S )
    if( Fitness( NS ) > Fitness( F ) )
    {
         S = NS
    }
}
Return( S )

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

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

Ответ 4

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