python - prioridad - Implementando una cola dinámica de múltiples líneas de tiempo

pila en python 3

Question

Introducción

Me gustaría implementar una cola dinámica de múltiples líneas de tiempo . El contexto aquí es la programación en general.

¿Qué es una cola de línea de tiempo ?

Esto sigue siendo simple: es una línea de tiempo de tareas, donde cada evento tiene su hora de inicio y finalización. Las tareas se agrupan como trabajos. Este grupo de tareas debe preservar su orden, pero puede moverse en el tiempo como un todo. Por ejemplo, podría ser representado como:

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

Yo implementaría esto como una cola de almacenamiento dinámico con algunas restricciones adicionales. El módulo de programación de Python tiene algunos enfoques básicos en esta dirección.

Definición de cola de línea de tiempo múltiple

Una cola representa un recurso y una tarea necesita un recurso. Ejemplo grafico:

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

Explicando " dinámico "

Se vuelve interesante cuando una tarea puede usar uno de los múltiples recursos. Una restricción adicional es que las tareas consecutivas, que pueden ejecutarse en el mismo recurso, deben usar el mismo recurso.

Ejemplo: si (desde arriba) la tarea t1.3 puede ejecutarse en R1 o R2 , la cola debería verse así:

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

Funcionalidad (en orden de prioridad)

• FirstFreeSlot (duration, start) : encuentra el primer intervalo de tiempo libre que comienza desde el start donde hay tiempo libre para la duration (consulte la explicación detallada al final).
• Encoque un trabajo lo antes posible en los múltiples recursos considerando las restricciones (principalmente: orden correcto de tareas, tareas consecutivas en el mismo recurso) y utilizando FirstFreeSlot .
• Pon un trabajo a una hora específica y mueve la cola hacia atrás
• Eliminar un trabajo
• Recalcular : después de eliminar, compruebe si algunas tareas se pueden ejecutar antes.

Pregunta clave

El punto es: ¿Cómo puedo representar esta información para proporcionar la funcionalidad de manera eficiente ? La implementación depende de mí ;-)

Actualización : Otro punto a considerar: las estructuras típicas de intervalo se centran en "¿Qué hay en el punto X?" Pero en este caso la enqueue y por lo tanto la pregunta "¿Dónde está la primera ranura vacía para la duración D?" es mucho mas importante Por lo tanto, un árbol de segmentos / intervalos o algo más en esta dirección probablemente no sea la elección correcta.

Para elaborar el punto con las ranuras libres aún más: debido al hecho de que tenemos múltiples recursos y la restricción de tareas agrupadas, puede haber ranuras de tiempo libre en algunos recursos. Ejemplo simple: t1.1 ejecuta en R1 para 40 y luego t1.2 ejecuta en R2. Por lo tanto, hay un intervalo vacío de [0, 40] en R2 que se puede completar con el siguiente trabajo.

Actualización 2 : Hay una propuesta interesante en otra pregunta de SO . Si alguien puede trasladarlo a mi problema y mostrar que está funcionando en este caso (especialmente elaborado para múltiples recursos), esta sería probablemente una respuesta válida.

Answer 1

Después de pasar algún tiempo pensando en esto. Creo que un árbol de segmentos podría ser más apropiado para modelar esta cola de la línea de tiempo. El concepto de trabajo es como una estructura de datos LIST.

Supongo que la tarea se puede modelar así (CÓDIGO DE PSEUDO). La secuencia de las tareas en el trabajo puede ser asegurada por el tiempo de inicio.

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() )

• Encolar es simplemente agregar un nodo de tarea en el árbol de segmentos, observe que _seg_startime se establece en -1 para indicar que se inicie justo después de su predecesor
• Colocar insertar un segmento en el árbol, el segmento se indica mediante start_time y duration.
• Eliminar eliminar el segmento en el árbol, actualizar su sucesor si es necesario (por ejemplo, si el nodo eliminado tiene un _seg_start_time presente)
• Recalcular llamando a get_starttime () nuevamente obtendrá directamente su hora de inicio más temprana.

Ejemplos (sin considerar la restricción de trabajo)

                  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

Si hacemos un 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

Si hacemos un Delete t1.1 al escenario original.

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

Cada recurso podría representarse utilizando 1 instancia de este huevo de intervalo.

Desde la perspectiva del árbol de segmentos (línea de tiempo):

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

desde la perspectiva del trabajo:

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

t2.1 y t2.2 se conectan mediante una lista vinculada, como se indica: t2.2 obtiene su _sg_start_time del árbol de segmentos, obtiene su _job_start_time de la lista vinculada, compara las dos veces y la hora más temprana en que se puede ejecutar. derivado.

Answer 2

Finalmente utilicé solo una lista simple para mis elementos de la cola y una base de datos SQLite en la memoria para almacenar las ranuras vacías, porque la consulta y actualización multidimensional es muy eficiente con SQL. Solo necesito almacenar los campos inicio , duración e índice en una tabla.

Answer 3

Limitémonos al caso más simple primero: encuentre una estructura de datos adecuada que permita una implementación rápida de FirstFreeSlot () .

Los intervalos de tiempo libre viven en un espacio bidimensional: una dimensión es la hora de inicio s, la otra es la longitud d. FirstFreeSlot (D) responde efectivamente a la siguiente consulta:

min s: d> = D

Si pensamos en syd como un espacio cartesiano (d = x, s = y), esto significa encontrar el punto más bajo en un subplano delimitado por una línea vertical. Un quad-tree , quizás con alguna información auxiliar en cada nodo (a saber, minutos sobre todas las hojas), ayudará a responder esta pregunta de manera eficiente.

Para Enqueue () en vista de las restricciones de recursos, considere mantener un quad-tree separado para cada recurso. El árbol quad también puede responder a consultas como

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

(requerido para restringir los datos de inicio) de una manera similar: ahora se corta un rectángulo (abierto en la parte superior izquierda), y buscamos los mínimos en ese rectángulo.

Put () y Delete () son simples operaciones de actualización para el quad-tree.

Recalculate () se puede implementar mediante Delete () + Put () . Para ahorrar tiempo para operaciones innecesarias, defina condiciones suficientes (o, idealmente, suficientes + necesarias) para desencadenar un recálculo. El patrón Observer puede ayudar aquí, pero recuerde colocar las tareas para reprogramar en una cola FIFO o en una cola de prioridad clasificada por hora de inicio. (Desea terminar de reprogramar la tarea actual antes de pasar a la siguiente).

En una nota más general, estoy seguro de que es consciente de que la mayoría de los problemas de programación, especialmente aquellos con limitaciones de recursos, están al menos NP-completos. Así que no esperes un algoritmo con un tiempo de ejecución decente en el caso general.

Answer 4

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

¿Es este un primer paso en la dirección que está buscando, es decir, un modelo de datos escrito en Python?

Actualizar:

De esta manera mi modelo más eficiente:

Básicamente, pone todas las tareas en una lista enlazada ordenada por tiempo de finalización.

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

Debido a las actualizaciones en enqueue y put decidí no usar árboles. Debido put las tareas que se mueven en el tiempo, decidí no usar los tiempos absolutos.

FirstFreeSlot no solo devuelve la tarea con la ranura libre, sino también las otras tareas en ejecución con sus tiempos finales.

enqueue funciona de la siguiente manera: buscamos una ranura libre de FirstFreeSlot y programamos la tarea aquí. Si hay suficiente espacio para la siguiente tarea, podemos programarlo también. Si no, mire las otras tareas que se ejecutan si tienen espacio libre. Si no: ejecute FirstFreeSlot con los parámetros de este tiempo y las tareas en ejecución.

Mejoras: si no se usa muy a menudo y se put enqueue desde el tiempo cero, podríamos hacer un seguimiento de las tareas superpuestas incluyendo un dict () por tareas que contiene las otras tareas en ejecución. Entonces también es fácil mantener una lista () por Recurso que contiene las tareas programadas con tiempo absoluto para este Recurso ordenado por tiempo final. Solo se incluyen aquellas tareas que tienen mayores intervalos de tiempo que antes. Ahora podemos encontrar más fácilmente una ranura libre.

Preguntas: ¿Las tareas programadas para put deben ejecutarse en ese momento? En caso afirmativo: ¿Qué sucede si se superpone otra tarea que se va a programar por colocación? ¿Todos los recursos ejecutan una tarea tan rápido?