Resumen

La teoría clásica de la programación (secuenciación) de tareas se ha dedicado a estudiar y evaluar la pertinencia de reglas o algoritmos cuando toda la información del grupo de tareas por ejecutar se conoce de manera anticipada. Estos escenarios se llaman de tipo estático (off-line). Recientemente se ha dedicado gran interés al estudio de algoritmos dinámicos (on-line), los cuales deben tomar decisiones de ejecución de las tareas en tiempo real conociendo únicamente la información disponible al instante de toma de la decisión. En este artículo, se estudia el problema de secuenciación on-line de tareas en un recurso único y se presenta el estudio de las reglas SPT (Shortest Processing Time) y FIFO (First In, First Out). Estas reglas son inicialmente analizadas con respecto a su competitividad para el peor de los casos y, posteriormente, se desarrolla una serie de experimentos de simulación para verificar dichos postulados y comparar las reglas aplicándolas a diferentes instancias de trabajo.

1. INTRODUCCIÓN

La programación (secuenciación) de tareas (scheduling) es una parte de la investigación de operaciones que se interesa por estudiar la asignación de recursos limitados a un conjunto de trabajos por realizar en un horizonte de tiempo, con el fin de optimizar uno o más objetivos. Es un proceso de toma de decisiones que constituye uno de los problemas más importantes en gestión de la producción, tanto desde el punto de vista teórico como práctico [Pinedo, 1995]. En los modelos clásicos se considera que toda la información necesaria para establecer la secuencia de ejecución de un conjunto de tareas es conocida desde el instante inicial del horizonte de programación. Se habla entonces de modelos estáticos o modelos off-line. Sin embargo, las condiciones actuales de competencia de mercados y algunas aplicaciones específicas en sistemas de producción han obligado a los investigadores a considerar nuevos modelos y métodos de secuenciación de trabajos, esta vez reactivos, adaptativos y, sobre todo, evolutivos en tiempo real, con el fin de satisfacer las nuevas necesidades industriales. De esta manera, se habla de modelos dinámicos o modelos on-line [Sgall, 1999].

Durante los últimos años, las investigaciones en el área de modelos on-line de secuenciación de tareas han tenido un gran desarrollo. Los modelos y algoritmos propuestos están basados tanto en reglas clásicas utilizadas desde hace mucho tiempo por los industriales, como en estrategias más sofisticadas [Sgall, 1999].

• Materias:Algoritmos (Computadores) Administración de la producción Algoritmos genéticos Ingeniería de la producción Programación de la producción Programación genética (Ciencia de la computación)
• Subjects:Computer algorithms Production management Genetic algorithms Production engineering Production scheduling Genetic programing (Computer science)
• Palabras claves:Secuenciación dinámica de tareas; Algoritmos dinámicos; Competitividad de reglas de secuenciación
• Keywords:On line scheduling; Dynamic algorithms; Competitiveness of scheduling rules