Optimizar. Solución de problemas de planificación con un algoritmo determinista

Abstract

El fin de este trabajo será adaptar el algoritmo determinista de Mària Ercsey-Ravasz y Zoltán Toroczkai publicado por la revista de divulgación científica Science Report en el artículo: "The chaos within Sudoku" (2012). El algoritmo descripto es utilizado para resolver Sudokus complejos, el problema pasa por una fase de codificación a Forma Normal Conjuntiva (CNF) y luego se simula un sistema de ecuaciones, analizando la evolución de la solución ante distintos valores posibles, hasta hallar el resultado final que satisfaga todas las restricciones. El solucionador planteado por los autores pasa por momentos dónde la trayectoria resolutiva es "caótica" y mientras mayor sea el tiempo que el sistema permanece en ese estado más compleja será encontrar la solución. El sistema dinámico propuesto por los autores incorpora la configuración de números de partida en el tablero y evoluciona desde una condición inicial aleatoria. Si la solución exis-te y es única, la evolución en tiempo de este sistema acabará alcanzándola. En el artículo publicado queda descripta la aplicación del algoritmo a la resolución de Su-dokus, fue demostrado por varios autores que este juego es un problema del tipo NP-Completo, uno de ellos fue Takayuki Yato en 2003. Además dadas sus características y debido a que puede ser expresado en forma normal conjuntiva, también se clasifica como SAT (problema de Satisfactibilidad Booleana, identificados por Cook en 1971), así lo describieron Lynce y Ouaknine en su trabajo "Sudoku as a SAT problema" (2006). Existen varios ejemplos de problemas de satisfactibilidad booleana como: N-damas, Sudo-ku, Coloreado de mapas, equivalencias de circuitos combinacionales, programación y asignación de tareas. Esta última situación es la que se va a analizar en el presente trabajo, buscando en primer lugar explicar su grado de dificultad y su relevancia en la planificación organizacional, para luego aplicar el solucionador presentado por Ercsey-Ravasz y To-roczkai a la resolución del mismo. La planificación de tareas organizacionales (Job Shop Scheduling) es un problema planteado desde hace casi medio siglo, ya que influye en todo el proceso productivo y en los planes operativos y estratégicos de la organización, las necesidades de materia prima, los tiempos de entrega y abastecimiento, pero también sirve para llevar a cabo controles de desviaciones en los tiempos pautados, de este modo al observar fluctuaciones en las estimaciones, (ya sea retrasos en lo pautado o "tiempos muertos") se podrán tomar medidas correctivas para evitar implicaciones monetarias que afectarán la viabilidad de la organiza-ción. Debido a que el Job Shop Scheduling también es del tipo NP-Completo cuando el número de máquinas es mayor o igual a 2 (Conway, Maxwell y Miller 1967), el cálculo de la se-cuencia óptima es extremadamente complejo (en especial cuando se presentan varias ope-raciones), es debido a su carácter combinatorio que dificulta la búsqueda de la solución, y que genera que la relación entre tamaño del problema y el tiempo de solución no sea lineal, suponiendo que al aumentar la complejidad el tiempo de resolución se dispara y los algoritmos planteados pierden su eficiencia. Por estas razones se está en una permanente búsqueda de un algoritmo que optimice la resolución de la planificación, y que permita un cálculo más rápido, y además algún indi-cador de la dificultad de ese cálculo. Caracterizar los sistemas caóticos es difícil, por la irregularidad de su comportamiento, por lo que lo habitual es introducir parámetros que caractericen el comportamiento a largo tiempo, ellos han decidido introducir un parámetro k que mide la duración del transitorio caótico (que acaba desapareciendo porque el sistema dinámico acaba convergiendo a la solución exacta). En definitiva esta investigación brinda una nueva manera de llevar a cabo la planificación de operaciones productivas, siendo este método eficiente cuando la complejidad imposibi-lita la solución utilizando modelos sencillos.