Análisis de la complejidad en algoritmos de calendarización

Abstract

El desarrollo de cualquier actividad productiva o de servicio se requiere de la organización adecuada de las tareas y recursos que se disponen para realizar dicha labor con éxito. La teoría de la calendarización es la disciplina científica que surgió a partir de esta problemática y uno de sus principales exponentes fue Henry Laurence Gantt. En la presente investigación se estudian los temas referentes a las técnicas usadas en los modelos de máquinas secuenciales y su relación con la complejidad computacional, como se verá en el desarrollo del presente trabajo, la gran mayoría de los problemas de calendarización de una máquina pertenecen a la clase NP-díficil y algunos parecen ser inclusive NP-completos, dichos conceptos no son sencillos de formular de una manera simple, por lo que fué necesario realizar un estudio relativamente amplio sobre la computación clásica con la finalidad de establecer con precisión la naturaleza de la dificultad de los algoritmos de calendarización. Aunque existe diversas técnicas para resolver problemas de calendarización, nos restringiremos a estudiar el método de reducción y algunas técnicas de algoritmos generales haciendo caso omiso del procedimiento de ramificación y acotamiento (branch and bound), programación dinámica, entre otras.