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

Question

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

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

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

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

• Есть N человек.
• Каждый человек p _i является либо производителем ( Mk ), либо менеджером (* 1030) * Мг * * тысяча тридцать одна). * * одна тысяча тридцать-две
• У каждого человека есть расписание с _i .
• У каждого человека расписание Ч часов.
• Расписание состоит из серии непересекающихся интервалов с _i = [ ч ₁ , ..., ч _J * *] 1055.
• Интервал либо свободен , либо занят . Два смежных свободных интервала эквивалентны одному свободному интервалу, который охватывает оба.
• Производительность P для каждого человека составляет от 0 до 1.
  • Производительность производителя максимизируется, когда количество свободных интервалов минимизировано.
  • Производительность производителя равна 1 / (максимум [1, количество свободных интервалов]).
  • Производительность менеджера максимизируется, когда максимизируется общая продолжительность свободного времени, но им нравятся длинные перерывы между заседаниями, а не короткие перерывы.
  • Производительность менеджера равна сумме квадратов длин каждого свободного интервала в виде доли дня. То есть ( ч ₁ / с _i ) ² + ( ч ₂ / с _i ) ² + ..., где каждый интервал является свободным интервалом.
• Цель: Максимизировать общую производительность команды.

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

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

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

<Ч />

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

Answer 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 на весь год примерно за два часа на моем ноутбуке.

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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