Programación algoritmo

Question

tengo un problema de programación donde las nuevas ofertas de trabajo (conjuntos de tareas cuya ejecución está conectado de forma secuencial) llegan cada pocos segundos o menos.
Cada trabajo requiere algunos recursos que se asignen a intervalos conocidos.
Por ejemplo:
Trabajo j1 es un conjunto de tareas para las que reservar recursos {r1, r2, r3} en un patrón de programación conocido: ser

r1:[t0 .. t1=t0+td1], 
r2:[t2=t1+td2+i2 .. t3=t2+td3] 

• t0 el tiempo de inicio de la ejecución
• TD1 es la longitud de la asignación de recursos para r1
• t1 siendo el tiempo de finalización de la asignación de recursos para r1
• i1 es la longitud de el perioido de espera entre r1, r2, etc.

En el ejemplo, se está programado un nuevo trabajo J2 justo después de la ejecución J1 ha comenzado. La hora de inicio más temprana para j2 es t1. Un trabajo puede tardar unos minutos de la ejecución de la mayoría de los cuales consiste en espera.

que tienen un planificador que se ve en la tabla de reserva actual y decide que es el momento temprana posible para empezar un nuevo trabajo con tiempos de asignación fija y períodos de espera y hace las reservas en consecuencia.

(Pero en realidad, el período de espera en realidad no necesita ser reparado, pero dentro de un porcentaje (tal vez 5%) y puede haber alternativas al uso de recursos, por ejemplo, si se reserva el recurso r3.1, luego 3.2 se puede usar como tal para lograr lo mismo.)

Sin embargo, si se requiere el planificador (sí, se sugiere) para poder ajustar dinámicamente todas las asignaciones de programación cuando llega un nuevo trabajo para maximizar la trabajo total realizado (en un día) aprovechando el hecho de que los tiempos de espera no tienen que ser exactamente como se da y la posibilidad de ejecución en paralelo con algunos duplicados resrouce (3.1/3.2), entonces estaría mirando a una completamente diferente esquema de programación (que mi enfoque actual de inicio tan pronto como sea posible).

1. ¿Qué esquema de programación llamarías entonces?
2. Cualquier sugerencia acerca de acercarse a la (nueva) problema?

Answer 1

En cuanto a su pregunta sobre "alternativas a la utilización de recursos":

El patrón más comúnmente implementado para hacer frente a ese tipo de problema es el Object Pool Pattern
El ejemplo más conocido de esto probablemente es el ThreadPool

que sugieren que implemente una clase ResourcePool con un método int GetResource(ResourceType type, int durationInSeconds). El valor de retorno indica que el siguiente recurso de lo dado ResourceType estará disponible

Answer 2

Usted podría estar tratando con el RCPSP (recursos limitados Programación de proyectos Problema). Las técnicas de solución van desde la programación entera y la programación de restricciones hasta varias heurísticas.La técnica depende de los detalles, como la planificación horizonte, cómo las tareas/trabajos utilizan recursos/acción, lo rápido que se necesita un programa de solución, etc.

véase:

https://developers.google.com/optimization/scheduling/job_shop

http://www.laas.fr/files/ROC/2014-Presentations/MILP-RCPSP-PMS2014.pdf