Предварительное планирование повторяющихся задач

Question

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

Например, если нам даны ограничения {(a, 2), (b, 2)}, лучшим графиком будет «ab ab ab ...» С другой стороны, если нам дадут ограничения ({a, 2}, {b, 5}, {c, 5}), лучшим графиком, вероятно, будет «abaca abaca abaca ...»

В настоящее время мы находим наилучшее расписание, выполняя генетический алгоритм, который пытается минимизировать расстояние между фактическими частотами и заданными ограничениями. На самом деле это работает довольно хорошо, но мне интересно, есть ли какой-нибудь алгоритм, который лучше подходит для такого рода проблем. Я пытался выполнить поиск в Google, но мне, кажется, не хватает нужных слов (планирование обычно связано с выполнением задач :(). Вы можете помочь?

Answer 1

Прежде всего, рассмотрите достоинства комментария jldupont! :)

Во-вторых, я думаю, что точка - это точное описание второго элемента кортежа, например, {Name, Period [icity]}.

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

Например, учитывая N задач, создайте N очередей, соответствующих задачам T0...Tn, и в каждом цикле («отметка»), основываясь на периоде задачи, ставьте элемент в очередь.

Затем алгоритм планировщика будет стремиться минимизировать (в среднем) общее количество официантов в очередях. Простой отправной точкой будет простое удаление из квен Qx с наибольшим количеством предметов. (Параметр на элементе в очереди, указывающий «возраст», помог бы в расстановке приоритетов.)