Palabras clave
algoritmos dinámicos
competitividad de reglas de secuenciación
Cómo citar
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.
Baker, K.R. Introduction to Sequencing and Scheduling. New York: John Wiley & Sons, 1974.
Garey, M.R., Johnson, D.S. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co, 1979.
Graham, R.L. Bounds on Multiprocessing Timing Anomalies. En: SIAM Journal of Applied Mathematics, 17, 1969, 416-429.
Hoogeveen, J.A., Vestjens, A. Optimal on-line Algorithms for Single-Machine Scheduling. En: Lecture Notes in Computer Science, 1084, 1996, 404-414.
Lee, H.L., Padmanabhan, V., Wang, S. The Bullwhip Effect in a Supply Chain. En: Sloan Management Review, Spring, 1997, 93-102.
Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P. Complexity of Machine Scheduling Problems. En: Annals of Discrete Mathematics, 1, 1977, 343-362.
Manesse, M.S., McGeoch, L.A., Sleator, D.D. Competitive Algorithms for Server Problems. En: Journal of Algorithms, 11, 1990, 208-230.
Mao, W., Kincaid, R.K., Rifkin, A. On-line Algorithms for a Single Machine Scheduling Problem. En: S. Nash, A. Sofer (eds.) The Impact of Emerging Technologies on Computer Science and Operations Research. Norwell: Kluwer Academic Publishers, 1995, p. 157-173.
Merchán-Alba, A.L., Rodríguez-Verjan, G.L. Estudio del impacto de las estrategias de cooperación entre los eslabones de una cadena logística a nivel de la programación de la producción. Trabajo de Grado en Ingeniería Industrial. Bogotá: Pontificia Universidad Javeriana, 2006.
Montoya-Torres, J.R. Une étude de l’influence de l’information anticipée en ordonnancement dynamique. Master of Science Thesis. Grennoble: Institut National Polytechnique de Grenoble, 2002.
Montoya-Torres, J.R. Competitive Analysis of a Better On-line Algorithm to minimize total Completion Time on a Single-Machine. En: Journal of Global Optimization, 27 (1), 2003, 97-103.
Motwani, R., Phillips, S., Torng, E. Non-Clairvoyants Scheduling. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, p. 422-431. Austin, USA. January 25-27, 1993.
Phipps, T.E. Machine Repair as a Priority Waiting-Line Problem. En: Operations Research, 4, 1956, 45-61.
Pinedo, M. Scheduling: Theory, Algorithms and Systems. Prentice Hall, 1995.
Schrage, L.E. A Proof of the Optimality of the Shortest Remaining Processing Time Discipline. En: Operations Research, 16, 1968, 678-690.
Sepúlveda, J.P., Frein, Y. About the Effect of Coordination and Information Sharing on the Performance of a Typical Supply Chain. Preprints of the Third International Conference on Management and Control of Production and Logistics. CD-ROM. Santiago de Chile, 2004.
Sgall, J. On-Line Scheduling – A Survey. En: A. Fiat, G.I. Woeginger (eds.). On-line Algorithms: The State of the Art. Vol. 1.442. Berlin: Springer-Verlag, 1999. p. 196-231.
Smith, W.E. Various Optimizers for Single-Stage Production. En: Naval Research Logistics Quarterly, 3, 1956, 56-66.
Vestjens, A.P. On-line Machine Scheduling. PhD thesis. Eindhoven University of Technology, 1997.
Wolper, P. Introduction à la calculabilité. Collection IIE, InterEditions, 1991.
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Derechos de autor 2020 Jairo Rafael Montoya-Torres, Gloria Rodríguez-Verján, Liliana Merchá- Alba