Estudio de algoritmos dinámicos para el problema de secuenciación de trabajos en una máquina simple
##plugins.themes.bootstrap3.article.details##
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 used in an off-line context. Recently, a great interest has been dedicated to the study of on-line 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 well-known 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.
On line scheduling, dynamic algorithms, competitiveness of scheduling rulessecuenciación dinámica de tareas, algoritmos dinámicos, competitividad de reglas de secuenciación
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.
This work is licensed under a Creative Commons Attribution 4.0 International License.