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

Ответ 1

Наконец, я использовал простой список для моих элементов очереди и базу данных SQLite в памяти для хранения пустых слотов, потому что многомерные запросы и обновления очень эффективны с SQL. Мне нужно только сохранить начальные, длинные и индексы полей в таблице.

Ответ 2

class Task:
    name=''
    duration=0
    resources=list()

class Job:
    name=''
    tasks=list()

class Assignment:
    task=None
    resource=None
    time=None

class MultipleTimeline:
    assignments=list()
    def enqueue(self,job):
        pass
    def put(self,job):
        pass
    def delete(self,job):
        pass
    def recalculate(self):
        pass

Это первый шаг в том направлении, которое вы ищете, т.е. модель данных, написанная на Python?

Update:

Настоящая моя более эффективная модель:

В основном он помещает все Задачи в связанный список, упорядоченный по времени.

class Task:
    name=''
    duration=0    # the amount of work to be done
    resources=0   # bitmap that tells what resources this task uses
# the following variables are only used when the task is scheduled
    next=None     # the next scheduled task by endtime
    resource=None # the resource this task is scheduled
    gap=None      # the amount of time before the next scheduled task starts on this resource

class Job:
    id=0
    tasks=list() # the Task instances of this job in order 

class Resource:
    bitflag=0       # a bit flag which operates bitwisely with Task.resources
    firsttask=None  # the first Task instance that is scheduled on this resource
    gap=None        # the amount of time before the first Task starts

class MultipleTimeline:
    resources=list()
    def FirstFreeSlot():
            pass
    def enqueue(self,job):
        pass
    def put(self,job):
        pass
    def delete(self,job):
        pass
    def recalculate(self):
        pass

Из-за обновлений enqueue и put я решил не использовать деревья. Из-за put, который перемещает задачи во времени, я решил не использовать абсолютные времена.

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

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

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

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

Ответ 3

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

Свободные временные интервалы живут в двухмерном пространстве: одно измерение - это время начала s, другое - длина d. FirstFreeSlot (D) эффективно отвечает на следующий запрос:

min s: d >= D

Если мы рассматриваем s и d как декартово пространство (d = x, s = y), это означает поиск нижней точки в подплане, ограниченной вертикальной линией. A quad-tree, возможно, с некоторой вспомогательной информацией в каждом node (а именно, min s по всем листам), поможет эффективно ответить на этот запрос.

Для Enqueue() перед ограничениями ресурсов рассмотрите возможность сохранения отдельного четырехъядерного дерева для каждого ресурса. Квадратное дерево может также отвечать на запросы типа

min s: s >= S и d >= D

(требуется для ограничения начальных данных): теперь прямоугольник (открытый в левом верхнем углу) обрезается, и мы смотрим на min s в этом прямоугольнике.

Put() и Удалить() - это простые операции обновления для четырехъядерного дерева.

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

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

Ответ 4

Потратьте некоторое время на это. Я думаю, что сегментное дерево может быть более подходящим для моделирования этой очереди временной шкалы. Концепция работы похожа на структуру данных LIST.

Я предполагаю, что задача может быть смоделирована так (PSEUDO CODE). Последовательность задач в задании может быть гарантирована start_time.

class Task:
    name=''

    _seg_starttime=-1; 
    #this is the earliest time the Task can start in the segment tree, 
    #a lot cases this can be set to -1, which indicates its start after its predecessor,
    #this is determined by its predecessor in the segment tree.
    #if this is not equal -1, then means this task is specified to start at that time
    #whenever the predecessor changed this info need to be taken care of

    _job_starttime=0; 
    #this is the earliest time the Task can start in the job sequence, constrained by job definition

    _duration=0;      
    #this is the time the Task cost to run

    def get_segstarttime():
       if _seg_starttime == -1 :
           return PREDESSOR_NODE.get_segstarttime() + _duration
       return __seg_startime + _duration

    def get_jobstarttime():
       return PREVIOUS_JOB.get_endtime()

    def get_starttime():
       return max( get_segstarttime(), get_jobstarttime() )

• Enqueue просто добавляет задачу node в дерево сегментов, замечает, что _seg_startime установлен в -1, чтобы указать, что он запускается сразу после его предшественника
• Поместите вставить сегмент в дерево, сегмент обозначается start_time и длительностью.
• Удалить удалить сегмент в дереве, при необходимости обновить его преемник (скажем, если у удаленного node есть _seg_start_time присутствует)
• Пересчитать, вызывающий get_starttime() снова, он получит самое раннее время начала.

Примеры (без учета ограничения работы)

                  t1.1( _segst = 10, du = 10 )
                      \
                      t2.2( _segst = -1, du = 10 ) meaning the st=10+10=20
                        \
                        t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30

если мы сделаем Put:

                    t1.1( _segst = 10, du = 10 )
                        \
                        t2.2( _segst = -1, du = 10 ) meaning the st=20+10=30
                        /  \
t2.3(_segst = 20, du = 10)  t1.3 (_segst = -1, du = 10 ) meaning the st = 30+10 = 30

если мы выполним сценарий "Удалить t1.1 в исходный"

                      t2.2( _segst = 20, du = 10 ) 
                        \
                        t1.3 (_segst = -1, du = 10 ) meaning the st = 20+10 = 30

Каждый ресурс может быть представлен с использованием 1 экземпляра этого дерева интервалов яйцо.

с точки зрения сегмента (временной шкалы):

t1.1                      t3.1
  \                        / \
  t2.2                  t2.1  t1.2

с точки зрения работы:

t1.1 <- t1.2
t2.1 <- t2.2
t3.1

t2.1 и t2.2 подключены с использованием связанного списка, как указано: t2.2 получить свой _sg_start_time из дерева сегментов, получить его _job_start_time из связанного списка, сравнить два момента, а затем самое раннее время, когда оно могло может быть получен.