| Journal: | Ingeniería y universidad |
| Database: | PERIÓDICA |
| System number: | 000348048 |
| ISSN: | 0123-2126 |
| Authors: | Montoya Torres, Jairo Rafael1 Rodríguez Verján, Gloria Merchán Alba, Liliana |
| Institutions: | 1Pontificia Universidad Javeriana, Departamento de Procesos Productivos, Bogotá. Colombia |
| Year: | 2006 |
| Volumen: | 10 |
| Number: | 2 |
| Country: | Colombia |
| Language: | Español |
| Document type: | Artículo |
| Approach: | Aplicado, descriptivo |
| Spanish abstract | 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 |
| English abstract | classical scheduling theory has traditionally considered the study and evaluation of scheduling algorithms based on the hypothesis of perfect advanced knowledge of the information needed to make the sequencing decisions. These algorithms are called to be used in an off-line context. Recently, a great interest has been dedicated to the study of online scheduling algorithms, which make sequencing decision on real-time, knowing only the information about jobs already arrived at the decision time. This paper considers the problem of scheduling on-line jobs on a single machine environment, and studies the wellknown SPT (Shortest Processing Time) and FIFO (First In, First Out) scheduling rules in an on-line context. The study of these two rules is first presented from the theoretic stand point by analyzing their worst-case competitiveness. Afterwards, the algorithms are compared from the practical point of view by a complete set of simulation experiments |
| Disciplines: | Ingeniería |
| Keyword: | Ingeniería industrial, Programación de tareas, Algoritmos, Reglas de secuenciación |
| Keyword: | Engineering, Industrial engineering, Task scheduling, Algorithms, Sequencing rules |
| Full text: | Texto completo (Ver PDF) |
