Peñalara Software

Publicado el

Integración con otras aplicaciones

El intercambio de datos entre distintas aplicaciones informáticas puede parecer algo relativamente sencillo que se consigue sin más, pero esto en general, no es cierto. En primer lugar los programas usan identificativos que normalmente no son compatibles. Por ejemplo, usando el DNI como clave para identificar a personas, podríamos establecer una correspondencia entre sus datos en las distintas aplicaciones. Pero si las claves no son las mismas, por ejemplo, si cada aplicación genera sus propios códigos como ocurre con frecuencia, la correspondencia se hace imposible sin un arduo y prolijo trabajo manual. Otro motivo evidente es que las relaciones entre los datos y sus estructuras internas también son propias de cada aplicación.

Para integrar los datos entre distintas aplicaciones se hace necesaria la existencia de interfaces bien diseñadas y documentadas, a través de las cuales se puedan exponer los datos y  comunicarse los programas. No hay otro modo. Pero esta condición, si bien es necesaria, no es suficiente. Además de una interfaz, debe ser posible establecer una correspondencia entre los códigos que se usen en una y otra aplicación para identificar sus elementos de información.

Si ponemos por caso una aplicación que realiza una petición de servicio a otra, la primera debe facilitar sus claves para que luego pueda interpretar el resultado una vez resuelto. Es decir, si una aplicación pide que se le resuelva una tarea, a través de la interfaz común debe aportar, además de la información propia de la petición, las claves necesarias para entender el resultado que reciba. Concretándolo más con un ejemplo, supongamos una aplicación que solicita a otra un servicio para resolver un horario académico. En este caso el horario resuelto debería expresarse usando claves para que la aplicación que lo pide lo reconozca. De este modo podrá identificar en la solución a los profesores, materias, etc. El acuerdo de formatos y de claves entre las dos aplicaciones debe ser preciso para que funcione y ambas partes deben de colaborar necesariamente en ello.

Existen algunas aplicaciones que exponen sus propias interfaces de intercambio sin que sean del todo operativas, con deficiencias de diseño que impiden que la carga del resultado pueda recibirse correctamente. Se hace por lo tanto necesaria la implementación de interfaces abiertas bien definidas y documentadas para la comunicación entre aplicaciones. De hecho existen organismos de estandarización que las establecen. En su defecto se podrían adoptar como estándares las interfaces abiertas asociadas a productos consolidados que se publiquen con este fin.

Peñalara Software ha hecho público el formato interno de almacenamiento de GHC para usarlo como interface de intercambio. El formato XML-GHC es completo. Todo aquello que se configura con el planificador, así como los resultados que genera GHC, puede expresarse con este modelo.

Además, junto al desarrollo de un nuevo motor de horarios que esperamos ofrecer próximamente como servicio remoto, disponemos de interfaces abiertas JSON que podrán consultarse a través del repositorio público GitHub y que están asociadas a librerías de desarrollo también disponibles, en este caso, en Apache Maven. Con este proyecto intentamos ofrecer servicios para la generación los horarios al ecosistema de aplicaciones de gestión académica, y así facilitar en última instancia el trabajo a los usuarios.

Publicado el

¿Es posible determinar la existencia de condiciones que impidan los resultados?

Podemos afirmar felizmente que disponemos de un motor capaz de encontrar de forma eficaz los horarios más exigentes. Pero como saben ustedes, para optimizar los horarios primero es necesario encontrar resultados completos. Desgraciadamente, al trabajar con la planificación del horario habrán experimentado que se introducen condiciones imposibles de cumplir. Ahora quizá la cuestión más controvertida en la utilización del generador de horarios sea cómo determinar, de forma previa al uso del motor, si hay condiciones imposibles. ¿Se puede saber qué condiciones impiden los horarios completos?

El motor es el componente que en última instancia debe encontrar la solución por lo que no siempre es posible saber a priori si existen condiciones imposibles de satisfacer. Y esto es estrictamente cierto; hay condiciones imposibles de cumplir que son muy difíciles de analizar. Sin embargo, sí es posible determinar muchas de las condiciones imposibles; casi todas las que se introducen inadvertidamente impidiendo los resultados completos. 

El motor de GHC encaja resultados muy rápidamente. Esto es un hecho. Si el motor no encuentra resultados de forma rápida y se obstina en dejar sin encajar alguna sesión en repetidos intentos, la mayor parte de las veces es debido a que hay alguna condición que lo impide y que se debe depurar. Otras veces, al motor le cuesta un poco más de tiempo y esfuerzo encontrar una solución completa si éstas son más singulares. ¿Debemos esperar? Y si sospechamos que existen alguna condición imposible, ¿cuál es?

Disponemos de dos procesos que nos pueden ayudar a comprobar de forma previa al uso del motor si existen condiciones imposibles de cumplir: la validación de la configuración del planificador y el analizador de conjuntos mínimos imposibles de encajar.

El proceso de validación examina algunas de las causas más comunes que puedan impedir los resultados completos. Por ejemplo, que se han asignado más horas a un grupo de alumnos de las que caben en su marco horario o que se han prefijado diferentes sesiones a la misma hora con el mismos profesor.

Por otra parte, el analizador de conflictos intenta solucionar por separado los horarios de cada profesor, de cada grupo de alumnos, etc. De forma que, si no puede solucionar alguno de estos subconjuntos, lo reducirá a un mínimo de sesiones imposibles de encajar. Si el analizador encuentra un conjunto mínimo de sesiones que no encajan, será más fácil ver qué ocurre, es decir, qué condiciones interfieren entre sí dentro de este reducido número de sesiones.

Aunque no es lo más común, como ya hemos indicado, puede haber horarios para los que el motor no encuentra solución que aparentemente no encierran conflictos. Efectivamente, existen horarios sin errores de validación y para los que el analizador no encuentra conflictos, que sin embargo contienen condiciones que impiden las soluciones. Para estos caso disponemos de una tercera herramienta que nos puede ayudar en gran medida:  el depurador de condiciones imposibles. El depurador de condiciones permite lanzar el motor y también el analizador, sin unas u otras de las condiciones estrictas inicialmente configuradas. El depurador de condiciones es muy útil para lanzar pruebas flexibilizando las condiciones estrictas y así saber cuáles impiden las soluciones.

Existen otras estrategias de depuración, cómo intentar asignar directamente desde el editor las sesiones que no se han podido encajar para ver qué mensajes aparecen o comprobar en el resultado incompleto dónde quedan los huecos en el horario de los grupos, por si el problema es alguna reunión o la existencia de un exceso de posiciones prohibidas a los profesores, coincidentes a la misma hora.

No queremos dejar de afirmar que la labor de hacer los horarios académicos es lo suficientemente compleja como para que, además de contar con las mejores herramientas, sea necesaria la pericia de quien las use. No deje de pedirnos toda la ayuda que necesite. En todo caso, el mérito de hacer los mejores horarios siempre será el suyo.

Publicado el

¿Es posible el horario perfecto?

Encajar los horarios semanales de un centro de enseñanza medianamente grande o complejo no es una tarea fácil. Esto lo saben muy bien quienes se han enfrentado a este problema en alguna ocasión y, en mayor medida, quienes tienen la responsabilidad de hacerlo cada año; hay que resolver un auténtico rompecabezas. Pero si es difícil encontrar una solución que satisfaga los requisitos mínimos, encontrar la mejor solución parece una tarea imposible. Y precisamente esta es la cuestión que planteamos: ¿Es posible hacer horarios perfectos?

En puridad, y por desgracia, debemos decir que el horario perfecto es imposible y existen varias razones para afirmarlo. La primera y más evidente es que cualquier modelo para expresar lo que se busca tendrá imperfecciones. Efectivamente, el modelo matemático a través del cual se calcula una función de peso que permita obtener el horario óptimo y su aplicación a los elementos que comprende el horario: alumnos, profesores, sesiones lectivas, etc., será siempre una aproximación a la realidad que, en el mejor caso, se estimará de forma precisa correspondiéndose con lo que se busca.

La segunda razón, y esta no es tan evidente, es que el conjunto de soluciones es tan elevado que la búsqueda exhaustiva es imposible, incluso para el ordenador más rápido del mudo.

¿Recuerdan la paradoja de la leyenda del inventor del ajedrez?

Cuenta la leyenda que un rey persa a quien gustó el juego del ajedrez, mandó llamar a su inventor para recompensarle por su ingenio. De forma imprudente el rey le dijo que pidiese lo que quisiese y el inventor le contestó: me conformo con 1 grano de trigo por la primera casilla del tablero, 2 por la segunda, 4 por la tercera, 8 por la cuarta y así hasta la casilla 64 del tablero. Es decir la suma de la serie 1+2+4+8… hasta completar 64 términos en progresión geométrica. El rey se pensó que lo que estaba pidiendo era una minucia y mandó preparar el premio solicitado pero haciendo los cálculos se dieron cuenta de que era imposible cumplir la orden, pues la suma de los granos de las 64 casillas era nada menos que la cantidad de 36.893.488.147.419.103.231 granos. Si en cada Kilogramo de trigo caben aproximadamente unos 25.000 granos, entonces el resultado sería de unas 1.475.739.525.896 toneladas. Si el carguero más grande puede alojar hasta 186.000 toneladas netas, harían falta alrededor de 8 millones de enormes cargueros para transportar todo el trigo. Más de 1000 veces la producción mundial anual de trigo.

Caballeros templarios jugando al ajedrez

Con el problema de hacer horarios académicos también se da esta paradoja; parece que sería relativamente fácil probar todas las posibles soluciones con una computadora pero, de hecho, es imposible. La cuestión es que el número de combinaciones crece exponencialmente y harían falta años de cálculo, incluso con la más potente computadora, para recorrerlas todas. Los procesos que resuelven este rompecabezas se estudian a través de una disciplina matemática y computacional que trata de dar la mejor solución posible, en tiempos razonables, a problemas excesivamente complejos.

El Generador de Horarios para Centros de enseñanza GHC de Peñalara utiliza un software de horarios capaz de encontrar soluciones y hacerlas óptimas de forma extraordinariamente eficaz en lapsos de tiempo suficientemente cortos aún en los supuestos más complicados. La buena noticia es que este tipo de problemas intratables mediante procesos de búsqueda exhaustiva se consiguen resolver en gran medida utilizando algoritmos inteligentes. Podemos afirmar, finalmente, con gran satisfacción y también alivio para quienes tienen la responsabilidad de hacer los horarios cada curso, que los horarios ‘perfectos’, en la práctica, sí que son posibles.