Scheduling Problem
¿Cuándo y dónde
debo hacer cada
trabajo ?
Ejemplos de problemas de
asignación de recursos
•
•
•
•
•
•
Fabricación de varios tipos de productos
Asignación de turnos de trabajo
Inversión financiera
Transporte de productos con coste mínimo
Asignación de tareas a procesadores
www.cirl.uoregon.edu/rechearch (Aircraft
Assembly, Cable Manufacturing)
Scheduling y Asignación
• Es un problema de optimización
• Orígenes en el comienzo de la Segunda
guerra mundial, debido a la necesidad
urgente de asignación de recursos escasos
en las operaciones militares, en problemas
tácticos y estratégicos
• Primeros resultados debidos a la
Investigación Operativa
Scheduling y Asignación
• Es un problema muy amplio del cual se
pueden derivar distintos subproblemas
según sean las restricciones que se
consideren en cada caso y según sean las
características del caso.
• La mayoría de estos problemas son
problemas NP_completos.
Algunas instancias
NP_completas del problema
MINIMUM MULTIPROCESSOR SCHEDULING
PROBLEMA: Conjunto T de tareas, m procesadores, con longitud
para cada tarea y cada procesador
SE BUSCA : Una planificación en m procesadores para T, i.e., una
función a optimizar
MEDIDA: Tiempo final de la planificación
•Se puede aproximar para m=2
Algunas instancias
NP_completas del problema
MINIMUM PRECEDENCE CONSTRAINED SCHEDULING
PROBLEMA: Conjunto T de tareas, m procesadores, longitud l(t)=1
y un orden parcial en T
SE BUSCA : Una planificación en m procesadores para T, que cumpla
restricciones
MEDIDA: Tiempo final de la planificación.
Algunas instancias
NP_completas del problema
RESOURCE CONSTRAINED SCHEDULING
PROBLEMA: Conjunto T de tareas, m procesadores, longitud l(t)=1,
un número de recursos, r, cada recurso esta limitado por Bi, 1<=I<=r, y
hay unos requerimientos de cada recurso por cada tarea
•SE BUSCA : Una planificación en m procesadores para T, con un
tiempo límite que cumpla las restricciones
Algunas instancias
NP_completas del problema
OPEN SHOP SCHEDULING
PROBLEMA: Sea m el número de procesadores , J un conjunto de trabajos.
Cada trabajo j del conjunto J está compuesto por m tareas, op,j que deben
ejecutarse en el procesador p, con una duración wp,j
SE BUSCA: Un conjunto de funciones de planificación para cada procesador, fp
de J en N, siendo p un número entre 1 y m, que asigna a cada tarea el instante
de tiempo en comenzará a ser ejecuta en el procesador p, tal que fp (j) > fp (j’)
implica que fp (j) >= fp (j’) + wp,j y para j, los intervalos [fp (j) , fp (j)+
wp,json disjuntos
OBJETIVO: Minimizar el tiempo total de las tareas.
Algunas instancias
NP_completas del problema
Job Shop Scheduling
PROBLEMA: Sea un conjunto de trabajos J, un número de máquinas m, cada
trabajo ji está compuesto por un conjunto de tareas{ ti1, ti2, .., tim}que deben ser
ejecutadas en un cierto orden. Cada tarea tij, requiere el uso exclusivo e
ininterrumpido de una de las máquinas durante su tiempo de ejecución duij .
Para cada trabajo hay un tiempo mínimo de inicio y un tiempo máximo de fin
entre los cuales deben ser ejecutadas todas sus tareas
SE BUSCA: Un tiempo de inicio para cada una de las tareas de modo que se
satisfagan todas las restricciones del problema y que además minimice el
tiempo de finalización de las tareas, makespan.
La diferencia con el Open Shop es que este caso fijamos el orden en que las
tareas deben visitar las máquinas
Scheduling
Lista completa de diferentes problemas
NP_completos de planificación en:
• Computers and Intractability: A Guide to
de Theory of NP_Completeness. Michael
R. Garey/ David S.Johnson.
• http://www.nada.kth.se/~viggo/www.comp
endium/node173.html
Soluciones
• Métodos tradicionales: Algoritmos
Voraces, Programación Dinámica, Branch
and Bound
• Heurísticas: métodos aproximados para la
resolución de problemas de optimización
Heurísticas
• Reglas de prioridad (clásicas): Una de las formas de aplicar reglas de
prioridad es ordenar los trabajos de acuerdo con algún criterio, el primer
trabajo de la lista es asignado a la primera máquina que quede libre.
• Ramdon list
• Longest Processing Time (LPT)
• Shortest Processing Time (SPT)
•
Simulated Annealing
•
Genetic Algoritms
•
Búsqueda Tabu
•
Redes Neuronales
Búsqueda Tabú
• Es un procedimiento iterativo para resolver
problemas discretos de optimización combinatoria.
• La idea básica del método es la de explorar el espacio
de búsqueda de todas las soluciones factibles por una
secuencia de movimientos.
• Para escapar de un óptimo local y para prevenir los
ciclos, algunos movimientos, en una iteración en
particular, son clasificados como prohibidos o tabú.
Algoritmo de Tabú
•
K=1
•
While (no fin)
Identificar N(s)S. (Conjunto de vecinos)
Identificar T(s)  N(s). (Conjunto Tabu)
Identificar A(s)  T(s). (Conjunto Aspirante)
Escoger s'  (N(sj)-T(sj))U A(sj), para el cual F(s') es maxima.
s=s'.
K=K+1.
•
END WHILE
Bases del Recocido Simulado
• El método se inspira del principio de la
termodinámica
• Los desplazamietos en el espacio de
búsqueda son basados en la distribución de
Boltzmann.
• El algoritmo de Kirkpatrick combina los
mecanismos de enfriamiento y de recorido.
Algoritmo del Recocido
Simulado (1)
• Inicialización
• Iterar
– Generar una nueva configuración
– Evaluar la energía
– Reemplazar si hay mejora o con probabilidad P=exp(-ΔE/T)
– Evaluar si se llegó al equilibrio
– Actualizar la temperatura
Estado actual
• Multitud de problemas de planificación en investigación
• La mayoría basadas en la utilización conjunta de las
técnicas anteriores: Reglas de prioridad, algoritmos
genéticos, heurísticas.
• Algunos artículos disponibles en la red:
– Evolutionary Computation for CSP’s.
http://www.aepia.org.revista
– Integración de algoritmos genéticos y heurísticas en la resolución
de problemas de Scheduling
http://tornado.dia.fi.upm.es/caepia/numeros/23/integracion.pdf
– Preemptive Scheduling for Distributed Systems
http://cactus.eas.asu.edu/partha/papers-pdf/pdcs98.pdf
Descargar

Problemas de asignación de tareas