17 de noviembre de 2015

Teoría de Scheduling: intro

La teoría de scheduling es el conjunto de modelos matemáticos que describen o se relacionan con el proceso de scheduling, a partir de esta descubriremos técnicas, soluciones e intuición práctica para seguir desarrollando la misma. La idea, al igual que en la creación de cualquier modelo matemático, es abstraer de manera cuantitativa el proceso de scheduling, describiendo los recursos y tareas, así como el(los) criterio(s) de decisión que transforamaremos en funcion(es) objetivo.

Las funciones objetivo pueden ser algo difícil de elegir pues idealmente deberían incluir todo costo relacionado con el schedule, pero esto rara vez es práctico. Por otro lado hay funciones objetivo muy comunes en la teoría de scheduling, dada la naturaleza e historia del scheduling relacionado con la producción se entenderá el por qué de la popularidad de las 3 funciones mencionadas:

Función Mide
Turnaround Tiempo requerido para completar una tarea
Timeliness Puntualidad
Throughput Cantidad de trabajo terminado en un periodo de tiempo fijo.

Mientras que la tercera función mide una característica que representa a todo el schedule, las primeras dos tareas miden "naturalmente" características de una tarea en particular, por lo que será necesario discutir más adelante estas dos funciones para darles sentido para evaluar un schedule completo.

Seguido de la función objetivo, se describe el problema de scheduling por otra características como
configuración de recursos y naturaleza de las tareas

RecursosTareasDisponibilidadTemporalidad
Una máquinaUna etapa / multi etapa (lo primero es más usual)
estático/dinámico
Multi máquinaUna etapa / multi etapa (lo segundo es más usual)paralelo/no paraleloestático/dinámico

El problema se puede describir aún más dependiendo de las condiciones, cuando estas son conocidas y no probabilísticas lo llamamos determinístico, en otro caso si conocemos de manera explícita la distribución de probablidad de las condiciones, lo llamamos estocástico. Solamente resta categorizar por factibilidad, ya sea por la capacidad de las máquinas, o el orden de ejecución de los trabajos.

Por otro lado podemos notar que una solución de un problema de scheduling, es decir, un schedule responde 2 preguntas: ¿Qué recursos deben ser asignados para realizar cada tarea? (asignación) y ¿Cuándo debe ser ejecutada cada tarea? (secuenciación).

Complejidad

No ahondaremos por ahora en el tema de la complejidad del problema del scheduling. Solamente notaremos que es un problema que puede llegar a ser muy difícil computacionalmente hablando (NP-hard) y es por eso que no es raro usar heurísticas en la práctica.

Conclusión

El hecho de que el scheduling sea un problema de asignación y secuenciación, y que tenga todas estas posibles configuraciones da pie al uso de técnicas muy variadas de modelación, simulación, métodos combinatorios, heurísticas, etc. Todo esto, aunado a su estrecha relación con el cómputo hacen que la teoría de scheduling sea un tema muy amplio e interesante.