La programación de horarios

Resumen

Suponga que está estudiando una carrera cuyas materias se dictan en distintos horarios que puede elegir libremente y que, además, le interesa concurrir a esas clases de inglés que hace tanto tiempo debería haber tornado, todo esto sin dejar de asistir a yoga dos veces por semana, que tanto bien le hace. Seguramente se las ingeniara, para acomodar todas sus actividades a lo largo de cada día de la semana, no sin antes haber pasado un buen rato, lápiz y papel en mano, evaluando las distintas posibilidades. Este es un problema típico —en pequeña escala— de planificación y programación de horarios. En la vida actual, este tipo de problemas se presenta con frecuencia y la cantidad de variables involucradas (muchas personas, maquinas, tareas) hace que su resolución sea una cuestión compleja. En estos casos no se puede pretender considerar todas las posibilidades y luego elegir la mejor, pues la cantidad de tiempo necesaria para ello puede resultar excesivamente grande. Esto ha motivado el desarrollo de algoritmos (ver Apéndice) que permiten obtener soluciones razonables en tiempos también razonables. El problema general se puede plantear de la siguiente manera: se debe realizar un cierto trabajo que consta de una serie tareas, para cuya ejecución se dispone de varias máquinas (usamos esta palabra en sentido amplio, pudiendo también referirse a robots, personas, etcétera). A partir de aquí surgen distintos subproblemas. Uno de ellos consiste en distribuir las tareas en las máquinas de modo tal que el tiempo requerido para terminar el trabajo sea el menor posible. Otro es distribuir las tareas en las máquinas de manera que el tiempo ocioso de las mismas sea mínimo. Finalmente, también podemos estar interesados en determinar la cantidad mínima de máquinas que permiten terminar el trabajo en un tiempo dado.