Реализация динамической очереди с несколькими временными шкалами

Введение

Я хотел бы реализовать динамическую множественную очередь временной шкалы. Контекст здесь планированиев целом.

Что такое очередь временной шкалы?

Это по-прежнему просто: это временная шкала задач, где каждое событие имеет свое время начала и окончания. Задачи сгруппированы как задания. Эта группа задач должна сохранять свой порядок, но ее можно перемещать во времени как единое целое. Например, это может быть представлено так:

 --t1--   ---t2.1-----------t2.2-------
 '    '   '        '                  '
20    30  40       70                120 

Я бы реализовал это как очередь кучис некоторыми дополнительными ограничениями. Модуль Pythonschedимеет несколько основных подходов в этом направлении.

Определение множественная очередь на временной шкале

Одна очередь соответствует ресурсу, а ресурс необходим задаче. Графический пример:

R1  --t1.1----- --t2.2-----      -----t1.3--    
            /  \                /
R2  --t2.1--     ------t1.2-----

Объяснение " динамическое"

Становится интересным, когда задача может использовать один из нескольких ресурсов. Дополнительным ограничением является то, что последовательные задачи, которые могут выполняться на одном и том же ресурсе, должны использовать один и тот же ресурс.

Пример: Если (сверху) задача t1.3может выполняться на R1или R2, очередь должна выглядеть так:

R1  --t1.1----- --t2.2-----      
            /  \                
R2  --t2.1--     ------t1.2----------t1.3--    

Функциональность ( в порядке приоритета)

• FirstFreeSlot(duration, start): Найдите первый свободный временной интервал, начиная с start, где есть свободное время для duration(см. подробное объяснение на конец).
• Поставьтезадание в очередь как можно раньше на нескольких ресурсах, принимая во внимание ограничения (главным образом: правильный порядок задач, последовательные задачи на одном ресурсе) и используя FirstFreeSlot.
• Поместитезадание в определенное время и переместите конец назад
• Удалитьзадание
• Пересчитать: После удаления проверьте, можно ли выполнить некоторые задачи раньше.

Ключевой вопрос

Суть в следующем: как я могу представитьэту информацию, чтобы обеспечить функциональность эффективно? Реализация зависит от меня ;-)

Обновление : Еще один момент для рассмотрения: типичные интервальные структуры сосредоточены на «Что находится в точке X?» Но в этом случае ставится в очередьи, следовательно, вопрос «Где находится первый пустой слот для длительности D?» гораздо важнее.Таким образом, дерево сегментов/интервалов или что-то еще в этом направлении, вероятно, не является правильным выбором.

Чтобы уточнить вопрос со свободными слотами: из-за того, что у нас есть несколько ресурсов и ограничение сгруппированных задач, на некоторых ресурсах могут быть свободные временные интервалы. Простой пример: t1.1запустить на R1 в течение 40, а затем t1.2запустить на R2. Таким образом, на R2 есть пустой интервал [0, 40], который может быть заполнен следующим заданием.

Обновление 2: в другом вопросе SO есть интересное предложение. Если кто-то может перенести его на мою проблему и показать, что он работает для этого случая (особенно разработан для нескольких ресурсов), это, вероятно, будет правильным ответом.