PROGRAMACIÓN DE OPERACIONES
SCHEDULING-SECUENCIAMIENTO DE TAREAS
JAIME MIRANDA
Departamento de Ingeniería Industrial
Universidad de Chile
DEFINICIONES: SCHEDULING
¿Qué es un Programa?
→ Es un horario para ejecutar actividades, utilizando recursos o asignando
instalaciones.
¿Qué es programar operaciones?
→ Programar implica determinar el orden en que se ejecutarán las tareas y,
también, la asignación de recursos a éstas (máquinas, personal, etc.).
DEFINICIONES: SCHEDULING (2)
¿Qué es un Centro de Trabajo?
→ Es un área de una empresa en la cual los recursos productivos se organizan y el
trabajo se lleva a cabo.
→ En el caso de Talleres de Trabajo, las tareas deben ser dirigidas entre Centro de
Trabajos organizados funcionalmente.
¿Qué es Secuenciemaiento de Tareas?
→ Corresponde al proceso de determinar qué tarea se inicia primero en alguna
máquina o centro de trabajo.
CASOS PRACTICOS
ASIGNACION DE TURNOS STAFF DE AEROLINEAS
→ PROBLEMA GENERAL
• Asignación de turnos a personal aéreo y rutas de aviones de una aerolínea.
CARACTERISICAS
→ Más de 1.000 empleados.
→ En variados países.
→ Distintos turnos y zonas horarias
→ Restricciones de vuelo.
PAPER: Optimized Crew Scheduling at Air New Zealand
Autor: David M. Ryan
CASOS PRACTICOS (2)
ESQUEMA DE HORARIOS Y CURSOS DE UNA UNIVERSIDAD
PROBLEMA GENERAL
• Asignación de salas, horarios y profesores a los ramos de los distintos semestres en una institución
académica
CARACTERÍSTICAS
→ Capacidad y número de salas.
→ Número de cursos
→ Número de alumnos.
→ Número de profesores.
→ Disponibilidades de bloques.
→ Ajustes de semestres.
CASOS PRACTICOS (3)
ESQUEMA DE ORGANIZACIÓN DE FECHAS DE PARTIDOS
→ PROBLEMA GENERAL
• Asignación de las fechas para cada partido, asignando a cada equipo durante la duración de un
campeonato
CARACTERISICAS
→ Muchos equipos.
→ Distintas tarificaciones horarias
→ Días importantes - Aniversario de clubes.
→ Días y hora para “clasicos”
→ Secuenciamiento de partidos – Local – Visitas.
→ Poder político. Televisión- jugadores.
PAPER: SCHEDULING A MAJOR COLLEGE BASKETBALL
Autor: George l. Nemhauser
CASOS PRACTICOS (4)
SECUENCIAMIENTO DE TRABAJOS EN PRODUCCIÓN
PROBLEMA GENERAL
• Generación de secuenciamientos de tareas a los distintos centros de trabajo.
CARACTERISTICAS
→ Se poseen n tareas y m maquinas.
→ ¿Qué tarea realizo primero?
→ ¿En qué máquina?
→ Prioridades sobre las tareas.
→ PAPER: Production Scheduling Theory: Just Where Is It Applicable?
• Autores: Víctor Portougal-David J. Robb
SISTEMAS DE PROGRAMACIÓN
Las principales maneras de programar operaciones se clasifican de la
siguiente forma:
→ Programación de Carga Infinita:
• Las tareas son asignadas a un centro de trabajo en base a lo que se necesita en el
tiempo, sin considerar si existen los recursos suficientes (capacidad).
→ Programación de Carga Finita:
• Determina con exactitud que hará cada recurso en cada momento de la jornada de
trabajo.
SISTEMAS DE PROGRAMACIÓN (2)
→ Programación de Carga Futura:
• Se toman los pedidos y programan las operaciones que deben completarse más
adelante en el tiempo.
• Indica la fecha más temprana en que un pedido puede terminarse.
→ Programación de Carga Inversa:
• Se inicia en una fecha futura (por ejemplo, vencimiento) y se programan las operaciones
requeridas en una secuencia inversa.
• Indica cuando debe iniciarse un pedido o tarea para que se termine en una fecha
específica.
• Un Sistema MRP es un buen ejemplo.
SISTEMAS DE PROGRAMACIÓN (3)
ALGUNAS LIMITANTES:
→ Limitado a las Máquinas:
• Los equipos corresponden a los recursos críticos en la programación de operaciones.
→ Limitado al Trabajo:
• El personal constituye el recurso clave de la programación de operaciones.
Nota: Actualmente la tecnología permite la generación de programas muy
detallados.
FUNCIONES
Para poder programar y controlar una operación, se deben ejecutar las
siguientes funciones:
→ Asignar pedidos, equipos y personal a los centros de trabajo.
→ Determinar la secuencia de ejecución de los pedidos o tareas.
→ Control de piso del taller, es decir, revisar estados de los pedidos y tomar las
acciones correctivas pertinentes.
OBJETIVOS
Dentro de los muchos objetivos que se pueden definir para la
programación, destacan:
→ Cumplir con las fechas de entrega de los pedidos.
→ Minimizar el plazo de entrega.
→ Minimizar el inventario de productos en proceso.
→ Minimizar el tiempo o costo de preparación (setup).
→ Maximizar la utilización de máquinas y personal (trade off).
REGLAS DE DESPACHO - HEURISTICAS
Definición:
→ Las reglas de despacho o normas prioritarias corresponden a los criterios
utilizados para obtener el secuenciamiento de un conjunto de tareas.
Formas de evaluarlas:
→ Ajuste a las fechas de vencimiento.
→ Minimización de los tiempos de proceso.
→ Minimización de los inventarios de productos en proceso.
→ Minimización del tiempo de inactividad de máquinas o trabajadores.
EJEMPLO
→ La información asociada a los pedidos es la siguiente:
Tarea Tiempo de Proceso Fecha de Vencimiento
(en orden de llegada) (días) (días a partir de hoy)
A 3 5
B 4 6
C 2 7
D 6 9
E 1 2
→ Todos los pedidos requieren de la utilización de una única máquina a color disponible.
El supervisor quiere decidir sobre la secuencia de procesamiento para los 5 pedidos
utilizando como criterio de evaluación el tiempo de proceso mínimo.
REGLAS DE DESPACHO (2)
Las 10 principales:
→ FCFS (First Come, First Served):
• La primera tarea o pedido en llegar es el primero en ser atendido.
• Los pedidos se ejecutan el orden en que llegan a la máquina o centro de trabajo.
Secuencia Duración Fecha de Vencimiento Tiempo en
de tareas (días) (días a partir de hoy) Proceso
A 3 5 0+3=3
B 4 6 3+4=7
C 2 7 7+2=9
D 6 9 9 + 6 = 15
E 1 2 15 + 1 = 16
Tiempo Total en Proceso = 3 + 7 + 9 + 15 + 16 = 50 días.
Tiempo Medio en Proceso = 50/5 = 10 días.
Tiempo Promedio de Atraso = (0 + 1 + 2 + 6 + 14)/5 = 4,6 días.
REGLAS DE DESPACHO (2)
→ SOT (Shortest Operating Time):
• Tiempo de operación más corto.
• Primero se ejecuta la tarea que tenga el tiempo de termino más corto.
• Es idéntica al tiempo de procesamiento más corto (SPT).
Secuencia Duración Fecha de Vencimiento Tiempo en
de tareas (días) (días a partir de hoy) Proceso
E 1 2 0+1=1
C 2 7 1+2=3
A 3 5 3+3=6
B 4 6 6 + 4 = 10
D 6 9 10 + 6 = 16
Tiempo Total en Proceso = 1 + 3 + 6 + 10 + 16 = 36 días.
Tiempo Medio en Proceso = 36/5 = 7,2 días.
Tiempo Promedio de Atraso = (0 + 0 + 1 + 4 + 7)/5 = 2,4 días.
REGLAS DE DESPACHO (3)
→ Fecha de vencimiento:
• Primero se ejecuta la tarea con fecha de vencimiento más cercana.
→ Fecha de iniciación:
• Se define como la fecha de vencimiento menos el tiempo normal que demora la tarea en
el centro de trabajo.
• Se ejecuta primero la tarea con fecha de iniciación más cercana.
Secuencia Duración Fecha de Vencimiento Tiempo en
de tareas (días) (días a partir de hoy) Proceso
E 1 2 0+1=1
A 3 5 1+3=4
B 4 6 4+4=8
C 2 7 8 + 2 = 10
D 6 9 10 + 6 = 16
Tiempo Total en Proceso = 1 + 4 + 8 + 10 + 16 = 39 días.
Tiempo Medio en Proceso = 39/5 = 7,8 días.
Tiempo Promedio de Atraso = (0 + 0 + 2 + 3 + 7)/5 = 2,4 días.
REGLAS DE DESPACHO (4)
→ STR (Slack Time Remaining):
• Corresponde a la holgura de tiempo restante para el inicio de una tarea.
• Se calcula como la diferencia entre el tiempo que falta para la fecha de vencimiento y el
tiempo total de procesamiento restante.
• Los pedidos que tienen el STR más corto se ejecutan primero.
→ STR/OP (Slack Time Remaining per Operation):
• Se calcula como la razón entre el STR y el número de operaciones restantes.
• El pedido con STR/OP más corto es ejecutado primero.
Secuencia Duración Fecha de Vencimiento Tiempo en
de tareas (días) (días a partir de hoy) Proceso
E 1 2 0+1=1
A 3 5 1+3=4
B 4 6 4+4=8
D 6 9 8 + 6 = 14
C 2 7 14 + 2 = 16
Tiempo Total en Proceso = 1 + 4 + 8 + 14 + 16 = 43 días.
Tiempo Medio en Proceso = 43/5 = 8,6 días.
Tiempo Promedio de Atraso = (0 + 0 + 2 + 5 + 9)/5 = 3,2 días.
REGLAS DE DESPACHO (6)
→ LCFS (Last Come, First Served):
• El último pedido en llegar es el primero en ser ejecutado.
• Esta norma se presenta con frecuencia por defecto. A medida que llegan los pedidos,
éstos se colocan encima de una pila, el operador recoge el pedido de encima y lo
ejecuta.
Secuencia Duración Fecha de Vencimiento Tiempo en
de tareas (días) (días a partir de hoy) Proceso
E 1 2 0+1=1
D 6 9 1+6=7
C 2 7 7+2=9
B 4 6 9 + 4 = 13
A 3 5 13 + 3 = 16
Tiempo Total en Proceso = 1 + 7 + 9 + 13 + 16 = 46 días.
Tiempo Medio en Proceso = 46/5 = 9,2 días.
Tiempo Promedio de Atraso = (0 + 0 +2 + 7 + 11)/5 = 4,0 días.
REGLAS DE DESPACHO (6)
→ RANDOM (Orden Aleatorio):
• Consiste en escoger cualquier tarea para ejecutarla primero.
Secuencia Duración Fecha de Vencimiento Tiempo en
de tareas (días) (días a partir de hoy) Proceso
D 6 9 0+6=6
C 2 7 6+2=8
A 3 5 8 + 3 = 11
E 1 2 11 + 1 = 12
B 4 6 12 + 4 = 16
Tiempo Total en Proceso = 6 + 8 + 11 + 12 + 16 = 53 días.
Tiempo Medio en Proceso = 53/5 = 10,6 días.
Tiempo Promedio de Atraso = (0 + 1 + 6 + 10 + 10)/5 = 5,4 días.
REGLAS DE DESPACHO (5)
→ CR (Critical Ratio):
• Se calcula como la diferencia entre la fecha de vencimiento y la fecha actual, dividida por
el número de días de trabajo restantes.
• El pedido que tiene CR más pequeño se ejecuta primero.
→ QR (Queue Ratio):
• Se calcula como el tiempo de holgura restante en el programa dividido por el tiempo en
cola restante planeado.
• El pedido con QR más pequeño se ejecutan primero.
TÉCNICAS DE PROGRAMACIÓN (9)
• Tabla Resumen:
Regla Tiempo Total Tiempo Medio Tiempo Promedio
en Proceso en Proceso (días) de Atraso (días)
FCFS 50 10,0 4,6
SOT 36 7,2 2,4
DDATE 39 7,8 2,4
LCFS 46 9,2 4,0
RANDOM 53 10,6 5,4
STR 43 8,6 3,2
• Se puede concluir que la regla SOT es la mejor de acuerdo al criterio considerado.
• Además, puede demostrarse matemáticamente que ésta genera una solución óptima
para el tiempo total de proceso y el tiempo medio de proceso.
TÉCNICAS DE PROGRAMACIÓN
OBSERVACIÓN GENERAL:
→ La dificultad teórica de los problemas de programación se incrementa a medida
que se consideran más máquinas, y no en la medida que se deben procesar más
tareas.
PROGRAMACIÓN DE OPERACIONES
SCHEDULING-SECUENCIAMIENTO DE TAREAS
JAIME MIRANDA
Departamento de Ingeniería Industrial
Universidad de Chile
