Universidad de Carabobo

Facultad de Ciencias y Tecnologıa

Departamento de Computacion

Modelo general de costos para elproblema de asignacion de horarios.

Autor:

Br. Jose Rosendo

C.I. V - 22.213.692

Tutor Academico:

Dr. Amadıs Martınez

Valencia, septiembre de 2016.

1

Resumen

El problema de asignacion de horarios consiste en la colocacion de tareas a realizar en

determinados momentos a un sujeto. Tal asignacion se ve restringida previamente por un

conjunto de limitaciones asociadas al contexto. Este problema es combinatorio y de orden

no polinomial, lo cual lo coloca como imposible de ser resuelto en tiempo polinomial por

un algoritmo determinıstico. A la fecha la solucion del mismo se ve abordada por tecnicas

heurısticas y metaheurısticas, las cuales brindan soluciones cercanas a la optima.

Tomando en cuenta el inconveniente antes mencionado, se hace necesario el planteamiento

de un modelo de costos lo suficientemente flexible en cuanto a uso y que sirva de base para la

optimizacion de los calculos relacionados a la asignacion de horarios. En este trabajo se plan-

tea la realizacion de tal tarea, desarrollando el correspondiente entramado teorico-practico,

a fin de conseguir un avance positivo en las investigaciones del campo.

Siguiendo las directrices establecidas por el Protocolo de Modelado matematico - logico,

se desarrollo un conjunto de premisas que estructuraban las entidades, relaciones y restric-

ciones del modelo general a construir, definiendo el objetivo del modelado, formulando el

respectivo modelo conceptual, estableciendo bajo que categorıa(s) cae el modelo a construir,

seleccionando las herramientas de software para las simulaciones y validaciones del mismo,

realizando previamente las respectivas parametrizaciones, para ası presentar bajo el formato

requerido el compendio de resultados en donde se demuestra la validez de las hipotesis plan-

teadas, esto es, la posibilidad de construir un sistema generico de procesos, o en su defecto

que abarque los principales casos del timetabling problem, que optimice el modelo de restric-

ciones del problema a solucionar, para luego proceder con la solucion en concreto.

Palabras claves: modelado de restricciones, algoritmos de propagacion de restricciones,

optimizacion.

2

Indice

1. Introduccion 7

2. Marco Teorico 9

2.1. Antecedentes de la investigacion . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2. Bases teoricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.1. Investigacion de operaciones . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.2. Problema de asignacion de horarios [38] [36] [58] . . . . . . . . . . . . 16

2.2.3. Complejidad algorıtmica . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.4. Programacion con restricciones . . . . . . . . . . . . . . . . . . . . . 20

2.2.5. Propagacion de restricciones [25] [28] [41] [53] . . . . . . . . . . . . . 20

2.2.6. Modelado cientıfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3. Planteamiento del Problema y Justificacion 24

3.1. Contexto del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2. Definicion del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3. Objetivos de la investigacion . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.3.1. Objetivos Generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.3.2. Objetivos Especıficos . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.4. Justificacion e importancia del tema tratado . . . . . . . . . . . . . . . . . . 28

4. Marco Metodologico 29

4.1. Descripcion de la metodologıa . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1.1. Protocolo de Modelado . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2. Aplicacion de la metodologıa . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.2.1. Definicion del objetivo del modelado . . . . . . . . . . . . . . . . . . 34

4.2.2. Formulacion del modelo conceptual . . . . . . . . . . . . . . . . . . . 37

4.2.3. Tipo de modelo a usar . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2.4. Seleccion del codigo a aplicar . . . . . . . . . . . . . . . . . . . . . . 43

4.2.5. Parametrizacion del modelo . . . . . . . . . . . . . . . . . . . . . . . 44

4.2.6. Validacion del modelo . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3

4.2.7. Simulacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2.8. Presentacion y analisis de resultados . . . . . . . . . . . . . . . . . . 47

5. Diseno de la solucion 49

5.1. Descripcion de la solucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2. Alcance y limitaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6. Resultados experimentales 52

6.1. Configuracion de los experimentos . . . . . . . . . . . . . . . . . . . . . . . . 53

6.1.1. Plataforma computacional . . . . . . . . . . . . . . . . . . . . . . . . 53

6.1.2. Casos de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.1.3. Metricas de evaluacion . . . . . . . . . . . . . . . . . . . . . . . . . . 103

6.2. Analisis de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.2.1. Hipotesis iniciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.2.2. Resultados obtenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

7. Conclusiones y recomendaciones 120

7.1. Conclusiones de la investigacion . . . . . . . . . . . . . . . . . . . . . . . . . 120

7.2. Trabajos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

4

Indice de figuras

1. Clases de complejidad [88] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2. Trilogıa Modelo - Algoritmo - Programa [32] . . . . . . . . . . . . . . . . . . 30

3. Esquema general del modelo matematico. [32] . . . . . . . . . . . . . . . . . 31

4. Primera etapa del protocolo de modelado [32] . . . . . . . . . . . . . . . . . 32

5. Segunda etapa del protocolo de modelado [32] . . . . . . . . . . . . . . . . . 33

6. Tercera etapa del protocolo de modelado [32] . . . . . . . . . . . . . . . . . . 34

7. Clase Individuo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

8. Clase Actividad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

9. Relacion Individuo-Realiza-Actividad. . . . . . . . . . . . . . . . . . . . . . . 42

10. Entrada del caso de prueba PE-CTT: matriz de asistencia de estudiantes a

clases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

11. Entrada del caso de prueba PE-CTT: matriz correlacion de aulas con propie-

dades. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

12. Entrada del caso de prueba PE-CTT: matriz correlacion de eventos con pro-

piedades requeridas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

13. Entrada del caso de prueba PE-CTT: matriz de restriccion de precedencia

entre eventos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

14. Ejemplo de formato original de entrada de caso de prueba CB-CTT. . . . . . 71

15. CB-CTT: Proporcion de casos exitosos . . . . . . . . . . . . . . . . . . . . . 108

16. CB-CTT: Menor tiempo de solucion por caso . . . . . . . . . . . . . . . . . 109

17. CB-CTT: Mayor tiempo de solucion por caso . . . . . . . . . . . . . . . . . . 109

18. CB-CTT: Tiempo promedio de solucion por caso . . . . . . . . . . . . . . . 110

19. PE-CTT: Proporcion de casos exitosos . . . . . . . . . . . . . . . . . . . . . 110

20. PE-CTT: Menor tiempo de solucion por caso . . . . . . . . . . . . . . . . . . 111

21. PE-CTT: Mayor tiempo de solucion por caso . . . . . . . . . . . . . . . . . . 111

22. PE-CTT: Tiempo promedio de solucion por caso . . . . . . . . . . . . . . . . 112

5

Indice de tablas

1. Valores de Caso de Prueba PE-CTT . . . . . . . . . . . . . . . . . . . . . . 69

2. Valores de Caso de Prueba CB-CTT . . . . . . . . . . . . . . . . . . . . . . 75

3. Resultados de Caso de Prueba CB-CTT . . . . . . . . . . . . . . . . . . . . 106

4. Resultados de Caso de Prueba PE-CTT . . . . . . . . . . . . . . . . . . . . 107

6

1. Introduccion

El problema de asignacion de horarios consiste en la asignacion de un conjunto de tareas

a ser realizada por un sujeto en determinados bloques horarios. Tal asignacion se ve influida

por un conjunto de restricciones que varıan de acuerdo al contexto. Ası, por ejemplo, en

un horario universitario tales restricciones van asociadas a la cantidad de aulas disponibles,

los profesores asignados a una determinada asignatura, entre otros factores. En terminos

conceptuales, el timetabling problem es un problema combinatorio de orden no polinomial.

Los problemas algorıtmicos que entran en esta categorıa no son resolubles en tiempos cortos

utilizando tecnicas tradicionales. Tomando en cuenta lo anterior, se han planteado multiples

soluciones que van desde optimizar el modelado de las restricciones, pasando por el uso de

heurısticas y metaheurısticas en el calculo del horario optimo para un sujeto dado, hasta la

aplicacion de computos en paralelo en hardware dedicado para tal fin. [38] [36] [58]

Partiendo de la base anterior, en la cual se perfila la naturaleza del problema de asigna-

cion de horarios, se hace enfatico el planteamiento de un modelo de costos y de restricciones

que por un lado sea lo suficientemente flexible para ser usado en los mas diversos contex-

tos y por el otro proporcione la base para optimizar los calculos posteriores relacionados a

la asignacion del horario requerido. Es ası que en este trabajo se plantea la posibilidad de

realizar tal cometido, partiendo de investigaciones previas que han planteado perspectivas

similares pero para contextos mas limitados. Se recalca que por un lado es imprescindible

la creacion de un modelo robusto que soporte cualquier restriccion a modelar, ası como los

mecanismos necesarios para que tal modelo se reformule en base a mecanismos algorıtmicos

ya establecidos. Tal reformulacion va orientada a la busqueda de mejores soluciones en el

marco del conjunto de datos dado. [84] [52] [51]

Este documento esta estructurado en siete capıtulos, incluyendo la introduccion. El capıtu-

lo 2 cubre el marco teorico en base a dos puntos principales que son los antecedentes de la

investigacion y las bases teoricas del presente trabajo. El capıtulo 3 define el contexto del

problema presentado ası como una definicion detallada del mismo, para luego mostrar los

7

objetivos generales y especıficos a lograr, todo esto con su debida justificacion y explicacion

de la importancia de cumplirlos. El capıtulo 4 describe la metodologıa a usar para resolver

el problema ya descrito, ası como el plan de trabajo a cumplir acorde a la misma. El capıtulo

5 da un paso mas alla, partiendo de la seccion anterior, y esquematizando el proceso empırico

que de vida a la solucion buscada, especificando tambien las limitaciones de la misma. El

capıtulo 6 muestra los datos recolectados consecuencia de ejecutar los pasos de la seccion

anterior, esto con sus respectivas metricas formales. El capıtulo 7 presenta un breve com-

pendio acerca de todo el trabajado desarrollando, el analisis que se pueda realizar acerca del

contraste entre los objetivos esperados y los obtenidos, ası como los respectivos consejos di-

rigidos a la realizacion de trabajos del mismo topico o de alguno ıntimamente relacionado. Y

de ultimo, en la seccion 7.2 se muestra el listado de recursos teoricos y practicos consultados

para la realizacion de este TEG.

8

2. Marco Teorico

Este capıtulo se compone de dos secciones. En los Antecedentes (2.1) se describe el con-

junto de trabajos mas resaltantes relacionados a la solucion del problema de asignacion de

horarios, el enfoque y/o busqueda de un modelo de costos general para expresar las enti-

dades y restricciones del mismo, ası como las herramientas de software mas significativas

desarrolladas al respecto. En las Bases Teoricas (2.2) se cubren los conceptos mas importan-

tes del problema que permitan un entendimiento completo del marco general a tratar, ası

como una base lo suficientemente robusta para generar el conjunto de nuevos razonamientos

y planteamientos plasmados en las posteriores secciones.

9

2.1. Antecedentes de la investigacion

En paralelo a la naturaleza combinatoria y altamente compleja del problema de asigna-

cion de horarios, la mayorıa de las soluciones propuestas se ven restringidas por el contexto

en el que se aplican, y si bien contribuyen al aumento de la bibliografıa relacionada a tal

campo de investigacion, brindando mas herramientas para el abordaje de tal problema, aun

se dista de tener un modelo cercano a lo general para el tratamiento del asunto. Sin em-

bargo, eso no quita que existan propuestas que hayan jugado con la posibilidad de brindar

un enfoque general para el timetabling problem, ası como tratamientos del mismo usando

herramientas de computos heurısticos. Existen tambien obras, desde papers hasta libros y

disertaciones, orientadas exclusivamente al analisis abstracto de los elementos que forman

parte del problema de asignacion de horarios, esto es, desde crear formatos generales para

los datos de entrada, crear representaciones estandar para las relaciones entre los individuos

y las actividades y las restricciones asociadas a las mismas. Se pueden listar los siguientes

trabajos:

Muhammad Rozi Malim, Ahamad Tajudin Khadery Adli Mustafa (2005), “University

Course Timetabling: A General Model”: [84] es un artıculo de investigacion redactado

por integrantes de la Universidad de la Ciencia en Malasia. Mostrado en la 2da Con-

ferencia Internacional de Investigacion y Educacion Matematica el 2005, toma como

objeto de estudio el contexto universitario al ser un entorno rico en complejidad y

restricciones en comparacion a otros entornos de estudios. Construye el modelo clasi-

ficando cada una de las restricciones como obligatoria (hard) y opcional (soft). Cada

restriccion es representada como una variable matematica entera acompanada por una

constante c = 0 o c = 1, proponiendo entonces el llamado modelo general como un

problema de programacion [lineal] entera.

Matthias Grobner, Peter Wilke, y Stefan Buttcher (2003), “A Standard Framework

for Timetabling Problems”: [52] es el tıtulo de un trabajo realizado por integrantes

de la Universitat Erlangen-Nurnberg, en Alemania, y The University of Western, en

Australia. En el trabajo construyen en paralelo una propuesta de modelo general para el

problema de asignacion de horarios relacionada ıntimamente con el funcionamiento del

10

framework que proponen como solucion al problema. Argumentan que las propuestas

existentes poseen un nivel de degradacion al grado de especificidad de los algoritmos

de acuerdo al contexto en los cuales son implementados, y que poco sirve para avanzar

en las investigaciones en el campo. Generalizan los elementos asociados al timetabling

problem llamandolos entidades, y diviendolos en distintas clases: recursos, eventos y

restricciones. Realizan el debido proceso de documentacion mediante UML y en base a

ella crean una implementacion de lo que llaman GTL: General Timetabling Language,

realizada sobre Java. En resumen, se crea el codigo de formulacion del problema sobre

GTL, representando las mencionadas entidades mediante clases, y la carga de los datos

asociados a un contexto se realiza mediante ficheros XML.

Edmun Burke, Jeffrey Kingston (1997), “A standard data format por timetabling pro-

blem instances”: [31] es una revision teorica de los aspectos obligatorios que debe cubrir

una propuesta de modelo estandar para la formulacion del problema de asignacion de

horarios, resumidos en los siguientes puntos: (1) generalidad, el modelo debe brindar el

soporte suficiente para que cualquier restriccion e instancia de un problema cualquie-

ra sea expresable en terminos de las herramientas proveıdas por el modelo; (2) cada

instancia de problema debe poder ser representada completamente por el modelo, esto

incluye contemplar los recursos, los participantes, las restricciones ası como las pro-

puestas de soluciones; (3) debe ser posible la conversion bidireccional de un problema

expresado con el modelo estandar con los distintos formatos de modelos existentes en

este campo de investigacion. El trabajo identifica que el problema central reside en la

dificultad atada invariablemente a la tarea de reducir expresiones complejas genericas

que incluyen elementos de teorıa de conjuntos, logica formal y de predicados a una

serie de directivas incluidas en librerıas, ası como la imposibilidad de cubrir todas las

conversiones posibles a los otros modelos existentes en un momento dado, aunque el

trabajo busque minimizar tal falla inherente al contexto. Al final, el modelo de lenguaje

que presentan incluyen combinados entre si elementos que van desde la programacion

imperativa hasta la programacion logica.

Michael Marte (2002), “Models and Algorithms for School Timetabling - A Constraint-

11

Programming Approach”: [51] es una tesis acerca del problema de asignacion de horarios

en relacion con el sistema de educacion media en Alemania, que asemeja mas no iguala,

en cuanto a complejidad de situaciones, al sistema universitario. Parte de la premisa

de la necesidad de establecer un sistema robusto de restricciones que emule de la mejor

manera posible el problema de asignacion de horarios asociado al Gymnasium aleman.

Luıs Paulo Reis y Eugenio Oliveira (2001), “A Language for Specifying Complete Ti-

metabling Problems”: [81] se identifican en este trabajo ocho versiones principales del

timetabling problem, y basados en ellos se presenta un nuevo lenguaje descriptivo lla-

mado Unilang, para la representacion de los problemas de asignacion de horarios. Este

va enfocado a servir como lenguaje adaptable para cualquier version del problema,

ofreciendo una representacion clara y concisa de los datos, las restricciones, medidas

de calidad ası como soluciones para cada una de las version del problema como la

asignacion de horarios para universitarios o para examenes.

Jeffrey Kingston (1999), “Modelling Timetabling Problems with STTL”: [62] artıculo

que explora las ventajas e inconvenientes presentados al intentar modelar problemas

del mundo real usando el Standard Timetabling Language.

David Ranson y Samad Ahmadi (2007), “An Extensible Modelling Framework for the

Examination Timetabling”: [80] en este trabajo los autores plantean que si bien el abor-

daje del timetabling problem con el objetivo de lograr una generalizacion del problema

ha sido ya realizado varias veces, argumentan que hasta el momento las opciones ofreci-

das no simplifican el proceso de modelado, carecen de caracterısticas claves para lograr

una mayor optimizacion en los resultados finales, y en ultima instancia ofrecen pocos

avances en comparacion a soluciones analogas ya existentes en lenguajes de programa-

cion ya establecidos en la comunidad. Para solucionar tal problema, proponen crear un

framework de modelado independiente del lenguaje a usar a posteriori, usando STTL.

Si bien al final del documento queda como trabajo en progreso, los planteamientos rea-

lizados a lo largo del documento son de utilidad para cualquiera que desea abordar la

misma tematica, a fin de generar nuevos resultados.

12

Jeffrey Kingston (2006), “Data Formats for Exchange of Real-World Timetabling Pro-

blem Instances and Solutions”: [60] realizado por el mismo autor del STTL, realiza los

siguientes planteamientos:

◦ La dificultad del modelado va intrınsecamente asociada a la larga cantidad de

requerimientos asociados al contexto. Esto se ha tratado de solucionar desde dis-

tintos enfoques, como lo son usando tecnologıas de la web semantica, modelado

orientado a objetos, usando programacion con restricciones, entre otros.

◦ A fin de no incurrir en la sobrecarga de informacion, deben establecerse cotas

asociadas a cuales variaciones del timetabling problem se pretende abarcar con la

propuesta de modelo general que se quiera realizar. Esto es, una vez definida la

cota y desarrollado una solucion basada en la misma, se propone a futuro volver

a redefinir la solucion extendiendo la cota superior en la que se basa la solucion

previa.

Ender Ozcan (2013), “Towards and XML base standard for Timetabling Problems:

TTML”: [70] busca solucionar el problema asociado a las dificultades de reusar los

datos de entrada y salida de otras propuestas de solucion al timetabling problem, crean-

do un nuevo formato de data en XML que se basa a su vez en MathML [90].

Moritz Muhlenthaler(2014), “Fairness in Academic Course Timetabling”: [75] luego de

realizar un analisis exhaustivo del Problema de Asignacion de Horarios en entornos uni-

versitarios, el autor se enfoca en como se puede formalizar y medir la equidad asociada

a la asignacion de individuos y actividades, terminando con un caso de estudio a fin de

probar la efectividad de sus planteamientos.

Simon Kristianse, Thomas Jacob Riss (2013), “A Comprehensive Study of Educational

Timetabling - a Survey”: [63] se encarga de realizar una descripcion extensiva del estado

del arte de un problema en cuestion, en este caso el problema de asignacion de horarios,

evalua las principales formalizaciones para cuatro principales versiones del problema,

usando datos de la vida real a fin de ofrecer medidas de calidad de las soluciones plan-

teadas.

13

De igual manera se puede encontrar en la red multitud de software que trata el timetabling

problem (no confundir con el software de agenda). En otros terminos se les conoce como

software para la creacion automatica de horarios una vez que se carga la informacion aso-

ciada a las entidades y restricciones de la instancia a trabajar. Entre los mas resaltantes se

encuentran:

FET [43] : es un software de codigo abierto creado en C++ para la generacion au-

tomatica de horarios de escuelas, liceos y universidades una vez cargada la informacion

asociada principalmente a profesores, asignaturas, aulas, estudiantes, entre otras. Sus

siglas se pueden interpretar como Free Evolutionary Timetabling, dado que de acuerdo

a los autores el conjunto de las restricciones varıa continuamente. Segun la descripcion

oficial, trata con un algoritmo “rapido y eficiente”, en contraste con el hecho de que en

el peor de los casos, cuando las restricciones cargadas son muy elaboradas, en el peor

de los casos el tiempo varia de cinco minutos a horas.

UniTime: University Timetabling [89] es un software distribuido bajo licencia de codigo

abierto, creado en Java para manejar con el mayor nivel de granularidad posible el pro-

blema de asignacion de horarios, a fin de minimizar en la medida posible la coincidencia

de horarios para las actividades de un estudiante u otro participante en la organizacion.

Su elemento mas distinguido es la Librerıa de Resolucion de Restricciones (Constraints

Solver Library), basado en una combinacion de “busqueda hacia adelante” iterativo

con conjunto con busqueda local, extendiendo sus capacidades a considerar todas las

soluciones consideradas como optimas, pero que no sean necesariamente completas. En

el proceso, los candidatos a soluciones deben ir cumpliendo cada una de las restric-

ciones contempladas en el sistema, sin excepcion. Para colaborar en la investigacion

asociada al problema de asignacion de horarios, el personal humano asociado a la crea-

cion y mantenimiento de este software ha liberado todo el trabajo relacionado bajo

licencias GNU, ademas de brindar en su web un listado de todas las publicaciones y

presentaciones en las cuales han colaborado.

14

En otro contexto, desde 1995 se celebra cada dos anos una serie de conferencias interna-

cionales acerca de la teorıa y practica del timetabling automatizado (PATAT, Practice and

Theory of Automated Timetabling) [76], en la que participa un cumulo de investigadores,

practicantes y relacionados de alguna manera a todo lo que tenga ver con el abordaje del

problema de asignacion de horarios. Entre los topicos tratados se encuentran los diferentes

tipos de horarios, manejo de restricciones, inteligencia artificial, metaheurısticas, grafos, entre

muchos otros, que van desde los aspectos formales del problema hasta sus representaciones

practicas.

Patrocinado por PATAT existe tambien existe la ITC – International Timetabling Compe-

tition [57], donde se ponen a prueba a los participantes para usar sus propuestas de soluciones

con problemas compuestos de restricciones tomada del mundo real, ası como otras creadas

especıficamente para la competencia. Es de notar que el software mencionado anteriormente,

UniTime, fue uno de los ganadores de tal competencia en su edicion del 2007, obteniendo

dos de los tres principales premios posibles.

2.2. Bases teoricas

2.2.1. Investigacion de operaciones

Campo multidisciplinario (posee componentes de matematicas, logica, ingenierıa, compu-

tacion, entre otros) encargado de la optimizacion del uso de recursos para la ejecucion de

distintas tareas [87]. Enfatiza en el uso de modelados matematicos, espacios de soluciones

factibles y no factibles ası como los subconjuntos asociados a tales espacios, y la repeticion

intensiva de calculos para optimizar las soluciones temporales encontradas. Tales elementos,

combinados entre sı, dan pie para que en la investigacion de operaciones se establezca que el

elemento de mayor importancia en la resolucion de un problema es la definicion del mismo,

y que el modelo general de solucion se defina en base al predicado maximizar o minimizar

una o mas funciones objetivos sujeto a un conjunto de restricciones [55].

15

2.2.2. Problema de asignacion de horarios [38] [36] [58]

Termino con el cual se denota el problema que envuelve asignar un conjunto de recursos

finitos en espacio y tiempo a una serie de actividades (comunmente academicas) que van a

ser realizadas por distintos componentes (maquinas, humanos), los cuales tambien poseen

limitaciones en cuanto a cantidad de tareas que pueden realizar, por cuanto tiempo pueden

hacerla, ası como cuales pueden ejecutar y cuales no (dependencia condicional). El problema

se formula inicialmente teniendo un conjunto de restricciones (analogo al enfoque de inves-

tigacion de operaciones), donde cada restriccion puede ser obligatoria (hard constraint), es

decir, para solucionar una instancia dada debe cumplirse esa restriccion obligatoriamente;

u opcional (soft constraint), es decir, la restriccion no es obligatoria pero en caso de que se

pueda incluir como parte de la solucion de una instancia dada, mejorarıa la calidad de la

misma.

El termino timetabling problem engloba distintas variantes que comparten la misma logica

de fondo. Entre las principales, en sus versiones mas basicas se tienen:

STP (School Timetabling Problem): la version mas basica del problema, y por lo

general resoluble facilmente de manera manual, busca asignar a los distintos estudiantes

de un sistema de primaria, a sus respectivos salones de clases.

BACP (Balanced Academic Curriculum Problem): dado los siguientes elemen-

tos:

◦ Un conjunto de asignaturas.

◦ Una carga asociada a cada asignatura.

◦ Sistema de prelaciones entre las asignaturas.

◦ Un conjunto de perıodos academicos.

◦ Un carga academica maxima permitida por cada perıodo.

En esta variante se busca distribuir el conjunto de asignaturas entre todos los perıodos

academicos, respetando las restricciones planteadas y minimizando la diferencia entre

las cargas academicas por cada perıodo.

16

ETP (Employee Timetabling Problem): dados los siguientes elementos:

◦ Un conjunto de actividades, cada una con una dificultad asociada.

◦ Un conjunto de individuos, cada una con una carga maxima de actividades a afron-

tar. Este formato de problema es el que mas se aborda en los problemas iniciales

de programacion lineal, se busca cubrir la realizacion de todas las actividades,

respetando las restricciones planteadas. Dependiendo del contexto, se suele contar

con un criterio de desgaste por cada individuo, ası como por ejemplo la dificultad

de una actividad varıe dependiendo del individuo.

ETP (Examination Timetabling Problem): dados los siguientes elementos:

◦ Un conjunto de pruebas

◦ Un conjunto de estudiantes, cada uno a la espera de presentar una de las pruebas.

◦ Una lista de bloques horarios.

◦ Salones de clase, cada uno con una capacidad maxima de estudiantes.

Se busca cubrir de manera eficiente la asignacion estudiantes - prueba - salon de clases,

sin incumplir las restricciones impuestas. Al ser una triple asignacion, las soluciones

creadas para este tipo de problemas suelen dividir el problema principal en subproble-

mas.

SSP (Student Sectioning Problem): por lo general, cuando se habla de que un

conjunto de estudiantes cursa o cursara una asignatura, esta asignacion se encuentra

con el inconveniente en que los salones de clases disponibles no presentan la capacidad

suficiente para acoger a todos los inscritos. Es aquı en donde entra el proceso de seccio-

namiento, en donde se realizan las divisiones optimas para luego distribuir cada seccion

de estudiantes en los salones de clases, y conceptualmente cada uno estarıa viendo una

asignatura distinta.

UCTP (University Course Timetabling Problem): una de las versiones mas

abordadas en el campo de investigacion del timetabling problem, es el que suele poseer

la mayor cantidad de individuos, actividades, relaciones entre esos dos componentes

17

ası como restricciones sobre tales restricciones. Tal sobrecarga de componentes en un

solo problema conlleva a asumir enfoques que dividan el problema principal en sub-

problemas, y mecanismos ya probados que interrelaciones los resultados de unos con la

entrada de otros, buscando soluciones factibles en tiempos cortos.

2.2.3. Complejidad algorıtmica

Un algoritmo es una secuencia de pasos ordenados para resolver un problema. Cada uno

de los pasos, o el conjunto de los mismos es expresable mediante operaciones matematicas

y logicas, las cuales varıan de forma de acuerdo al paradigma de programacion que se este

usando al momento. [37]

Comunmente se asocia a un algoritmo un tamano n el cual es un valor natural asocia-

do al tamano de los datos de entrada que seran evaluados por el programa. En base a ese

tamano n, se determina un orden de complejidad, que es un valor real obtenido mediante

tecnicas de analisis de complejidad de algoritmos [45]. Este valor es determinado en base al

analisis del algoritmo ante el peor de los casos que se puedan presentar. Este peor caso es

planteado mediante el modelo de analisis que se este usando [49]. Ası, si el estudio se hace

mediante un analisis asintotico, se realizan entonces los calculos de complejidad asociados

con una cantidad lımite de data de entrada, la maxima cantidad iteraciones a ser ejecutada

para cada bucle del algoritmo en el caso de la programacion imperativa ası como en una

decision condicional, hacer los calculos en base a la mayor complejidad de cada una de las

posibles condiciones a ejecutarse. [88] [26]

La notacion mas usada para realizar analisis de complejidad de algoritmos es la notacion

O-grande, que trabaja con el ya nombrado analisis asintotico [88], donde se define una funcion

g(n) que viene a ser peor valor en tiempos de ejecucion para el algoritmo dada una entrada

de tamano n.

En base a lo anterior se define brevemente que [88]:

Un algoritmo de tiempo polinomial es aquel que posee un orden de complejidad O(p(n)),

18

donde p(n) es una funcion polinomial (complejidad P).

Los algoritmos que no entran en la categorıa anterior son algoritmos de complejidad

no polinomial (complejidad NP).

Un algoritmo es de tiempo exponencial si la complejidad asociada es O(cn), donde

c ≥ 1.

Si un algoritmo es la solucion a un problema, y cada algoritmo posee una complejidad

asociada, se define la complejidad de un problema como la complejidad asociada al mejor

algoritmo creado para resolver tal problema. [54]

Conocer el orden de un complejidad de un problema es un problema de decision porque en

la teorıa de algoritmos los problemas se encuadran en dos clases principales de complejidad:

polinomial y no polinomial, ya mencionados anteriormente. Estas clases de complejidad se

dividen en subclases de manera recursiva. [64]

Figura 1: Clases de complejidad [88]

Un problema de clase de complejidad P (de ahora en adelante clase P) son problemas

resolubles en tiempos polinomiales en el peor de los casos [61]. La clase de interes para el pro-

yecto actual es la clase de complejidad NP (de aquı en adelante clase NP). Son problemas que

en promedio para el caso estandar o el peor de los casos son resolubles en tiempo polinomial

por algoritmos no determinısticos, dado que si se abordan con estrategias determinısticas

su tiempo de solucion puede llegar al orden de anos o siglos [35]. Uno de los problemas del

19

milenio plantea la interrogante: ¿P=NP? [34]

Esta demostrado que el Problema de Asignacion de Horarios es un problema NP-completo.

[42]

2.2.4. Programacion con restricciones

Es un paradigma de modelado y busqueda orientado a satisfacer un conjunto de restriccio-

nes [27]. Es una de las principales estrategias a aplicar en problemas que dada su naturaleza

poseen una alta cantidad de restricciones, cada una con una cantidad importante de condi-

ciones a satisfacer. [56]

Dado un problema X, una solucion al problema se puede plantear como un vector de

valores V = (v1, v2, . . . vn). Un algoritmo inicial buscarıa la solucion optima al problema

analizando todas las combinaciones de valores para el vector V , lo cual teoricamente es

valido, pero ineficiente cuando la cantidad de combinaciones es alta (en este caso, es n!) [59].

La programacion con restricciones aprovecha la posibilidad de definir un problema como un

conjunto de condiciones que la solucion debe cumplir para ser valida, reduciendo ası el espacio

de busqueda inicial ası como los subsecuentes caminos a seguir para hallar una solucion valida

y optima.

2.2.5. Propagacion de restricciones [25] [28] [41] [53]

Dado un modelo de restricciones, definido en base a un conjunto de variables y restriccio-

nes de valor aplicadas sobre las mismas, se entiende a la propagacion de restricciones como

el proceso de determinar como las restricciones y los posibles valores de una variable pueden

afectar los posibles valores de otras variables. Tal proceso desemboca en la re-formulacion

del modelo original, todo esto encaminado a reducir el numero de decisiones a tomar a la

hora de hallar la solucion (haciendo con esto analogıa al proceso de resolver un modelo de

restricciones como una busqueda).

Tal proceso de refinacion del modelo se logra ya sea reduciendo el dominio de las variables

20

involucradas, creando y/o eliminando variables y/o restricciones. Un algoritmo de propaga-

cion de restricciones se conoce comunmente como ”propagador”. Un esquema resumido de

como se comporta serıa el siguiente:

Cuando una variable X cambia de valor, el sistema evalua el dominio de cada variable

Yi dependiente de X. Esto genera nuevos dominios para cada una de ellas.

Por lo general, cada nuevo dominio de una variable Yi es subconjunto del dominio de

esa misma variable Yi previo al cambio de valor de X.

Ahora, cada variable Yi se convierte en una variable X, y se repite el proceso de ma-

nera recursiva, hasta llegar a un punto de parada, que varıa dependiendo del tipo de

propagador que se este usando.

Entre los principales tipos de propagadores, se tienen:

Node consistency.

Arc consistency.

Hyper-arc consistency.

Directional arc consistency.

Path consistency.

Directional path consistency.

2.2.6. Modelado cientıfico

Es una actividad cientıfica orientada a convertir un componente del mundo real en al-

go mas facil de entender, definir, cuantificar, visualizar y/o simular, usando mecanismos,

conceptos y herramientas aceptados por la comunidad cientıfica. Si bien la totalidad de los

modelos existentes no dejan de ser solo aproximaciones a aquello que desean representar, su

utilidad esta exenta de prueba en lo que concierne a entender los fenomenos que comunmente

acontecen. Entre los principales tipos de modelos se tienen:

21

Modelos cualitativos vs cuantitativos: los primeros basan su esencia en la descrip-

cion mas que todo verbal del objeto a modelar, mientras que los segundos se construyen

mediante unidades de medida, interrelaciones de entidades y formulacion de procesos

mediante basamentos logico-matematicos.

Modelos deductivos vs inductivos: un modelo deductivo trabaja con un enfoque

top-down, esto es, va desde lo mas general hasta lo mas especifico. En otras palabras,

parte desde una teorıa general (dentro del marco de abstraccion en el cual este tra-

bajando), y va descomponiendo la misma en un conjunto de ”sub-postulados”tambien

validos, repitiendo el proceso de manera cıclica, hasta que un elemento desconocido es

tomado como cierto, ya que esta respaldado por el proceso previo realizado. Mientras

que un modulo inductivo usa el enfoque bottom-up, el cual empieza con observacio-

nes especıficas, y mediante la identificacion de patrones y elementos regulares, termina

formulando una o mas hipotesis que al ser probadas y resultan ser ciertas, derivan en

conclusiones o teorıas generales.

Modelos deterministas vs estocasticos: un modelo determinista describe el com-

portamiento de un objeto o fenomeno como algo completamente condicionado por su

estado inicial. Esto es, para los mismos datos de entrada, siempre se tendran los mismos

valores de salida. Mientras que en un modelo estocastico o probabilista el resultado no

es tan directo, ya que los valores de entrada se ven influenciados en los procesos internos

del modelo por mecanismos de aleatoriedad.

Modelos universales vs especıficos: los primeros buscan simular procesos que sean

convertibles a traves de distintos dominios e instancias del mismo problema, mientras

que los segundos solo trabajan en un dominio unico, ası como en conjuntos de datos

adaptados a ese unico dominio del problema.

Entre los puntos mas importantes a recalcar acerca de un modelo cientıfico se tiene:

Estos son construidos cuando el nivel de factibilidad asociado a reproducir empırica-

mente las condiciones y/o el fenomeno a estudiar es bajo o nulo.

22

La puesta en marcha del modelo se conoce como simulacion, y genera resultados a ser

evaluados para verificar principalmente si el modelo cumple el objetivo para el cual fue

creado.

Un modelo estructurado adecuadamente debe cubrir los pasos de observacion y reco-

nocimiento de todos los patrones y relaciones existentes en el objeto real.

Generar/construir el modelo implica asumir un adecuado nivel de abstraccion, que varıa

de acuerdo al problema.

La evaluacion de un modelo conlleva a tener en cuenta los siguientes factores:

◦ Habilidad para describir las observaciones previas.

◦ Habilidad para predecir, con margenes de error mınimos, futuras observaciones.

◦ Costo de usar el modelo en comparacion a otros con los mismos objetivos.

◦ Simplicidad.

23

3. Planteamiento del Problema y Justificacion

Este capıtulo se compone de cuatro secciones. En el Contexto del Problema (3.1) se des-

cribe brevemente dos puntos: los contextos en donde suele ubicarse el problema de asignacion

de horarios, y el contexto escogido para desarrollar el presente TEG, que dara pie para en-

tonces escoger, capıtulos mas adelante, determinados casos de prueba. En la Definicion del

Problema (3.2 se presenta lo que se entiende en este trabajo por el timetabling problem, y

sera este el concepto a usar en el posterior desarrollo. En los Objetivos de la Investigacion

(3.3) se detallan los objetivos generales y especıficos a alcanzar por este trabajo. Mientras

que en la Justificacion e Importancia del tema a tratar (3.4) se presentan el conjunto de

razones que sustentan la realizacion de este trabajo, amparadas en conjunto por la necesidad

ya descrita de aumentar la sistematizacion en cuanto a recoleccion de esquemas y modelos

de restricciones del problema de asignacion de horarios.

24

3.1. Contexto del Problema

El problema de asignacion de horarios se encuentra en todos aquellos ambitos en los

que la planificacion de actividades con relacion a los recursos disponibles, tanto en tiempo

como en mano de obra o similares, es un asunto crıtico. El caso a desarrollar tanto en

terminos teoricos, como a la hora de estructurar los casos de pruebas y las simulaciones,

corresponde al timetabling problem asociado a entornos academicos, esto es, escuelas, liceos

y universidades [30]. La complejidad de cada formulacion es proporcional al nivel academico

el cual se este trabajando, ası, el problema de asignacion de horarios en una escuela suele

ser un problema no pocas veces resoluble con algoritmos deterministas, mientras que en una

universidad la regla es que se usen metaheurısticas, que no es mas que la combinacion de

varias heurısticas, con el fin de aproximarse a soluciones optimas o en su defecto aceptables.

3.2. Definicion del problema

Tomese en cuenta que en un entorno de trabajo la realizacion de una serie de tareas

es la actividad central del mismo. Una medida de optimalidad en el llevado a cabo de las

mismas esta basada en el orden en que son realizadas unas con respecto a las otras, ası como

la ubicacion en el tiempo de cada una de ellas. Todos estos elementos teoricos entran en el

marco de la investigacion de operaciones [91], donde se busca dado un conjunto de recursos

para la realizacion de tareas, optimizar el uso de los mismos.

El problema de asignacion de horarios (interpretacion del termino anglosajon timetabling

problem) busca en su version mas basica distribuir la realizacion de un conjunto de tareas

atados a dos restricciones obligatorias:

Cantidad de espacio limitada.

Cantidad limitada de bloques horarios.

Al ser un problema combinatorio NP-completo [42] la busqueda de soluciones optimas

suele estar muy influida por el contexto en el cual se evalua el problema, ası, las alternativas

25

algorıtmicas planteadas se ven altamente atadas en cuanto a modelado de acuerdo al pro-

blema especıfico tratado (un departamento universitario o un ente del gobierno). Es decir,

mientras se busca elevar la cota de optimalidad de las soluciones generadas, el algoritmo de-

genera hasta convertirse solo util para un numero reducido de contextos, con particularidades

especıficas.

Ahora bien, hay dos segmentos bien delimitados, pero para nada independientes, en la

resolucion del timetabling problem. Esto es:

El modelo de restricciones que representa el problema a resolver.

El conjunto de algoritmos a usar para solucionar el modelo. Entiendase por solucion la

asignacion de individuos a actividades redundando en la superacion de una cota mınima

de optimalidad.

El presente trabajo se encarga de optimizar los procesos asociados al primer elemento,

mientras que el segundo, asociado a la busqueda, de la solucion queda excluido.

Los principales problemas asociados a la construccion de un modelo de restricciones para

una instancia del timetabling problem son los siguientes:

La rigidez en su estructura. Un diseno demasiado atado al problema para el cual fue

creado resulta inutil cuando la instancia origen cambia, haciendo incluso necesario

volver a re-formular todo el sistema.

La optimalidad asociada al modelo de restricciones (existen metricas que calculan la

misma) incide directamente en la factibilidad a la hora de construir una solucion factible

al problema.

En relacion al problema de la rigidez, un modelo flexible entonces va orientado a que

la mayor cantidad de instancias del timetabling problem puedan ser representadas bajo

el modelo, sin que en el proceso de transformacion se pierda informacion alguna.

26

El lenguaje usado para el modelo suele causar limitantes a la hora de usarlo. Esto es,

al construirlo en un lenguaje de uso especifico, genera una carga adicional de trabajo

en caso de que sea necesario usarlo bajo otras tecnologıas.

3.3. Objetivos de la investigacion

3.3.1. Objetivos Generales

1. Crear un modelo de costos que contemple la naturaleza dinamica de las restricciones de

una instancia cualquiera del problema de asignacion de horarios, usando herramientas

de modelado y tomando en cuenta las debilidades de los planteamientos previos con el

fin de superar la rigidez de modelos de restricciones ya existentes.

2. Usar un recurso algorıtmico que trabaje sobre el modelo construido y, en conjunto

con datos provenientes de la instancia a resolver, realice un proceso de reformulacion

del mismo, optimizando su estructura y con miras a optimizar los calculos futuros de

resolucion del sistema.

3.3.2. Objetivos Especıficos

1.1 Realizar un estudio intensivo del estado del arte del problema de asignacion de horarios,

en especıfico el manejo de las restricciones, con el fin de asegurar la mayor cantidad de

herramientas disponibles para el modelado del proyecto actual.

1.2 Crear un modelo de costos usando basamentos formales logicos y matematicos para un

conjunto dinamico de restricciones.

2.1 Construir el esquema algorıtmico de alto nivel que trabajara sobre el modelo de costos

y restricciones construido en el paso anterior para la reformulacion del mismo.

2.2 Implementar el esquema algorıtmico en lenguaje de programacion, y probar el com-

portamiento del mismo usando conjuntos de entrenamiento pertenecientes a diversos

contextos.

27

3.4. Justificacion e importancia del tema tratado

Se piensa que el planteamiento de una solucion para el timetabling problem que contem-

ple un modelado robusto para un conjunto dinamico de restricciones que ademas supere la

tradicional dicotomıa de restricciones obligatorias y opcionales, asignando una medida de

importancia especıfica a cada una conllevarıa a un avance positivo en las investigaciones de

dicho campo.

La realizacion de actividades es, sin necesidad de extenderse demasiado al respecto, el eje

central de la existencia de cualquier organismo. Y en la sociedad industrializada, en donde

la planificacion toma mas importancia conforme aumenta la complejidad de las relaciones de

trabajo, la necesidad de automatizar procesos que solucionados de otra manera (manualmen-

te por ejemplo) tomarıan mas tiempo del necesario cobra mayor importancia. El desarrollo

de un topico desde una perspectiva global, y que busque abarcar en terminos solventes al

menos las principales versiones de un problema, siempre ofrecera la oportunidad de revisar

nuevos aspectos del problema consecuencia de las conclusiones a las que se logre llegar.

De esta manera, los resultados que se obtengan de este trabajo no deberıan limitarse a su

aplicacion al contexto indicado mas arriba, sino que pueden servir tambien como medidores

en contextos de la misma naturaleza.

28

4. Marco Metodologico

Este capıtulo se compone de dos secciones. En la Descripcion de la Metodologıa (3.1) se

presenta el Protocolo de Modelado, el cual no es mas que una serie de pasos a seguir para la

construccion de un modelo matematico y/o logico, mientras que en la seccion de Aplicacion de

la Metodologıa (4.2) los pasos anteriores toman vida para comenzar con el diseno del modelo

general que es el objetivo general del presente trabajo, yendo desde el esclarecimiento final

sobre el objetivo del modelado, pasando por el modelado conceptual, la parametrizacion del

modelo, la escogencia del codigo y recursos de software para la ejecucion de las simulaciones

y pruebas, y la creacion del esquema con el cual se presentaran los resultados finales.

29

4.1. Descripcion de la metodologıa

Se perfila que el trabajo genere como producto principal el modelo general de restricciones

para el timetabling problem.

El modelado cientıfico toma un ente de la realidad y lo convierte en un conjunto de pos-

tulados formales basados principalmente en elementos logicos y matematicos que describen

el comportamiento de tal ente conforme a las caracterısticas que se desean estudiar [32] [47].

Se define la siguiente trilogıa:

Figura 2: Trilogıa Modelo - Algoritmo - Programa [32]

Existen otros dos elementos que brindan robustez a la metodologıa de modelado ma-

tematico, como lo son el esquema general del modelo y el protocolo de modelado.

El esquema general gira alrededor del postulado de la validez universal del principio causa-

efecto. Los elementos que conforman este principio son adaptados al contexto en el cual se

aplica. En un escenario se transfiere energıa, en otros informacion.

El modelo se clasifica de acuerdo a sus caracterısticas [48]. Existen muchos tipos de

modelos, ası como subtipos, y de la misma manera tal clasificacion no necesariamente se

establece al terminar de construirlo. Tambien se puede inferir sobre que clase de modelo es,

respondiendo preguntas durante el proceso de creacion que esclarezca que decisiones tomar

30

Figura 3: Esquema general del modelo matematico. [32]

de acuerdo a que herramientas usar y cuales no.

4.1.1. Protocolo de Modelado

1. Definicion del objetivo del modelado: debe responder a las preguntas ”¿para que

modelar un proceso?”, ”¿para que modelar los procesos relacionados a las restricciones

del problema de asignacion de horarios?”. Siendo la seccion inicial del protocolo, si

bien no todas las ideas que puedan generar los investigadores seran plasmadas aquı,

es importante que se planteen aquı todos los puntos crıticos asociados al objetivo del

modelado: las hipotesis, establecer el tipo del modelo, alcances y limitaciones entre otros

elementos. No posee una estructura definida, y dependera de la esencia del modelo que

se este construyendo.

2. Formulacion del modelo conceptual: teniendo un marco establecido en cuanto a

nivel de factibilidad del trabajo a realizar, el modelo conceptual establece la complejidad

de los procesos y elementos a tomar en cuenta para el modelado. Al mismo tiempo, se

identifican tambien los elementos pertenecientes al modelo, y como se relacionan entre

sı, el alcance del modelo o, en otras palabras, sus limitantes.

3. Tipo de modelo a usar: consecuencia del paso anterior, se puntualiza que tipo de

modelo es mas adecuado usar. Puede ser puro o compuesto, esto de acuerdo a las

31

necesidades. Conforme al tipo de modelo escogido, se explica el porque de la eleccion,

y esto mas que todo esta condicionado a las caracterısticas lo cual lo ubican dentro de

determinada categorıa.

Figura 4: Primera etapa del protocolo de modelado [32]

4. Seleccion del codigo a aplicar: basado en el tipo de modelo a usar, se investiga la

disponibilidad de codigo, librerıas y cualquier otro soporte de software relacionado al

mismo y que sirva de apoyo para el desarrollo de la aplicacion que trabajara sobre la

construccion, testing y validacion del modelo, ası como de los resultados que se generen

de los procesos ya mencionados. Es aplicable la creacion de codigo propio, y este ultimo

es obviamente imprescindible para cuando la existencia de herramientas que den soporte

al producto a construir sea casi nula.

5. Parametrizacion del modelo: se establecen las magnitudes de los parametros que

forman parte de la estructura matematica. Los elementos identificados y plasmados

en el modelo conceptual son traducidos a definiciones formales en terminos logicos y

matematicos, principalmente. Esto incluye variables, relaciones, restricciones, ası como

alcances y limitaciones del modelo en su generalidad.

32

Figura 5: Segunda etapa del protocolo de modelado [32]

6. Validacion del modelo: mientras que el paso anterior establece el rango de valores

a trabajar para cada uno de los parametros del modelo, este ultimo se prueba ahora

con un conjunto de valores de prueba que esten fuera de tales rangos, recolectando

los resultados obtenidos. A tal conjunto de resultados se les asocia una medida de

error de acuerdo al criterio de validacion que se este usando. El modelo construido sera

considerado valido a efectos de uso cuando tal medida de error se encuentre dentro de

un lımite considerado permisible.

7. Simulacion: el modelo construido entra en fase de uso con casos de prueba definidos

sistematicamente, con el fin de obtener la informacion suficiente para el paso final.

Si bien ya es una practica general, vale recalcar que queda como implıcito que estas

simulaciones son computacionales, ası que tambien es importante especificar las espe-

cificaciones de las plataformas en donde se realicen tales simulaciones.

La construccion y/o recoleccion de casos de prueba debe ser realizada de manera sis-

tematica y ordenada, para ası tener un control preciso sobre el contraste que se realice

entre los resultados obtenidos y los esperados (en las hipotesis previas).

8. Analisis y presentacion de resultados: se verifica la coherencia de los resultados

33

Figura 6: Tercera etapa del protocolo de modelado [32]

obtenidos en el paso anterior, soportado tambien por el momento en que se supero la

validacion del modelo, para ası construir el documento formal que de soporte a la toma

de decisiones, ası como la construccion de las conclusiones y recomendaciones.

4.2. Aplicacion de la metodologıa

4.2.1. Definicion del objetivo del modelado

El problema de asignacion de horarios es un problema combinatorio NP-completo [66]. No

existe una sola version del mismo, sino que esta varıa dependiendo del contexto del proble-

ma. Esta variacion se define mediante cambios en la naturaleza y estructura de sus variables,

relaciones entre las mismas, restricciones sobre los dominios de las variables y sobre tales

relaciones. Si bien persiste un patron comun en cuanto el nucleo del problema, independiente

de las versiones que tenga el mismo, el comun de las soluciones existentes se basa en el alto

grado de diferencia que hay entre cada una de ellas consecuencia de crearlas condicionadas

en su totalidad a la instancia especıfica que se desea resolver.

34

El proceso general de solucion al problema se divide en la fase de modelado y la fase al-

gorıtmica. La segunda trabaja sobre lo construido en la primera. Esto trae como consecuencia

que la efectividad asociada a la estructura del modelo influya directamente en la calidad de

la solucion algorıtmica.

En cuanto a la bibliografıa que trata acerca de las soluciones al problema de asignacion de

horarios (en sus distintas variantes), la mayorıa se concentra mas en los procesos algorıtmicos

que en la fase de modelado, siendo esta ultima ubicada como un elemento trivial en compa-

racion a los algoritmos desarrollados para tratar el problema.

Entonces, durante el desarrollo del modelo se busca responder las siguientes interrogantes,

con el fin de tener un producto consistente:

¿Que se busca?

◦ Aportar al fortalecimiento de la bibliografıa relacionada a la construccion de mo-

delos.

◦ Desarrollar un esquema base orientado en principio a unificar una lista definida

tomada de las principales variantes del timetabling problem en un sistema que per-

mita luego reformular el modelo usando como datos la informacion de la instancia

a resolver, todo esto orientado a la optimizacion de los calculos algorıtmicos que

resuelvan el problema.

◦ El modelo creado (entendiendose por modelo tanto los esquemas conceptuales aso-

ciado al mismo como los mecanismos de reformulacion y optimizacion basado en

los casos de prueba) va orientado a ser independiente de plataformas y lenguajes de

programacion. En otras palabras, debe ofrecer los mecanismos (teoricos y empıri-

cos) mınimos necesarios para que su interfaz de entrada-salida sea re-usable en la

mayor cantidad de contextos asociados al problema de asignacion de horarios.

¿Que se sabe?: Esto es cubierto en la seccion del modelado conceptual (4.2.2). Se

expresa verbalmente y mediante graficos las entidades que se han identificado del pro-

35

blema, las relaciones entre las mismas, y los resultados (propiedades emergentes del

sistema) de operar ambos elementos.

¿Que se puede asumir?: descrito tambien la seccion del modelado conceptual (4.2.2),

las suposiciones que se realizan con respecto al problema a modelar son concentradas

en terminos conceptuales en lo que sera tratado como las entradas del modelo general

del problema de asignacion de horarios.

¿Como deberıa ser visto este modelo?: cada una de las caracterısticas del modelo

a construir lo condicionan a formar parte de ciertos conjuntos de modelos cientıficos

(cubiertos en la seccion (4.2.3)), los cuales definen la respuesta a tal interrogante. Ası

mismo, y en terminos generales, el trabajo presente se orienta principalmente a pre-

sentar el modelo como una especie de plantilla base en la cual deberıan confluir, si no

todos, un segmento significativo tanto en cantidad como en relevancia de las instancias

del timetabling problem.

¿Los resultados obtenidos coinciden con las hipotesis planteadas?: esta pre-

gunta es respondida convenientemente en la seccion de Hipotesis Iniciales (6.2.1) y

en la seccion de Resultados Obtenidos (6.2.2). Los elementos a analizar en las simu-

laciones del modelo son expuestos en la seccion de Metricas de Evaluacion (6.1.3).

¿Como sera usado este modelo?: respuesta cubierta mas extensamente en la seccion

de (7.1), basicamente dependiendo de los resultados obtenidos, si son alcanzadas las

hipotesis planteadas, el modelo entonces deberıa servir para avanzar en la creacion de

un marco de trabajo para el problema investigado que gire alrededor del modelo general

planteado, y en su si defecto si no son cubiertas en su mayorıa las hipotesis predecidas,

entonces deberıa servir como indicador de distintos elementos tales como el evitar el

codigo escogido para futuras soluciones al mismo problema, el desarrollo del mismo

modelo conceptual pero bajo otro paradigma de programacion, la reformulacion del

mismo modelo bajo otro enfoque de modelado, entre otras alternativas.

¿Como se puede mejorar este modelo? descrito con mayor profundidad en la sec-

cion de Trabajos Futuros (7.2), la mejora del modelo construido deberıa ir orientada

36

principalmente a mejorar los resultados contemplados en las metricas de evaluacion, y

ampliar su capacidad de aceptar nuevas instancias del problema de asignacion de ho-

rarios, ası mismo tal proceso de transformacion deberıa ser lo menos engorroso posible.

4.2.2. Formulacion del modelo conceptual

El modelo conceptual se divide en tres secciones:

Entrada: es la instancia original del problema a resolver. Esta compuesta de :

◦ Modelo original: es el conjunto de variables, relaciones y restriciones existentes

en el modelo original. Pueden estar formuladas solo de manera conceptual o ya

estar parametrizadas adecuadamente en terminos logicos y matematicos.

◦ Datos de entrada: es la instancia del mundo real que necesita ser resuelta. Por

ejemplo, pueden ser el conjunto de estudiantes que necesitan ser distribuidos entre

las distintas asignaturas, o el conjunto de operarios a distribuir entre las distintas

maquinas de una planta.

37

Modelo general: incluye el esquema general al cual debe ser mapeado el modelo

original, ası como los procesos encargados de optimizar el modelo. Mas detalladamente:

◦ Mapeo: es el proceso de conversion del modelo original al modelo general.

Transforma los elementos del modelo original a elementos que encuadren den-

tro de la logica de Clases Individuo-Clases Actividad-Relaciones-Restricciones.

38

Es realizado de manera manual por aquel que desee hacer uso de los mecanis-

mos de optimizacion del sistema. Este proceso de transformacion tambien debe

aplicarse sobre el conjunto de datos, generando entonces mapeo(dataOriginal) =

dataTransformada.

◦ Clases Individuo: en la semantica del problema de asignacion de horarios son

aquellos elementos del sistema avocados a realizar alguna actividad.

Figura 7: Clase Individuo.

Para los distintos tipos de clase individuo se tienen los mismos tipos de campo, a

continuacion:

◦ Id: identificador unico para el individuo.

◦ Lista de atributos: tupla de valores, en donde cada valor es de un tipo primiti-

vo o tupla. Su estructura varıa dependiendo del modelo origen. Este atributo

compuesto sirve para modelar los atributos de los Individuos del modelo ori-

ginal que no tienen representacion directa en el resto de los atributos de la

clase Individuo.

◦ Clases Actividad: en la semantica del problema de asignacion de horarios son

aquellos elementos del sistema disponibles para ser ejecutados por los individuos.

Para los distintos tipos de clase actividad se tienen los mismos tipos de campo, a

continuacion:

◦ Id: identificador unico para la actividad.

◦ Lista de atributos: tupla de valores, en donde cada valor es de un tipo primitivo

o tupla. Su estructura varıa dependiendo del modelo origen. Este atributo

39

Figura 8: Clase Actividad.

compuesto sirve para modelar los atributos de las actividades del modelo

original que no tienen representacion directa en el resto de los atributos de la

clase Actividad.

Posterior al concepto de Clase Actividad, se tiene el concepto de seccionamiento. Para

la definicion del mismo, y con el fin de generalizar el concepto de Actividad aplicado

a las principales instancias existentes de problema de asignacion de horarios, se deben

en tener en cuenta los siguientes factores:

◦ Una actividad puede tener una cantidad o estimada o determinada de o aspirantes

o participantes.

◦ Diferencias contextuales entre participantes y aspirantes : se habla de participantes

cuando ya esta establecida la relacion de ejecucion de un individuo con respecto

a una actividad. Se habla de aspirante cuando tal relacion es deseable (ya sea por

condiciones del sistema o por voluntad del individuo) pero aun no se ha establecido.

◦ En la generalizacion del problema de asignacion de horarios, se tiene que el con-

junto de actividades son ejecutadas en un determinado plazo. Tal plazo es repetido

por lo menos una vez, es decir, su ejecucion es cıclica.

◦ La ejecucion de cada actividad en el marco de un plazo cıclico se ve condicionada,

directa o indirectamente, por tres elementos:

◦ Tiempo: la ejecucion total de una actividad, en algunos casos (depende del

problema original), debe distribuirse en segmentos a traves del tiempo. A cada

uno de estos segmentos se le conocera como sub-actividad.

40

◦ Ubicacion: una actividad es ejecutada en alguna instancia del espacio. Tal

ubicacion poseera diversos atributos relacionados, pero a efectos del analisis

presente relacionado al seccionamiento, se considerara unicamente aquel atri-

buto relacionado a la maxima carga de individuos que tal ubicacion puede

admitir.

◦ Ejecutores: cantidad estimada o determinada de participantes o aspirantes.

Comprendiendo entonces la limitante asociada a la cantidad de individuo que puede

albergar una ubicacion fısica para la prosecucion de una actividad, se tiene que:

Se entiende por seccionamiento [71] el proceso por el cual una actividad es replicada

de tal manera que cada replica se toma como una actividad independiente con respecto

a las otras, con el fin de que su ejecucion sea manejable con respecto a la correlacion

carga maxima de individuos por ubicacion y cantidad total estimada o

determinada de participantes o aspirantes

Establecido el concepto de seccionamiento, entra en juego el de eventos. Un evento

no es mas que la asignacion de una sub-actividad a un par (instancia temporal,

instancia posicional). En otras palabras, un evento es la representacion indivisible (a

efectos del presente modelo) de la ejecucion de una actividad en terminos de sub-

actividades, ubicando cada una en una determinada instancia del espacio y del tiempo

(cada una de estas caracterısticas dependeran del contexto del trabajo, pero se toman

como referencias principales no excluibles por ser parte de los principales sistemas de

medicion existentes).

◦ Relaciones: son las representaciones necesarias para indicar que la Clase In-

dividuo X agrupa los individuos del modelo original que se plantean realizar las

actividades del modelo original pertenecientes ahora a la Clase Individuo Y. Las

siguientes son las relaciones planteadas en el modelo a construir:

◦ Individuo-realiza-Actividad:

41

Figura 9: Relacion Individuo-Realiza-Actividad.

◦ Incompatiblidad: se habla de ausencia de compatibilidad cuando, prestos dos

o mas elementos a ser comparados entre si, existe disonancia entre los valores

esperados para ser evaluados dentro de un conjunto de funciones matematicas y

condiciones logicas y los valores reales de tales elementos aplicados a tales funciones

y condiciones. Este esquema general es donde van encuadradas las tradicionales

restricciones “fuertes” y opcionales del timetabling problem.

◦ Propagadores: [29] es el conjunto de algoritmos de optimizacion de modelos

que trabaja sobre el modelo general (que contiene, posterior al proceso de mapeo,

una representacion manejable del modelo original), produciendo una version me-

jorada del mismo. En terminos formales, puede describirse de la siguiente manera:

propagadores(modeloGeneral, dataTransformada) = modeloOptimizado.

Salida: es consecuencia de la actividad de los propagadores, el modeloOptimizado.

4.2.3. Tipo de modelo a usar

Es un modelo hıbrido, dado que su estructura engrana conceptos y mecanismos de dis-

tintos tipos de modelos homogeneos, los cuales estan listados a continuacion:

Modelo matematico [40]: dado que la mayorıa de sus componentes son expresa-

dos en base a conceptos matematicos. Principalmente las restricciones asociadas a las

relaciones entre las clases existentes en el sistema.

Modelo logico [85]: debido a que tanto las relaciones como las restricciones son

expresadas, en ultima instancia, como el cumplimiento o no (verdadero o falso) de

determinadas condiciones construidas con postulados matematicos.

42

Modelo empırico: como consecuencia de incluir en uno de los procesos del modelo el

uso de datos reales.

Modelo estocastico: por el uso de componentes aleatorios y heurısticos a la hora de

hallar una version optimizada del modelo general basado en los datos de la instancia

del problema a resolver.

Modelo conceptual/cualitativo: porque en su concepcion inicial, a fines de una me-

jor comprension, es presentado como un engranaje de conceptos que permitan realizar

el proceso de mapeo mas facilmente.

Modelo descriptivo: dado que el enfoque asumido para la construccion del modelo

general es comprender la esencia del problema de asignacion de horarios desde una

perspectiva tanto global como intrınseca, haciendo necesario la descripcion detallada

de los procesos involucrados no solo en terminos formales sino tambien en lenguaje

natural, y definiendo la estructura final del mismo usando un marco recursos-procesos-

resultados.

Modelo de optimizacion: debido a que una de las principales caracterısticas del

timetabling problem es que las soluciones propuestas van orientadas desde un principio

a optimizar las asignaciones de individuos a actividades a realizar.

Modelo universal (vs Modelo de dominio especıfico): porque se busca englo-

bar el problema de asignacion de horarios, colocando como cota mınima abarcar sin

inconvenientes las versiones mas representativas del problema, para luego en trabajos

futuros basados en el actual, corregir las deficiencias del modelo construido y anadir

nuevas caracterısticas que permitan cubrir versiones mas sofisticadas del timetabling

problem que no sean cubiertas con el esquema construido en el presente trabajo.

4.2.4. Seleccion del codigo a aplicar

Esto es descrito con mas detalle en la seccion de Plataforma Computacional (6.1.1),

especıficamente en el segmento dedicado a la especificacion de los recursos de software a usar

para ejecutar las simulaciones.

43

4.2.5. Parametrizacion del modelo

Actividades:

A = {Ai/Ai es una actividad} , 1 ≤ i ≤ nA, nA = |A|

Ai =< id,< attr1, attr2, ..., attrm >>,m ≥ 0

Donde attri es un valor primitivo o una tupla, que contiene a su vez valores primitivos

o una tupla, y ası sucesivamente...

Sea F = {fi/fi es la cantidad de individuos asignados a realizar la actividad Ai}

Sea P = {p1, p2, ..., pn}

Donde pi es la cantidad promedio estimada de ejecutores que tendrıa cada sub-actividad

de Ai.

|A| = |F | = |P |

Aplicando criterio de seccionamiento (replicacion de actividad):

R = {Ri/Ri es el conjunto de replicas de la actividad Ai ∧ |Ri| = roof(fi/pi)}

Donde roof(...) arroja el valor redondeado al tope del parametro.

Se tiene entonces:

A′ =n⋃

i=1

(Ri ∈ R) = {Aj/Aj es un seccionamiento de una de las actividades originales}

Aj =< id, id actividad original, < attr1, attr2, ..., attrm >>

Lapso:

L = {Lk/Lk es una instancia temporal } , 1 ≤ k ≤ nL, nL = |L|

Lk =< id,< attr1, attr2, ..., attrp >>, p ≥ 0

Ubicacion:

U = {Ul/Ul es una instancia locacional } , 1 ≤ l ≤ nU , nU = |U |

Ul =< id,< attr1, attr2, ..., attrq >>, q ≥ 0

Eventos:

44

E = {Ed/Ed es un evento } , 1 ≤ d ≤ nE, nE = |E|

Ed =< id, id actividad, id lapso, id ubicacion,< attr1, attr2, ..., attrr >>, r ≥ 0

Donde compatibles(AEd[id actividad] ∈ A′, LEd[id lapso] ∈ L,UEd[id ubicacion] ∈ U

). Esta res-

triccion de compatibilidad sera etiquetada como RT0.

Individuos:

I = {Is/Is es una individuo } , 1 ≤ s ≤ nI , nI = |I|

Us =< id,< attr1, attr2, ..., attrw >>,w ≥ 0

Restricciones:

◦ Minimizacion de incompatibilidades entre eventos (RT1):

Dado un valor min1 ∈ R:

RT2 ≡ (

nE∑i=1

incompatibilidad(AEi[id actividad] ∈ A′,

LEi[id lapso] ∈ L,UEi[id ubicacion] ∈ U)) ≤ min1

◦ Minimizacion de incompatibilidades en asignaciones Individuo-Actividad

(RT2):

Sea G = {(Iy, Ac)/Iy ∈ I ∧ Ac ∈ A′}

G es el conjunto de asignaciones de individuos a actividades que se desean solu-

cionar. Tomando como elementos de calculo los pertenecientes a G, minimizar lo

siguiente:

Dado (Ix, Ai), (Ix, Aj) ∈ G. Ocurre que:

RT2 ≡ (Ai[id] 6= Aj[id] ∧ Ai[id actividad] = Aj[id actividad])∨

(Ai[id] 6= Aj[id] ∧ Ai[id actividad] 6= Aj[id actividad]∧

(∃x, y ∈ E[x[id actividad] = Ai[id actividad]∧

y[id actividad] = Aj[id actividad]∧

(solapamiento(Lx[id lapso] ∈ L,Ly[id lapso] ∈ L)∨

solapamiento(Ux[id ubicacion] ∈ U,Uy[id ubicacion] ∈ U))]))

45

4.2.6. Validacion del modelo

Verificacion del modelo:

¿El modelo esta programado correctamente?, ¿Los algoritmos han sido im-

plementados apropiadamente?, ¿El modelo no contiene errores de ningun

tipo? [86]

El diseno del modelo, realizado con cierto subconjunto de tecnologıas y descrito con mas

profundidad en la seccion de Configuracion de los experimentos (6.1.2), se baso en

la construccion de un conjunto de condiciones en logica de primer orden, que incluye

logica de predicados y postulados matematicos basicos, que pueden ser verificados para

comprobar su correctitud semantica y por supuesto sintactica.

Ası mismo la fiabilidad funcional de las herramientas de software a usar estan garantiza-

das dado que se tratan de creaciones validadas por los procesos estandar de evaluacion

de las investigaciones cientıficas.

La existencia o ausencia de errores en el modelo de restricciones creado para el presente

trabajo puede ser verificado, como ya se dijo, estudiando las condiciones desarrolladas

en la seccion de descripcion de los casos de prueba.

Validacion del modelo: La validacion de un modelo va orientada principalmente a

establecer la correctitud que existe entre lo que hace el modelo y el comportamiento

del fenomeno del mundo real que desea reproducir. Este modelo no busca esquematizar

un fenomeno del mundo real sino brindar un marco comun de parametros (entidades,

relaciones y restricciones) para el problema de asignacion de horarios. En consecuencia,

no son aplicables los mecanismos de validacion de modelos existentes para el actual.

4.2.7. Simulacion

El proceso de simulacion consta de las siguientes fases:

Definicion de casos de prueba.

Mapeo de casos de prueba, en conjunto con la data complementaria, al modelo general

construido en el presente trabajo.

46

Formulacion de hipotesis iniciales.

Escogencia de codigo, software y/o librerıas que desarrollen los algoritmos de propaga-

cion.

Implementacion de resultados de mapeo de los casos de prueba en los codigos seleccio-

nados.

Establecimiento de plataformas de hardware en donde se ejecutaran las simulaciones

(equipos computadores).

Ejecucion de los codigos en conjunto con los casos de prueba.

Analisis de los resultados obtenidos, constrastacion con hipotesis iniciales. Reformula-

cion de hipotesis o de otro punto previo en caso de considerarse necesario.

Presentacion de resultados finales.

4.2.8. Presentacion y analisis de resultados

Presentacion de resultados:

Cubierto en la seccion de Resultados obtenidos (6.2.2).

Se realiza con las herramientas de presentacion mas convenientes (tablas, graficos),

adaptando los valores generados a partir de las simulaciones contenidos por determina-

das variables. Se trabajan las distintas combinaciones que puedan generarse entre los

segmentos de datos generados para ası producir la informacion que sera cubierta en el

analisis final de resultados.

Analisis de resultados:

Desarrollado en la seccion de Conclusiones y Recomendaciones.

Aquı se expone el analisis final que contrasta las hipotesis iniciales planteadas y los

resultados obtenidos de las simulaciones. A partir de aquı tambien se generara las

recomendaciones para futuros trabajos que basen su tematica en la desarrollada en la

47

presente investigacion, en la continuacion de la misma, o en su defecto de uno intrınseca-

mente relacionado tanto al problema de generar un esquema general de las restricciones,

o en la optimizacion de las mismas mediante tecnicas de propagadores o alternativas.

48

5. Diseno de la solucion

Este capıtulo se compone de dos secciones. En la Descripcion de la Solucion (5.1) se

presentan una serie de puntos que describen el proceso a seguir ahora que se tiene establecido

por completo el marco de trabajo definido por el Protocolo de Modelado. Esta serie de pasos

incluyen el proceso de escogencia de los casos de prueba a desarrollar y la seleccion del

software para las simulaciones. En la seccion de Alcances y Limitaciones (5.2) se describen

los contras en relacion al proceso a seguir para la consecucion de los resultados que convaliden

los objetivos a lograr.

49

5.1. Descripcion de la solucion

El siguiente es un listado que resume la serie de pasos a seguir para lograr el objetivo final

propuesto, ası como las caracterısticas que rodean al proceso. Cada paso posee la respectiva

referencia a la seccion o secciones del presente trabajo en donde se describe con mayor detalle:

Se ha realizado una investigacion a fondo de los topicos mas activos con respecto al

problema de asignacion de horarios. Esto ha permitido identificar las principales ins-

tancias existentes del problema, y para cada una de ellas extraer un patron alrededor

de la trıada entidades-relaciones-restricciones, y construir un modelo conceptual debi-

damente parametrizado que permita dar soporte en su totalidad a los aspectos mas

esenciales de las instancias seleccionadas.

Se escogen de manera detallada los casos de prueba mas representativos a efectos de

poner a prueba la validez de los planteamientos del presente trabajo. Estos casos de

prueba consisten en modelos de entidades-relaciones-restricciones de instancias del ti-

metabling problem. A cada caso de prueba se le asocian datos de entrada, tanto reales

como artificiales (provenientes de un generador de casos previamente construido), los

cuales serviran para la ejecucion de los pasos posteriores.

Habiendo construido las hipotesis iniciales, estableciendo cotas de trabajo, definido las

plataformas en donde se ejecutara la simulacion, en conjunto con el codigo correspon-

diente, se realiza la conversion de los modelos originales en conjunto con la data al

esquema general planteado como solucion en este trabajo.

Desarrolladas las conversiones, se ejecutan las simulaciones, que consistiran en (para

cada modelo convertido al esquema general), usando los mecanismos proveıdos por el

codigo seleccionado, la aplicacion de los algoritmos de propagacion (optimizadores de

modelo) en base a los datos que tambien fueron transformados.

Posterior a las simulaciones, se recolectaran los datos producidos por las mismas, rea-

lizando los analisis correspondientes orientados principalmente a validar las hipotesis

planteadas. En caso de no existir una correlacion valida entre hipotesis y resultados, se

realiza una iteracion consistente en identificar algun elemento erroneo existente entre

50

los planteamientos iniciales del trabajo y las hipotesis previas a la simulacion. Realizada

la re-formulacion, se ejecutan nuevamente las simulaciones (volver al paso anterior).

Para cuando exista una correlacion valida entre hipotesis y resultados obtenidos, se

realizan las conclusiones asociadas a la investigacion en general, ası como las recomen-

daciones para trabajos futuros basados en el actual.

5.2. Alcance y limitaciones

El proceso de mapeo debe realizarse de manera manual. Esto involucra una carga

adicional para el usuario, dado que tiene que realizar un analisis propio que logre

encajar con el esquema general construido. Se evaluo la posibilidad de trabajar con

un proceso de mapeo automatico, pero queda fuera de los objetivos propuestos en el

trabajo actual.

El codigo encontrado para ser usado en el modulo de optimizacion del modelo (los

propagadores), si bien cumplen su trabajo, no esta asegurado que sean la mejor version

de si mismos, constituyendose esto en otra limitacion, y al mismo tiempo, en un punto

importante a ser tocado en un trabajo futuro, en donde se optimicen los algoritmos de

propagacion encargados de optimizar el modelo construido en el trabajo actual.

Queda fuera del trabajo la realizacion de una interfaz de usuario de alto nivel que

permita un manejo y/o entendimiento simple de los resultados, esto debido a que el

uso de estos componentes esta mas orientado a desarrolladores de una herramienta

mas global como lo serıa un solver para el problema de asignacion de horarios, con los

conocimientos necesarios en el campo.

Si bien la bibliografıa revisada esta lejos de ser pequena, el modelo construido esta lejos

de abarcar todas las variantes del problema de asignacion de horarios, pero si ha sido

disenado para que de solucion, con la respectiva conversion (mapeo), a las principales

versiones del mismo. Dando pie entonces a que, en trabajos futuros, una version mas

refinada del modelo sea construida.

51

6. Resultados experimentales

Este capıtulo se compone de dos secciones. En la Configuracion de los Experimentos

(6.1) se describe la plataforma computacional sobre la cual se ejecutaran las pruebas (esto

incluye caracterısticas de hardware y codigos escogidos que traten con el problema de la

optimizacion de modelos mediante algoritmos de propagacion de restricciones), los casos de

prueba en su version inicial, descritos verbalmente, pasando por sus definiciones logicas hasta

la representacion de los mismos en el software escogido para las simulaciones, ası como la

definicion de las metricas de evaluacion para analizar el nivel de validez de los resultados

en relacion a los objetivos planteados. Mientras que en el Analisis de los Resultados (6.2) se

describen las hipotesis iniciales en relacion a lo que se espera obtener de las simulaciones en

base a todo el entramado teorico y de analisis realizado previamente, para luego mostrar los

resultados obtenidos de las simulaciones.

52

6.1. Configuracion de los experimentos

6.1.1. Plataforma computacional

Las pruebas descritas en las siguientes secciones fueron realizadas en un equipo compu-

tador con las siguientes caracterısticas de hardware y software:

Sistema Operativo: Windows 10 de 32 Bits.

Disco Duro (HDD):

◦ Capacidad: 320 GB.

◦ Marca: Samsung.

◦ Modelo: HM321HI.

◦ RPM (Revoluciones Por Minuto): 5400 / 8M.

RAM: DDR3 2 GB Single Channel. Frecuencia DRAM (Dynamic RAM) de 399.0

MHz.

CPU: Pentium(R) Dual-Core E5700 @ 3.00 GHz 3.00 GHz.

En cuanto a la seleccion de codigo para ejecutar la optimizacion del modelo, se construyo

una lista de candidatos suficientemente amplia, para que el analisis de escogencia (en base a

una serie de criterios descritos a posteriori) se realizara con la mayor holgura posible. Estos

programas son los mencionados a continuacion:

Choco [2]: es una biblioteca para Java de codigo abierto usada para la programacion con

restricciones. Permite al usuario (programador) modelar su problema estableciendo el

conjunto de restricciones que deben ser cumplidas en cada una de las soluciones. Luego,

el problema es resuelto usando mecanismos que alternan entre algoritmos de filtrado

con mecanismos de busqueda.

EclipseCLP [4]: es un sistema de codigo abierto para el desarrollo y puesta en marcha

de aplicaciones basadas en programacion con restricciones. Contiene varias librerıas

para resolver esquemas pre-definidos de restricciones, un lenguaje de alto nivel para el

53

modelado, interfaces para solvers externos, entre otras herramientas. Su uso es mediante

la sintaxis de la programacion logica.

IBM ILOG Cplex Optimization Studio [11]: es un kit de herramientas de soporte a

la toma de decisiones mediante analıtica para acelerar el desarrollo y el despliegue

de modelos de optimizacion utilizando programacion matematica y de restricciones.

Combina un entorno de desarrollo integrado con un potente lenguaje de programacion

de optimizacion y solucionadores de optimizador ILOG CPLEX de alto rendimiento. Es

de uso pago mediante licencia, ofreciendo una version de prueba y con funcionalidades

limitadas.

Mozart Programming System [16]: combina investigaciones en desarrollo acerca del

diseno e implementacion de lenguajes de programacion, computacion distribuida, e

interfaces humano-computador. Esta implementado sobre el lenguaje multiparadigma

Oz y provee poder expresivo y avanzadas funcionalidades por igual. La ultima version

(la 2) provee un soporte limitado al manejo de restricciones, que espera ser mejorado

con el lanzamiento de nuevas versiones, siendo esta la principal meta.

Constraint 0.4.1 [3]: es una biblioteca disponible para Python, orientada a resolver

problemas de restricciones usando propagadores. Es un desarrollo aun en fase experi-

mental.

UNITIME [89]: descrito ya previamente en la seccion de Antecedentes Teoricos / Tra-

bajos Previos. Ademas del software principal, ofrece acceso a componentes .jar para ser

usados como librerıas externas de algun modulo personalizado relativo al timetabling

problem.

python-constraint [18]: otra biblioteca para Python que ofrece solucionadores para pro-

blemas de programacion con restricciones. Los solvers disponibles hasta el momento

son backtracking, recursivo y el de mınimo conflicto, en donde se minimizan la cantidad

de veces en la que cierta restriccion se incumple en las soluciones halladas o construidas.

Swi-Prolog [22]: es una implementacion estable y gratuita del lenguaje Prolog, con

orientacion a ser usada principalmente en entornos de investigacion y educativos.

54

Lingo [13]: herramienta disenada para la construccion y solucion de modelos lineales y

no lineales (convexos y no convexos), cuadraticas, restringidas cuadraticamente, entre

otros, de manera rapida, facil y eficiente.

Gecode [7]: es un conjunto de herramientas para el desarrollo de sistemas y aplicacio-

nes basadas en restricciones. Posee caracterısticas en su implementacion que lo hacen

abordar de manera muy eficiente muchos problemas tanto con enfoques deterministas

como con enfoques heurısticos. Permite su ejecucion en paralelo, maximizando el uso de

esta caracterıstica acorde a la arquitectura de hardware en la que este siendo ejecutada,

respaldada por sus primeros lugares en diversas competencias del ramo, y distribuida

de manera gratuita y en codigo abierto.

SavileRow [74]: implementada en Java, es una herramienta orientada a la optimizacion

de modelos de restricciones, mas que a la solucion de los mismos.

Ası mismo, existe un compendio adicional de herramientas, entre ellas LOOM ( [14]),

IBEX ( [10]), Cassowary ( [1]), Jacop ( [12]), Simple Theorem Prover (AKA SMT Solver)

( [20]), Opta Planner ( [17]), SCIP ( [19]), GUROBI ( [8]), Xpress ( [23]), SoPlex ( [21]),

FaCiLe ( [5]), HaifaCSP ( [9]), FPCS ( [6]), Mistral ( [15]). A diferencia de los descritos

mas detalladamente en la lista previa a la anterior, estos ultimos tienen en comun que son

softwares descontinuados, programas pagos sin acceso a versiones de prueba (limitadas en

tiempo de uso o cantidad de caracterısticas/funcionalidades), o sin posibilidad de acceder a

su codigo fuente para revisiones mas detalladas. En base a los mismos criterios junto a otros

adicionales se aplico un filtro entre los principales, para ası quedar con un solo candidato a

usar en las simulaciones:

Acceso a codigo fuente: disponible en todas las principales excepto en UNITIME

y en IBM ILOG Cplex.

Licencias libres Vs Licencias privativas: aplica el mismo resultado del punto

anterior.

Curva de aprendizaje: un aprendizaje mas rapido es ofrecido por herramientas

como SavileRow, dado que solo precisan conocimientos en logica de primer orden, ası

55

como definicion de predicados, mientras que en Lingo o ILOG Cplex o las bibliotecas

de Python hay que adaptarse a una sintaxis especifica definida por la herramienta, o

en Gecode, Swi-Prolog, Mozart o EclipseCLP se debe tener un background de conoci-

mientos en Programacion Logica.

De igual manera, la capacidad expresiva de la librerıa para Java llamada Choco es bastante

reducida, en contraste con la potencia de sus solvers internos ası como de sus algoritmos

propagadores.

En base a lo anterior, tenemos entonces que el codigo escogido para la ejecucion de las

simulaciones fue SavileRow 1.6.3, el cual a su vez usa dos herramientas complementarias,

Minion 1.8 y Essence 1.6.3. Se ha escogido SavileRow por su capacidad expresiva a la

hora de construir las restricciones, por sus algoritmos de propagacion debidamente validados

en sus publicaciones cientıficas y concursos y conferencias del problema de asignacion de

horarios, ası como la versatilidad inherente a la hora de generar los resultados en distintos

formatos para distintos solvers de restricciones. Se describen las herramientas escogidas a

continuacion:

SavileRow [74]: en su version 1.6.3, es un asistente de modelado para programacion

con restricciones. Provee un lenguaje de alto nivel que permite especificar las restriccio-

nes del problema que se quiera solventar, y luego traslada esa definicion a un archivo de

entrada para un determinado solver. Durante el proceso de traduccion, SavileRow apli-

ca procesos de reformulacion al modelo usando tecnicas de propagacion de restricciones,

en conjunto con los valores asignados a las variables del modelo de restricciones, para

ası optimizar el modelo. El lenguaje usado para modelar el problema que luego sera

pasado para ser optimizado por el nucleo de SavileRow (implementado en Java [79])

se conoce como Essence.

Minion [69]: en su version 1.8, es un solucionador de restricciones basado en el modela-

do de las mismas usando modelos matriciales. En otras palabras, restringe la expresion

de las restricciones a ser aplicadas sobre el conjunto de datos a resolver a una estruc-

tura de matriz, ofreciendo poca versatilidad a la hora de modelar, esto con el fin de

optimizar los procesos de solucion del problema. Esto contrasta con la mayorıa de los

56

restantes solucionadores de restricciones, que en la busqueda de proporcionar mas fle-

xibilidad a la hora del modelado, sacrifican el performance de las soluciones obtenidas,

tanto en calidad como en tiempo. El paper que presento a Minion fue escogido entre

los 10 primeros de un total de 500 entregas durante la ECAI [50].

Essence [46]: en su version 1.6.3, es un lenguaje formal (usado por SavileRow en

el presente problema) para la especificacion de problemas combinatorios, usando una

mezcla de lenguaje natural y matematicas discretas (logica de primer orden, de pre-

dicados, matrices, etc). Provee un sistema de tipos para definir una amplia gama de

estructuras de datos, con el nivel de profundidad que requiera el problema a solucionar.

Esta construido con la finalidad de ser accesible en uso a cualquiera que tenga cono-

cimientos basicos en matematicas discretas, y no necesariamente de programacion con

restricciones.

6.1.2. Casos de prueba

De la lista de casos del problema de asignacion de horarios estudiados hasta el punto

actual, han sido escogidos dos instancias para la realizacion de las simulaciones, dado que

ambas engloban las principales caracterısticas a ser estudiadas del timetabling problem. Las

dos pertenecientes al contexto universitario, debido a que este brinda la mayor cantidad de

condiciones que aumentan la complejidad del problema, estas son:

Post-Enrolment Course Timetabling (PE-CCT): evalua la distribucion de las asigna-

turas en un conjunto de aulas y perıodos (intervalos de horas repartidos en los dıas de

la semana) una vez que ya se tiene definido el conjunto de estudiantes que cursara cada

asignatura [67]. Mas formalmente, se manejan los siguientes elementos en esta instancia

del problema:

◦ Entidades:

◦ Eventos: cada evento requiere la asistencia de un conjunto de estudiantes ası

como de un salon con determinadas caracterısticas. Puede existir una pre-

cedencia obligatoria que obligue a que un evento ocurra primero en un dıa

57

antes que otro en especıfico. De igual manera, tambien se define una condi-

cion de disponibilidad que establezca cuales timeslots estan disponibles para

el evento.

◦ Salones: un salon posee un conjunto de caracterısticas, siendo la principal la

capacidad maxima de estudiantes que puede admitir.

◦ Timeslots: se tienen a disposicion cierto conjunto de dıas (dentro de una

semana), cada uno dividido en determinados teaching timeslots (“ranuras de

tiempo para ensenanza”) los cuales tienen que ser asignados a los eventos.

◦ Restricciones obligatorias:

◦ Restriccion H1 - Conflictos: eventos que posean estudiantes en comun no

pueden compartir el mismo timeslot.

◦ Restriccion H2 - Compatibilidad: un evento no puede ser alojado en un salon

que no posea las caracterısticas necesarias para el desarrollo del mismo, ası

como tampoco en un salon que no posea la capacidad mınima necesaria.

◦ Restriccion H3 - Ocupacion: No se permite el desarrollo de mas de un evento

por salon al mismo tiempo.

◦ Restriccion H4 - Disponibilidad: el timeslot asignado a un evento debe estar

disponible y no restringido para ese evento en especıfico.

◦ Restriccion H5 - Precedencias: respetar la precedencia entre eventos.

◦ Restricciones opcionales:

◦ Restriccion S1 - Eventos Tardıos: evitar la asignacion de eventos al final del

dıa.

◦ Restriccion S2 - Eventos Consecutivos: evitar la asignacion de eventos que

obliguen al estudiante a asistir a dos eventos consecutivos.

Curriculum-Based Course Timetabling (CB-CCT): plantea la asignacion de horarios

agregando como elemento central del analisis el concepto de currıculum. Este no es mas

que la agrupacion de un conjunto de asignaturas marcadas por varias caracterısticas en

comun relacionadas mayoritariamente por la proximidad semestral. Existen distintas

58

variantes de este problema, siendo la presentada aquı un compendio de los elementos

mas resaltantes de [39], [72] y [65].

◦ Entidades:

◦ Dıas, timeslots y perıodos: se especifica un conjunto de dıas a la semana,

y cada dıa es dividido en un conjunto de timeslots. Un perıodo viene a ser la

combinacion dıa-timeslot. La cantidad total de perıodos disponibles vendrıa a

ser la union generalizada de todos los productos cardinales entre cada dıa y

sus respectivos timeslots.

◦ Cursos y profesores: un curso es divido en clases para ser impartidas cada

una en un timeslot, siendo atendida por un conjunto de estudiantes, y dirigida

por un profesor. Hay timeslots para los cuales esta restringido el desarrollo de

determinadas asignaturas.

◦ Salones: poseen una capacidad de carga maxima, y en principio son asigna-

bles a cualquier clase (aplicando luego la restriccion de capacidad).

◦ Currıculo: es un grupo de cursos tal que cualquier par de ellos posee es-

tudiantes en comun. Es a partir de este elemento de donde se generan las

restricciones de este caso.

◦ Restricciones obligatorias:

◦ Restriccion H6 - Ocupacion de aula: no pueden haber par de clases compar-

tiendo la misma aula en el mismo perıodo.

◦ Restriccion H7 - Conflictos: clases que pertenezcan a asignaturas del mismo

currıculo deben tener entonces distintos perıodos asignados.

◦ Restriccion H8 - Disponibilidad: si el profesor encargado de una asignatura

no esta disponible para trabajar un determinado perıodo, entonces ninguna

clase de esa asignatura debe ser dictada en ese perıodo.

◦ Restriccion H9 - Multiplicidad: solo se permite mas de una clase de la misma

asignatura para aquellas especificadas en el conjunto de datos de entrada.

◦ Restriccion H10: existen perıodos en los que no se esta permitido dictar clases

de determinados cursos.

59

◦ Restriccion H11: existen aulas en las que no esta permitido dictar clases de

determinados cursos.

◦ Restricciones opcionales:

◦ Restriccion S4 - No exceder la capacidad maxima de cada aula.

◦ Restriccion S5 - Las clases de cada asignatura deben ser dictadas por encima

de una cantidad mınima de dıas, incluyente.

◦ Restriccion S6 - Asignar de manera consecutiva las clases de asignaturas per-

tenecientes al mismo currıculo.

◦ Restriccion S7 - Todas las clases de una misma asignatura deben ser realizadas

en la misma aula.

En base a lo anterior, se construiran los casos de prueba, cada uno de ellos basados en los

formatos que se acaban de describir respectivamente, excluyendo determinadas restricciones.

Ası mismo, se hara enfasis en describir los procesos relacionados al seccionamiento, creacion

de eventos, y optimizacion de modelos para posterior asignacion de individuos a actividades

y/o eventos. Todo esto descrito a continuacion:

Caso de prueba 1: basado en el PE-CTT. Se excluyen la restriccion S1 debido que

a la formulacion de la misma conlleva el uso de expresiones matematicas basadas en

sumatorias que no pueden ser desarrolladas de manera directa con el software escogido.

Las entidades y/o variables, relaciones y restricciones a tomar en cuenta son los siguien-

tes:

◦ Entidades:

◦ Eventos: E = {ei/ei es un evento} , |E| > 0

Cada evento posee un identificador unico y un conjunto de atributos de valores

booleanos

ai =< id,< attr1, attr2, ..., attrn >>, n > 0

La semantica de cada atributo attrj es la siguiente: si attrj == V erdadero,

significa que es necesario que el aula en donde se quiera llevar a cabo el evento

60

ei debe cumplir con ese requerimiento. Si es Falso, indica que no es necesario

que el aula cumpla con tal requisito.

Cada evento posee la misma cantidad de atributos booleanos, y variara entre

ellos el valor de verdad de cada uno.

◦ Aulas: A = {ai/ai es un aula} , |A| > 0

Cada aula posee un identificador unico y un conjunto de atributos de valores

booleanos

ai =< id,< attr1, attr2, ..., attrn >>, n > 0

La semantica de cada atributo attrj es la siguiente: attrj == V erdadero indica

que el aula ai cumple con poseer el atributo mencionado. En caso contrario,

si es Falso, quiere decir que no lo posee.

Cada aula posee la misma cantidad de atributos booleanos, y variara entre

ellas el valor de verdad de cada uno.

◦ Estudiantes: S = {si/si es un estudiante} , |S| > 0

Cada estudiante posee un identificador unico asociado, y la lista de eventos

en los que definitivamente va a participar.

si =< id,< e1, e2, ..., em >>,m ≤ |E|

Donde ej es un identificador de uno de los eventos.

◦ perıodos: P = {pi/pi es un periodo} , |P | > 0

Un perıodo es la combinacion de un timeslot con un dıa.

pi = (d, t)

d ∈ D = {di/di es un dia de la semana} , 1 ≤ |D| ≤ 7

t ∈ T = {ti/ti es un timeslot} , |T | > 0

ti = (hx, hy), donde hx y hy son horas y hx < hy.

Entonces, P ⊆ D × T .

◦ Restricciones:

◦ H1: Sea E el conjunto de eventos,

E ′ = {(x, y)/x, y ∈ E ∧ x 6= y ∧ x[periodo] = y[periodo]}, y sea Zv el conjunto

de estudiantes que asisten al evento v ∈ E, para cada (x, y) ∈ E ′ minimizar

61

la cantidad de veces en las que ocurre lo siguiente:

Zx ∩ Zy 6= ∅

◦ H2: disminuir la cantidad de situaciones en las que, asignada la realizacion

de un evento e en un aula a, ocurra que:

incompatibilidad(e[atributos], a[atributos])

◦ H3: sea E el conjunto de eventos, minimizar la cantidad de situaciones en

las que dado un (x, y) ∈ E × E, se cumpla que:

x 6= y ∧ x[aula] = y[aula]

◦ H4: hay perıodos que estan restringidos para la realizacion de ciertos eventos.

En otras palabras, no esta permitido que un evento ei sea realizado en deter-

minados perıodos. Tal restriccion se especifica mediante el siguiente conjunto:

C1 = {(e, p)/e ∈ E ∧ p ∈ P}

◦ H5: dados dos eventos x y y, en caso de que ambos deban transcurrir el

mismo dıa, se presenta a veces el caso en el que el evento y esta restringido a

ser desarrollado posterior al evento x.

C2 = {(x, y)/x, y ∈ E}

En base a la definicion anterior, entonces ocurre que toda asignacion (x, p1) y

(y, p2) donde p1, p2 ∈ P debe cumplir que:

(p1[d] 6= p2[d] ∨ (p1[d] = p2[d] ∧ p1[t] < p2[t]))

◦ S2: Minimizar la cantidad de situaciones en las que, dados dos eventos e1, e2

en los que el estudiante x es partıcipe, ocurre que son consecutivos(e1, e2).

Caso de prueba 2: basado en el CB-CTT. Se excluyen las restricciones S5 y S6

por los siguientes motivos:

◦ La restriccion S5 es removida debido que a la formulacion de la misma conlle-

va el uso de expresiones matematicas basadas en sumatorias que no pueden ser

implementadas de manera directa con el software escogido.

◦ Se elimina la restriccion S6 debido que a que la semantica de la misma involucra

descartar una cantidad considerable de combinaciones validas (que no incluirıan

62

esta restriccion) lo cual no dejarıa paso a que el planteamiento inicial de solucion

pueda ser implementado por el software usado en este trabajo, ni alguno similar

(teniendo en cuenta sus naturalezas deterministicas).

Las entidades y/o variables, relaciones y restricciones a tomar en cuenta son los siguien-

tes:

◦ Entidades:

◦ Cursos: C = {ci/ci es un curso } , |C| > 0.

Lo que comunmente se conoce tambien como Asignatura. Cada curso se define

mediante la siguiente estructura:

ci = < id, id profesor, cant clases,min dias,max dias, cant estudiantes,

multiples clases >

Donde:

� id : identificador unico del curso.

� id profesor : identificador del profesor que dicta tal curso.

� cant clases : la cantidad de clases a la semana que deben dictarse de este

curso.

� min dias : la cantidad mınima de dıas abarcados por las clases del curso.

� max dias : la cantidad maxima de dıas abarcados por las clases del curso.

� multiples clases : valor booleano que indica si un curso puede permitirse

tener mas de una clase el mismo dıa.

◦ Aulas: A = {ai/ai es un aula } , |A| > 0.

Cada una representa el espacio en donde deben llevarse a cabo las clases de

cada curso. La estructura de un aula es la siguiente:

ai =< id, capacidad, ubicacion >

Donde:

63

� id : identificador unico para el aula.

� capacidad: maxima cantidad de estudiantes permitida en el aula.

� ubicacion: valor entero que indica en ”donde”se encuentra el aula. Puede

usarse como referencia para la construccion de metricas en donde el tras-

lado de un estudiante de un aula a otra sea proporcional al valor absoluto

de la diferencia entre la ubicacion de cada aula.

◦ Currıculo: R = {Ri/Ri = {cj/cj ∈ C}}.

Un currıculo es una agrupacion de cursos. Se cumple que:

C =|R|⋃i=1

(Ri ∈ R)

Ası como tambien es posible mas no obligatorio que ∃x, y ∈ C[x ∩ y 6= ∅].

◦ perıodos: P = {pi/pi es un periodo} , |P | > 0

Un perıodo es la combinacion de un timeslot con un dıa.

pi = (d, t)

d ∈ D = {di/di es un dia de la semana} , 1 ≤ |D| ≤ 7

t ∈ T = {ti/ti es un timeslot} , |T | > 0

ti = (hx, hy), donde hx y hy son horas y hx < hy.

Entonces, P ⊆ D × T .

◦ Restricciones:

◦ H6: sean x, y dos clases distintas. Minimizar la cantidad de ocurrencias de:

x[periodo] 6= y[periodo] ∧ x[aula] 6= y[aula]

◦ H7: sean x, y dos clases distintas. Minimizar la cantidad de ocurrencias de:

x[periodo] = y[periodo] ∧ x[curriculo] ∩ y[curriculo] 6= ∅

◦ H8: sean x, y dos clases distintas. Minimizar la cantidad de ocurrencias de:

x[periodo] = y[periodo] ∧ x[profesor] = y[profesor]

◦ H9: sean x, y dos clases distintas. Minimizar la cantidad de ocurrencias de:

x[asignatura] = y[asignatura] ∧ x[periodo][dia] =

y[periodo][dia] ∧ Asignaturax[asignatura][multiples clases]

◦ H10: existen perıodos en donde no se permite que un curso dicte una deter-

minada clase (la misma restriccion del primer caso de prueba).

64

C1 = {(x, y)/x ∈ C ∧ y ∈ P ∧ no se permite que se dicten clases de x en el periodo y}

◦ H11: existen aulas en donde no se permite que se dicten clases para un de-

terminado curso.

C2 = {(x, y)/x ∈ C ∧ y ∈ A ∧ no se permite que se dicten clases de x en el aula y}

◦ S4: minimizar la cantidad de veces en las que dado un Sx como el conjunto

de estudiantes participantes del evento x, ocurra que:

|Sx| > Aulaevento[aula][capacidad]

◦ S7: Minimizar la cantidad de situaciones en las que, dados dos eventos dis-

tintos ex, ey, ocurra que ex[asignatura] = ey[asignatura] ∧ ex[ubicacion] 6=

ey[ubicacion].

Los datasets a usar para la ejecucion de los propagadores seleccionados son los siguientes:

Caso de prueba 1: los proporcionados en [77], [44], [78], [82]. Descritos a continuacion:

Los archivos de entrada asociados al PE-CTT proveen la siguiente informacion:

◦ Numero de eventos (clases).

◦ Numero de aulas.

◦ Numero de propiedades (requeridas por una actividad, poseıdas por un aula).

◦ Numero de estudiantes.

◦ Capacidad de las aulas.

◦ A que clases (eventos) asiste cada uno de los estudiantes, desde el estudiante e0

hasta el estudiante en−1.

65

Figura 10: Entrada del caso de prueba PE-CTT: matriz de asistencia de estudiantes a clases.

◦ Las propiedades que posee cada salon de clases.

Figura 11: Entrada del caso de prueba PE-CTT: matriz correlacion de aulas con propiedades.

◦ Las propiedades que cada evento requiere que posea el salon de clases en donde

vaya a desarrollarse.

66

Figura 12: Entrada del caso de prueba PE-CTT: matriz correlacion de eventos con propie-

dades requeridas.

◦ La restriccion de precedencia entre eventos.

Figura 13: Entrada del caso de prueba PE-CTT: matriz de restriccion de precedencia entre

eventos.

En la siguiente tabla se muestran los valores de las distintas variables, dependiendo del

caso de entrada:

67

Descripcion de siglas:

◦ CC: cantidad de propiedades.

◦ CA: cantidad de asignaturas.

◦ CC2: cantidad de clases (como el resultado de la sumatoria de las clases de cada

asignatura).

◦ CP: cantidad de perıodos.

◦ CE: cantidad de estudiantes.

◦ CA2: cantidad de aulas.

68

Entrada CC CA CC2 CP CE CA2

easy05 5 34 34 34 80 5

easy02 5 35 35 35 80 5

easy03 5 36 36 36 80 5

easy01 5 37 37 37 80 5

easy04 5 38 38 38 80 5

o12 5 64 64 64 200 10

o17 10 64 64 64 300 10

o15 10 68 68 68 300 10

med 4 9 70 70 70 400 10

medium01 5 112 112 112 200 10

o20 5 85 85 85 300 10

medium04 5 116 116 116 200 10

medium03 10 83 83 83 400 10

med 8 5 121 121 121 200 10

medium02 5 126 126 126 200 10

medium05 5 131 131 131 200 10

med 1 10 88 88 88 400 10

med 9 10 92 92 92 400 10

med 3 10 99 99 99 400 10

med 2 10 104 104 104 400 10

big 17 10 100 100 100 1200 25

big 7 20 117 117 117 1100 25

big 6 20 133 133 133 1000 25

big 11 20 146 146 146 1000 25

big 10 20 159 159 159 1000 25

Tabla 1: Valores de Caso de Prueba PE-CTT

69

Caso de prueba 2: los proporcionados en [83]. Descritos a continuacion:

Los archivos de entrada asociados al CB-CTT proveen la siguiente informacion:

◦ Nombre del caso.

◦ Cantidad de cursos (asignaturas).

◦ Cantidad de aulas.

◦ Cantidad de perıodos por dıa (entiendase por perıodo un intervalo de tiempo).

◦ Cantidad de currıculos.

◦ La cantidad mınima y maxima de clases que deben ser dictadas en un dia con

respecto a un currıculum.

◦ Las restricciones que involucran la no realizacion de clases de una asignatura en

determinadas aulas.

◦ Las restricciones que involucran la no realizacion de clases de una asignatura en

determinadas aulas.

Un ejemplo de archivo de entrada de los casos de prueba originales es el siguiente:

70

Figura 14: Ejemplo de formato original de entrada de caso de prueba CB-CTT.

La explicacion para cada uno de los elementos del archivo de entrada original (la des-

cripcion de los datos en su forma original para el caso de prueba CB-CTT):

◦ Name: Toy indica que el nombre de la instancia del caso de prueba es Toy.

71

◦ Courses: 4 indica que son cuatro las asignaturas contempladas en la instancia

actual.

◦ Rooms: 3 indica que son tres las aulas disponibles para llevar a cabo las clases

de cada asignatura.

◦ Days: 5 indica que son cinco los dıas sobre los cuales se distribuiran las clases de

cada una de las asignaturas.

◦ Periods per day: 4 indica que son cuatro la cantidad de horas academicas o

lapsos de tiempo disponibles por cada dıa.

◦ Currıcula: 2 indica que son dos las agrupaciones curriculares disponibles a ser

trabajadas. Recuerdese que un currıculo es un conjunto de asignaturas que tienen

en comun que sus clases no coinciden entre ellas en tiempo y mucho menos en

espacio.

◦ Min Max Daily Lectures: 2 3 indica que por cada dıa deben ser dictadas al

menos dos y como maximo tres clases entre todas las asignaturas disponibles.

◦ UnavailabilityConstraints: 8 indica que son ocho la cantidad de restricciones

temporales a tener en cuenta. Es decir, hay ocho combinaciones a considerar en-

tre asignaturas, dıas y horas academicas indicando que la asignatura no puede

permitirse clases a ser dictadas en un determinado dıa y hora.

◦ RoomConstraints: 3 indica que son tres la cantidad de restricciones espaciales

a tener en cuenta. Es decir, hay tres combinaciones a considerar entre asignaturas

y aulas indicando que la asignatura no puede permitirse clases a ser dictadas en

una determinada aula.

◦ COURSES: va seguido de un conjunto de lıneas (en este ejemplo cuatro) que des-

criben, bajo un determinado formato, cada una de las asignaturas de la instancia

del caso de prueba CB-CTT, por ejemplo:

SceCosC Ocra 3 3 30 1 indica que la asignatura SceCosC (primer valor)

sera dictada por el profesor Ocra (segundo valor), debiendo hacerlo en tres clases

(tercer valor) (por cada ciclo de cinco dıas, acorde a lo especificado mas arriba), en

un mınimo de tres dıas (cuarto valor) a un total de 30 estudiantes (quinto valor),

72

permitiendo la realizacion de dos clases de la misma asignatura en un mismo dıa.

Este ultimo valor puede ser un uno o un cero, indicado que se puede dictar dos

clases de la misma asignatura el mismo dıa o no se puede, respectivamente.

◦ ROOMS: va seguido de un conjunto de lıneas (en este ejemplo tres) que describen,

bajo un determinado formato, cada una de las aulas de la instancia del caso de

prueba CB-CTT, por ejemplo:

rA 32 1 indica que el aula rA (primer valor) posee una capacidad maxima de 32

estudiantes (segundo valor), estando ubicado en la locacion 1 (tercer valor).

◦ CURRICULA: va seguido de un conjunto de lıneas (en este ejemplo dos) que

describen, bajo un determinado formato, cada una de las unidades curriculares de

la instancia del caso de prueba CB-CTT, por ejemplo: Cur1 3 SceCosC Ar-

cTec TecCos indica que el currıculo Cur1 (primer valor) agrupa tres asignaturas

(segundo valor), indicando el nombre de las mismas a continuacion, en la misma

lınea, separadas por un espacio en blanco.

◦ UNAVAILABILITY CONSTRAINTS: va seguido de un conjunto de lıneas

(en este ejemplo ocho) que describen, bajo un determinado formato, cada una de

las restricciones temporales de asignaturas con respecto a los perıodos CB-CTT,

por ejemplo:

TecCos 2 0 indica que la asignatura TecCos (primer valor) no tiene permiti-

do que sus clases sean dictadas al primer periodo (tercer valor) del segundo dıa

(segundo valor).

◦ ROOM CONSTRAINTS: va seguido de un conjunto de lıneas (en este ejemplo

tres) que describen, bajo un determinado formato, cada una de las restricciones

espaciales de asignaturas con respecto a las aulas CB-CTT, por ejemplo:

SceCosC rA indica que la asignatura SceCosC (primer valor) no tiene permitido

que sus clases sean dictadas en el aula rA (segundo valor).

En la siguiente tabla se muestran los valores de las distintas variables, dependiendo del

caso de entrada:

Descripcion de siglas:

73

◦ CA: cantidad de asignaturas.

◦ CP: cantidad de perıodos.

◦ CC2: cantidad de eventos.

◦ CA2: cantidad de aulas.

◦ CC3: cantidad de curriculos.

74

Entrada CA CP CC2 CA2 CC3

toy 2 20 6 3 2

comp01 15 30 30 6 14

comp11 14 40 40 5 13

test1 21 58 58 12 26

test2 22 65 65 12 30

EA11 19 30 19 14 27

comp15 16 25 17 16 68

test4 20 40 40 10 55

comp02 17 25 21 16 70

EA06 17 50 34 15 19

test3 22 41 41 13 55

comp08 20 25 23 18 61

EA12 25 30 25 19 19

Udine4 23 47 47 16 55

DDS7 19 60 46 9 37

comp14 24 25 28 17 60

comp19 25 25 25 16 66

comp21 23 25 25 18 78

comp13 25 25 25 19 66

comp09 24 25 25 18 75

Udine3 27 27 27 17 62

comp04 28 25 25 18 57

EA01 56 25 25 27 37

EA08 53 50 50 14 23

EA04 60 55 55 29 29

Tabla 2: Valores de Caso de Prueba CB-CTT

75

Aplicando el proceso de mapeo a cada caso de prueba, se tiene que:

Caso de prueba 1:

◦ Los Eventos pasan a ser Actividades.

◦ Las Actividades no sufren proceso de seccionamiento, dado que el conjunto de

datos ofrecido por el modelo de entrada no proporciona la informacion necesaria

para tal proceso, lo cual conlleva a asumir que no es necesario implementarlo.

◦ Las Aulas pasan a ser Ubicaciones.

◦ Los perıodos pasan a ser Lapsos.

◦ Para el proceso de creacion de Eventos (entiendase Evento ahora en el marco

de conceptos del Modelo General) sera necesaria la implementacion del analisis

de compatibilidad entre la Actividad, la Ubicacion y el Lapso.

◦ H1 ' RT2. Esto es disminuir la cantidad global de individuos que compartan dos

eventos en el mismo lapso, para cada par de eventos ubicados en el mismo lapso

de tiempo.

◦ H2 ' RT0. Porque debe haber coincidencia booleana entre los atributos de Ac-

tividad y los de Ubicacion.

◦ H3 ' RT0. Porque no se puede permitir que dos eventos ubicados en el mismo

Lapso posean tambien la misma ubicacion.

◦ H4 ' RT0. Uno de los atributos del elemento Ubicacion debe ser compatible

con el id del elemento Actividad (la Actividad no debe encontrarse en la ”lista

negra”de Ubicacion).

◦ H5 ' RT1. Sean dos eventos x y y, si se establece una relacion de precedencia

de x con respecto a y y se cumple que x[periodo][dia] = y[periodo][dia], entonces

debe cumplirse que x[periodo][timeslot] < y[periodo][timeslot].

◦ S2 ' RT2. Minimizar la cantidad de situaciones en las que, dados dos eventos

e1, e2 en los que el Individuo x es partıcipe, ocurre que son consecutivos(e1, e2).

76

En base a las condiciones anteriores, las estructuras de datos quedan definidas de la

siguiente manera:

◦ Entidades:

◦ Lapso: l =< id,< dia, timeslot, peso,< actividad1, actividad2, ...,

actividadn >>>

Donde actividadi es una de las actividades vetadas para ser desarrolladas en

el lapso l, peso es un valor entero mayor o igual a cero. peso → ∞ conforme

l[timeslot] es mas tardıo con respecto al dıa en el que se encuentra ubicado.

o

l = (id, (d, t, p, Al))

Donde Al es el conjunto de actividades vetadas para ser desarrolladas por el

individuo l, d es el dia, t es el timeslot del modelo original y p es el peso ya

explicado.

L = {l/l es un Lapso}

◦ Ubicacion: u =< id,<< attr1, attr2, ..., attrn >>>

Donde attri es un valor booleano que indica si la ubicacion posee o no la

caracteristicai.

o

u = (id, (Au))

Donde Au es el conjunto de atributos booleanos que indica si la ubicacion

posee o no cada caracterıstica.

U = {u/u es una Ubicacion}

◦ Actividad:

a =< id,<< attr1, attr2, ..., attrn >,< lapso1, lapso2, ..., lapsom >>>

Donde attri es un valor booleano que indica si la actividad requiere o no de

una caracteristicai, y lapsoi es un lapso vetado para el desarrollo de A.

o

a = (id, (Aa, La))

Donde Aa es el conjunto de atributos booleanos que indica si la actividad a

77

requiere o no de que la ubicacion en donde vaya a ser ejecutada requiere de

una determinada caracterıstica, y La es el conjunto de lapsos vetados para la

realizacion de la actividad a.

A = {a/a es una Actividad}

◦ Evento: e =< id,Ax, Uy, lz >

Donde Ax es una Actividad, Uy es una Ubicacion y lz es un Lapso.

E = {e/e es un evento}

◦ Individuo:

i =< id,<< actividad1, actividad2, ..., actividadn >>>

Donde actividadi es una de las actividades en donde i sera partıcipe.

o

i = (id, (Ai))

Donde Ai es el conjunto de actividades a ser realizadas por el individuo i.

I = {i/i es un Individuo}

◦ Restricciones:

H1 = ∀x ∈ I[¬∃z, w ∈ E[z 6= w ∧ z[lapso] = w[lapso]∧

z[actividad] ∈ x[actividades] ∧ w[actividad] ∈ x[actividades]]]

H2 = ∀e ∈ E[¬incompatibilidad(e[actividad][propiedades],

e[ubicacion][propiedades])]

H3 = ∀x, y ∈ E[¬(x 6= y ∧ x[lapso] = y[lapso] ∧ x[ubicacion] = y[ubicacion])]

H4 = ∀e ∈ E[¬∃l ∈ L[l ∈ ae[actividad][La]]]

H5 = ¬∃x, y ∈ E[x 6= y ∧ forzar precedencia(x[actividad], y[actividad])∧

x[lapso] ≥ y[lapso]]

78

S2 = ¬∃x ∈ I[∃z, w ∈ E[z 6= w ∧ z[actividad], w[actividad] ∈ x[actividades]∧

consecutivos(z[lapso][timeslot], w[lapso][timeslot])]]

Y la optimizacion del modelo va orientado a la creacion de Eventos, dado que no

existe el proceso de seccionamiento, y ya los individuos tienen asignadas sus respectivas

actividades.

Caso de prueba 2:

◦ Las asignaturas pasan a ser Actividades.

◦ Las Actividades no sufren proceso de seccionamiento, dado que el conjunto de

datos ofrecido por el modelo de entrada no proporciona la informacion necesaria

para tal proceso, lo cual conlleva a asumir que no es necesario implementarlo.

◦ Cada Actividad (previamente asignatura) es preciso repetirla una cantidad de-

terminada de veces a la semana. Se tiene entonces el conjunto de sub-actividades,

con cardinalidad mayor o igual al conjunto de actividades.

◦ Las Aulas pasan a ser Ubicaciones.

◦ Los perıodos pasan a ser Lapsos.

◦ Los profesores pasan a ser tomados como Individuos.

◦ Para el proceso de creacion de Eventos (entendiendose Evento ahora en el marco

de conceptos del Modelo General) sera necesaria la implementacion del analisis

de compatibilidad entre la Actividad, la Ubicacion y el Lapso.

◦ H6 ' RT1. Dados dos eventos distintos ex, ey, minimizar la cantidad de veces en

las que ocurre que ex[lapso] = ey[lapso].

◦ H7 ' RT1. Dados dos eventos distintos ex, ey, minimizar la cantidad de veces en

las que ocurre que ex[lapso] = ey[lapso] ∧ (ex[profesor] =

ey[profesor] ∨ ex[curriculo] ∩ ey[curriculo] 6= ∅).

◦ H8 ' RT1. Dados dos eventos distintos ex, ey, minimizar la cantidad de veces en

las que ocurre que ex[lapso] = ey[lapso] ∧ ex[profesor] = ey[profesor].

79

◦ H9 ' RT1. Dados dos eventos distintos ex, ey, minimizar la cantidad de ve-

ces en las que ocurre que ex[asignatura] = ey[asignatura] ∧ ex[periodo][dia] =

ey[periodo][dia] ∧ ¬Asignaturaex[asignatura][multiples clases].

◦ H10 ' RT0. Dado un evento e, minimizar la cantidad de veces en las que

e[lapso] ∈ actividade[actividad][lapsos vetados].

◦ H11 ' RT0. Dado un evento e, minimizar la cantidad de veces en las que

e[ubicacion] ∈ actividade[actividad][ubicaciones vetadas].

◦ S4 ' RT0. Minimizar la cantidad de veces en las que dados Se como el conjun-

to de individuos (estudiantes) asistiendo al evento (clase) ex, ocurre que |Se| >

Ubicacionex[ubicacion].

◦ S7 ' RT1. Minimizar la cantidad de situaciones en las que, dados dos eventos

distintos ex, ey, ocurra que ex[asignatura] = ey[asignatura] ∧ ex[ubicacion] 6=

ey[ubicacion].

En base a las condiciones anteriores, las estructuras de datos quedan definidas de la

siguiente manera:

◦ Entidades:

◦ Lapso: l =< id,< dia, timeslot, < actividad1, actividad2, ..., actividadn >>>

Donde actividadi es una de las actividades vetadas para ser desarrolladas en

el lapso l.

o

l = (id, (d, t, Al))

Donde Al es el conjunto de actividades vetadas para ser desarrolladas por el

individuo l, d es el dia, t es el timeslot del modelo original.

L = {l/l es un Lapso}

◦ Ubicacion: u =< id,< capacidad,< actividad1, actividad2, ..., actividadn >

, edificio >>

Donde capacidad es un valor entero que indica la cantidad maxima de indi-

viduos que puede permitir la ubicacion durante la realizacion de un evento.

80

Mientras que cada actividadi es aquella para la cual no se permiten eventos

en la ubicacion u.

o

u = (id, (capacidad, actividades, edificio))

Donde capacidad es un valor entero que indica la cantidad maxima de indi-

viduos que puede permitir la ubicacion durante la realizacion de un evento.

Y actividades el conjunto de aquellas a las que no se les permite desarrollar

eventos en la ubicacion u.

U = {u/u es una Ubicacion}

◦ Actividad:

a =< id,<< lapso1, lapso2, ..., lapsom >, curriculo,multiples clases,

< ubicacion1, ubicacion2, ..., ubicacionp >, cant estudiantes, profesor,

cant minima dias, cant clases >>

Donde lapsoi es un lapso vetado para el desarrollo de A, y currıculo es un

conjunto de identificadores donde cada uno asocia la actividad a un conjunto

A′ ⊂ A. multiples clases es un valor booleano que indica si la actividad puede

ejecutarse en dos lapsos distintos tal que cada lapso compartan el mismo valor

para la propiedad dıa. Mientras que ubicacioni es aquella en la que no se

permite desarrollar eventos de la actividad a. cant estudiantes es el total de

individuos asignados a participar en cada evento asociado a la actividad a.

o

a = (id, (La, c,m, Ua, ce, p, cmd, cc))

Donde La es el conjunto de lapsos vetados para la realizacion de la activi-

dad a y c es un identificador que asocia la actividad a un conjunto A′ ⊂ A.

multiples clases es un valor booleano que indica si la actividad puede ejecu-

tarse en dos lapsos distintos tal que cada lapso compartan el mismo valor para

la propiedad dıa. Ua es el conjunto de ubicaciones en donde no se esta permi-

tido desarrollar eventos asociados a la actividad a. ce es el total de individuos

asignados a participar en cada evento asociado a la actividad a.

A = {a/a es una Actividad}

81

◦ Evento: e =< id,Ax, Uy, lz >

Donde Ax es una Actividad, Uy es una Ubicacion y lz es un Lapso.

E = {e/e es un evento}

◦ Individuo:

i =< id,<< actividad1, actividad2, ..., actividadn >>>

Donde actividadi es una de las actividades en donde i sera partıcipe.

o

i = (id, (Ai))

Donde Ai es el conjunto de actividades a ser realizadas por el individuo i.

I = {i/i es un Individuo}

En este caso de prueba, la entidad Individuo no sera necesario abordarla.

◦ Restricciones:

H6 = ¬∃x, y ∈ E[x 6= y ∧ x[lapso] = y[lapso] ∧ x[ubicacion] = y[ubicacion]]

H7 = ¬∃x, y ∈ E[x 6= y ∧ ∃z, w ∈ A[x[actividad] = z ∧ y[actividad] = w∧

z[curriculo] ∩ w[curriculo] 6= ∅ ∧ x[lapso] = y[lapso]]]

H8 = ¬∃x, y ∈ E[x 6= y ∧ ∃z, w ∈ A[x[actividad] = z ∧ y[actividad] = w∧

z[profesor] = w[profesor] ∧ x[lapso] = y[lapso]]]

H9 = ¬∃x, y ∈ E[x 6= y ∧ x[actividad] = y[actividad] ∧ x[lapso] 6= y[lapso]∧

x[lapso][dia] = x[lapso][dia]∧

∃z ∈ A[x[actividad] = z ∧ z[multiples clases]]]

H10 = ¬∃x ∈ E[∃y ∈ A[x[actividad] = y ∧ x[lapso] ∈ y[lapsos]]]

H11 = ¬∃x ∈ E[∃y ∈ A[x[actividad] = y ∧ x[ubicacion] ∈ y[ubicaciones]]]

S4 = ¬∃x ∈ E[∃y ∈ A[x[actividad] = y ∧ ∃z ∈ U [x[ubicacion] = z∧

y[cant estudiantes] > z[capacidad]]]]

S7 = ∀x ∈ A[∀y, z ∈ E[y 6= z ∧ y[actividad] = z[actividad] = x∧

y[ubicacion] = z[ubicacion]]]

82

Es de notar que con respecto a la simulacion, la cual se realiza con propagadores deter-

ministas, establecer las condiciones tal como estan descritas, redundara en la busqueda de

configuraciones por parte del solver muy probablemente inexistentes, y esto es por la na-

turaleza NP del problema presentado. El enfoque usado entonces para validar las hipotesis

iniciales sera el trabajar con subconjuntos aleatorios de los casos de entrada originales.

A continuacion la formulacion de los datos y las restricciones con las tecnologıas escogidas.

SavileRow es software de codigo abierto, y se ejecuta desde la linea de comandos, inde-

pendientemente del sistema operativo en el que se encuentre. Esta vıa de ejecucion puede

ser configurada convenientemente con un conjunto de flags, que controlan desde el tiempo

maximo de ejecucion hasta el formato de archivo a generar en la salida del programa. La

ejecucion estandar de una instancia a resolver mediante savilerow es la siguiente:

s av i l e r ow path/ to / case . eprime path/ to / case . eparam

Donde:

savilerow es un archivo bash (.sh en Linux, .bat en Windows).

case.eprime es el archivo que contiene el modelado de las restricciones en lenguaje

Essence.

case.eparam es el archivo que contiene los datos del problema de restricciones a resolver.

La ejecucion del comando anterior genera por defecto un archivo .minion, que sirve como

input optimizado para el solver del mismo nombre. Con diferentes banderas se puede forzar

la salida en un formato distinto, pero se ha escogido este formato por defecto para el actual

proyecto, dado que es el solver mas estable, en comparacion a las otras propuestas.

Dicho esto, la estructura de un archivo .eparam para el PE-CTT y el CB-CTT, son las

siguientes:

PE-CTT (valores de ejemplo)

83

language ESSENCE’ 1 .0

l e t t i n g C a n t C a r a c t e r i s t i c a s be 2

l e t t i n g Cant Act iv idades be 2

l e t t i n g Cant Eventos be 3

l e t t i n g Cant Lapsos be 4

l e t t i n g Cant Indiv iduos be 5

l e t t i n g Cant Ubicac iones be 2

l e t t i n g Cant Col s Act iv idades be 1 + C a n t C a r a c t e r i s t i c a s

+ Cant Lapsos + Cant Act iv idades

l e t t i n g Cant Cols Lapsos be 2

l e t t i n g Cant Co l s Ind iv iduos be Cant Act iv idades + 1

l e t t i n g Cant Col s Ubicac iones be C a n t C a r a c t e r i s t i c a s + 2

l e t t i n g Act iv idades : matrix indexed by

[ i n t ( 1 . . Cant Act iv idades ) ,

i n t ( 1 . . Cant Co l s Act iv idades ) ]

o f i n t ( 0 . . ) be

[

[ 1 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 ] ,

[ 2 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 ]

]

l e t t i n g Lapsos : matrix indexed by [ i n t ( 1 . . Cant Lapsos ) ,

i n t ( 1 . . Cant Cols Lapsos ) ]

o f i n t ( 0 . . ) be

[

[ 1 , 1 ] ,

[ 2 , 2 ] ,

[ 3 , 3 ] ,

[ 4 , 4 ]

]

l e t t i n g Ubicac iones : matrix indexed by

84

[ i n t ( 1 . . Cant Ubicac iones ) ,

i n t ( 1 . . Cant Col s Ubicac iones ) ]

o f i n t ( 0 . . ) be

[

[ 1 , 1 , 1 , 5 ] ,

[ 2 , 1 , 0 , 4 ]

]

l e t t i n g INDEX INDIVIDUOS be domain i n t ( 1 . . Cant Indiv iduos )

l e t t i n g INDEX EVENTOS be domain i n t ( 1 . . Cant Eventos )

l e t t i n g INDEX CARACTERISTICAS be

domain i n t ( 2 . . C a n t C a r a c t e r i s t i c a s +1)

l e t t i n g INDEX LAPSOS VETADOS be domain

i n t ( C a n t C a r a c t e r i s t i c a s +2. .

Cant Lapsos+C a n t C a r a c t e r i s t i c a s +1)

l e t t i n g INDEX ACTIVIDADES A REALIZAR be domain

i n t ( 2 . . Cant Act iv idades +1)

l e t t i n g ID be 1

l e t t i n g ACTIVIDAD DE EVENTO be 2

l e t t i n g UBICACION DE EVENTO be 3

l e t t i n g LAPSO DE EVENTO be 4

l e t t i n g TIMESLOT DE LAPSO be 2

Donde:

◦ La sentencia letting es equivalente a una declaracion variable con valor inicial

asignado.

◦ Se puede establecer los ındices de las matrices a conveniencia, aquı se definen desde

1 hasta n, donde n es cualquiera de los valores declarados previamente mediante

letting.

85

◦ Cada una de las matrices construidas representan el conjunto de datos provenientes

del problema, y cada fila es una elemento del conjunto al que se refiera el nombre

de la matriz. De esta manera, una fila de la matriz Ubicaciones es una de las

ubicaciones, que a su vez es un aula en la formulacion original del problema, ya

transformado.

◦ Cada columna de la matriz, en relacion a cada una de las filas, tiene un significado

asociado a la definicion del modelo general de restricciones, y es determinado por

el ındice de la columna. A continuacion, la explicacion por cada matriz:

◦ Actividades :

� Indice 1: ID de la actividad.

� Indices [2..Cant Caracteristicas + 1]: valor 1 en caso de que la actividad

requiera que el aula en donde vaya a ser desarrollada posea esa carac-

terıstica, valor 0 en caso contrario.

� Indices [Cant Caracteristicas+2..Cant Lapsos+Cant Caracteristicas+

1]: valor 1 en caso de que no se permita que un evento (clase) de esa ac-

tividad (asignatura) sea realizado durante ese lapso (perıodo). Valor 0 en

caso contrario.

◦ Lapsos :

� Indice 1: ID del lapso.

� Indice 2: ID del timeslot (atributo personalizado proveniente de la defini-

cion original del problema).

◦ Ubicaciones :

� Indice 1: ID de la ubicacion.

� Indices [2..Cant Caracteristicas+1]: valor 1 en caso de que el aula posea

esa caracterıstica, valor 0 en caso contrario.

◦ INDEX INDIV IDUOS, INDEX EV ENTOS,

INDEX CARACTERISTICAS, INDEX LAPSOS V ETADOS

y INDEX ACTIV IDADES A REALIZAR son valores de rango, usados en la

definicion de las restricciones sobre un conjunto de datos (descrito mas adelante).

86

◦ ID, ACTIV IDAD DE EV ENTO, UBICACION DE EV ENTO,

LAPSO DE EV ENTO y TIMESLOT DE LAPSO son valor es enteros que

sirven para indexar de manera mas directa y comprensible columnas especificas

de una matriz (que posean un significado semantico ya explicado arriba).

CB-CTT (valores de ejemplo)

language ESSENCE’ 1 .0

l e t t i n g Cant Act iv idades be 2

l e t t i n g Cant Lapsos be 7

l e t t i n g Cant Eventos be 6

l e t t i n g Cant Ubicac iones be 3

l e t t i n g Cant Curr i cu los be 2

l e t t i n g Base Lapsos Vetados be Cant Curr i cu los + 3

l e t t i n g Base Ubicac iones Vetadas be Cant Curr i cu los + 3

+ Cant Lapsos

l e t t i n g Cant Col s Act iv idades be 6 + Cant Curr i cu los

+ Cant Ubicac iones + Cant Lapsos

l e t t i n g Cant Cols Lapsos be 3 + Cant Act iv idades

l e t t i n g Cant Col s Ubicac iones be 3 + Cant Act iv idades

l e t t i n g Act iv idades : matrix indexed by

[ i n t ( 1 . . Cant Act iv idades ) ,

i n t ( 1 . . Cant Col s Act iv idades ) ]

o f i n t ( 0 . . ) be

[

[ 3 , 1 , 1 , 1 , 40 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 4 , 3 ] ,

[ 4 , 0 , 1 , 1 , 18 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 4 , 4 , 3 ]

]

87

l e t t i n g Lapsos : matrix indexed by [ i n t ( 1 . . Cant Lapsos ) ,

i n t ( 1 . . Cant Cols Lapsos ) ]

o f i n t ( 0 . . ) be

[

[ 1 , 1 , 1 , 0 , 0 ] ,

[ 2 , 1 , 2 , 0 , 0 ] ,

[ 3 , 1 , 3 , 0 , 0 ] ,

[ 4 , 1 , 4 , 0 , 0 ] ,

[ 5 , 2 , 1 , 0 , 0 ] ,

[ 6 , 2 , 2 , 0 , 0 ] ,

[ 7 , 2 , 3 , 0 , 0 ]

]

l e t t i n g Ubicac iones : matrix indexed by

[ i n t ( 1 . . Cant Ubicac iones ) ,

i n t ( 1 . . Cant Col s Ubicac iones ) ]

o f i n t ( 0 . . ) be

[

[ 1 , 32 , 0 , 0 , 1 ] ,

[ 2 , 50 , 0 , 1 , 0 ] ,

[ 3 , 40 , 1 , 0 , 0 ]

]

l e t t i n g ID be 1

l e t t i n g INDEX CURRICULOS be domain i n t ( 2 . . Cant Curr i cu los +1)

l e t t i n g INDEX EVENTOS be domain i n t ( 1 . . Cant Eventos )

l e t t i n g INDEX ACTIVIDADES be domain i n t ( 1 . . Cant Act iv idades )

l e t t i n g ACTIVIDAD DE EVENTO be 2

88

l e t t i n g CAPACIDAD DE UBICACION be 2

l e t t i n g UBICACION DE EVENTO be 3

l e t t i n g LAPSO DE EVENTO be 4

l e t t i n g PROFESOR DE ACTIVIDAD be Cant Curr i cu los

+ Cant Lapsos + Cant Ubicac iones + 4

l e t t i n g DIA DE LAPSO be 2

l e t t i n g MULTIPLES CLASES be Cant Curr i cu los + 1

l e t t i n g CANT ESTUDIANTES DE ACTIVIDAD be 3 + Cant Curr i cu los

l e t t i n g EDIFICIO DE UBICACION be 3 + Cant Act iv idades

Se describe la semantica de cada las columnas o rangos de columnas de cada una de

las matrices:

◦ Actividades :

◦ Indice 1: ID de la actividad.

◦ Indices [2..Cant Curriculos+1]: valor 1 en caso de que la actividad pertenezca

al currıculo indexado, valor 0 en caso contrario.

◦ Indice Cant Curriculos + 2: valor 1 si la actividad puede permitirse dos o

mas eventos para los cuales el lapso asignado posea el mismo valor para el

atributo dia (atributo personalizado proveniente de la formulacion original del

problema).

◦ Indice Cant Curriculos + 3: cantidad de aspirantes a asistir a los distintos

eventos de la actividad.

◦ Indices [Cant Curriculos + 4..Cant Curriculos + Cant Lapsos + 4]: valor 1

en caso de que la actividad no pueda desarrollar algunos de sus eventos en el

lapso indexado. Valor 0 en caso contrario.

◦ Indices [Cant Curriculos+Cant Lapsos+5..Cant Curriculos+Cant Lapsos+

Cant Ubicaciones+5]: valor 1 en caso de que la actividad no pueda desarrollar

algunos de sus eventos en la ubicacion indexada. Valor 0 en caso contrario.

◦ Indice Cant Curriculos+Cant Lapsos+Cant Ubicaciones+ 6: ID del pro-

89

fesor (atributo personalizado proveniente de la formulacion original del pro-

blema).

◦ Indice Cant Curriculos + Cant Lapsos + Cant Ubicaciones + 7: cantidad

mınima de dıas a cubrir en cuanto a realizacion de eventos asociados a la

actividad.

◦ Indice Cant Curriculos+Cant Lapsos+Cant Ubicaciones+ 8: cantidad de

eventos a desarrollar asociados a la actividad.

◦ Lapsos :

◦ Indice 1: ID del lapso.

◦ Indice 2: ID del dıa (atributo personalizado proveniente de la definicion ori-

ginal del problema).

◦ Indice 3: ID del timeslot (atributo personalizado proveniente de la definicion

original del problema).

◦ Indices [4..Cant Lapsos+4]: valor 1 en caso de que la actividad indexada este

vetada para realizar algunos de sus eventos en el lapso actual, valor 0 en caso

contrario.

◦ Ubicaciones :

◦ Indice 1: ID de la ubicacion.

◦ Indice 2: Capacidad de la ubicacion.

◦ Indices [3..Cant Actividades+3]: valor 1 en caso de que la actividad indexada

este vetada para realizar algunos de sus eventos en la ubicacion actual, valor

0 en caso contrario.

INDEX CURRICULOS, INDEX EV ENTOS y INDEX ACTIV IDADES son

valores de rango, usados en la definicion de las restricciones sobre un conjunto de datos

(descrito mas adelante).

ID, ACTIV IDAD DE EV ENTO, UBICACION DE EV ENTO,

CAPACIDAD DE UBiCACION , LAPSO DE UBICACION ,

PROFESOR DE ACTIV IDAD, EDIFICIO DE UBICACION ,

90

CANT ESTUDIANTES DE ACTIV IDAD, MULTIPLES CLASES

y DIA DE LAPSO, son valores enteros que sirven para indexar de manera mas directa

y comprensible columnas especificas de una matriz (que posean un significado semantico

ya explicado arriba).

A continuacion, se muestra como quedarıa modelado en Essence la instancia mostrada

en la figura 14:

language ESSENCE’ 1 .0

l e t t i n g Cant Act iv idades be 2

l e t t i n g Cant Lapsos be 20

l e t t i n g Cant Eventos be 6

l e t t i n g Cant Ubicac iones be 3

l e t t i n g Cant Curr i cu los be 2

l e t t i n g Base Lapsos Vetados be Cant Curr i cu los + 3

l e t t i n g Base Ubicac iones Vetadas be Cant Curr i cu los + 3 +

Cant Lapsos

l e t t i n g Cant Col s Act iv idades be 6 + Cant Curr i cu los +

Cant Ubicac iones + Cant Lapsos

l e t t i n g Cant Cols Lapsos be 3 + Cant Act iv idades

l e t t i n g Cant Col s Ubicac iones be 3 + Cant Act iv idades

l e t t i n g Act iv idades : matrix indexed by

[ i n t ( 1 . . Cant Act iv idades ) ,

i n t ( 1 . . Cant Co l s Act iv idades ) ]

o f i n t ( 0 . . ) be

$1 columna para id de ac t i v idad

$2 columnas para marcadores boo leanos de c u r r i c u l o s

$1 columna para marcador booleano de doble a c t i v i dad

$1 columna para cant idad de e s t u d i a n t e s

$20 columnas para marcadores boo leanos de l a p s o s vetados

$3 columnas para marcadores boo leanos de ub i ca c i one s vetadas

91

$1 columna para id de p r o f e s o r

$1 columna para cant idad minima de d ia s

$1 columna para cant idad de c l a s e s

[ [ 3 , 1 , 1 , 1 , 40 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 ,

0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 4 , 3 ] ,

[ 4 , 0 , 1 , 1 , 18 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,

0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 4 , 4 , 3 ] ]

l e t t i n g Lapsos : matrix indexed by

[ i n t ( 1 . . Cant Lapsos ) ,

i n t ( 1 . . Cant Cols Lapsos ) ]

o f i n t ( 0 . . ) be

$1 columna para id de lapso

$1 columna para id de dia

$1 columna para id de t i m e s l o t

$1 columnas para marcadores boo leanos de a c t i v i d a d e s vetadas

[ [ 1 , 1 , 1 , 0 , 0 ] , [ 2 , 1 , 2 , 0 , 0 ] , [ 3 , 1 , 3 , 0 , 0 ] ,

[ 4 , 1 , 4 , 0 , 0 ] , [ 5 , 2 , 1 , 0 , 0 ] , [ 6 , 2 , 2 , 0 , 0 ] ,

[ 7 , 2 , 3 , 0 , 0 ] , [ 8 , 2 , 4 , 0 , 0 ] , [ 9 , 3 , 1 , 1 , 0 ] ,

[ 1 0 , 3 , 2 , 1 , 0 ] , [ 1 1 , 3 , 3 , 0 , 0 ] , [ 1 2 , 3 , 4 , 0 , 0 ] ,

[ 1 3 , 4 , 1 , 0 , 0 ] , [ 1 4 , 4 , 2 , 0 , 0 ] , [ 1 5 , 4 , 3 , 1 , 0 ] ,

[ 1 6 , 4 , 4 , 1 , 0 ] , [ 1 7 , 5 , 1 , 0 , 0 ] , [ 1 8 , 5 , 2 , 0 , 0 ] ,

[ 1 9 , 5 , 3 , 0 , 0 ] , [ 2 0 , 5 , 4 , 0 , 0 ]

]

l e t t i n g Ubicac iones : matrix indexed by

[ i n t ( 1 . . Cant Ubicac iones ) ,

92

i n t ( 1 . . Cant Col s Ubicac iones ) ]

o f i n t ( 0 . . ) be

$1 columna para id de ub i cac ion

$1 columna para capacidad

$2 columnas para marcadores boo leanos de a c t i v i d a d e s vetadas

$1 columna para id de e d i f i c i o

[ [ 1 , 32 , 0 , 0 , 1 ] , [ 2 , 50 , 0 , 1 , 0 ] , [ 3 , 40 , 1 , 0 , 0 ] ]

l e t t i n g ID be 1

l e t t i n g INDEX CURRICULOS be domain i n t ( 2 . . Cant Curr i cu los +1)

l e t t i n g INDEX EVENTOS be domain i n t ( 1 . . Cant Eventos )

l e t t i n g INDEX ACTIVIDADES be domain i n t ( 1 . . Cant Act iv idades )

l e t t i n g ACTIVIDAD DE EVENTO be 2

l e t t i n g CAPACIDAD DE UBICACION be 2

l e t t i n g UBICACION DE EVENTO be 3

l e t t i n g LAPSO DE EVENTO be 4

l e t t i n g PROFESOR DE ACTIVIDAD be Cant Curr i cu los +

Cant Lapsos + Cant Ubicac iones + 4

l e t t i n g DIA DE LAPSO be 2

l e t t i n g MULTIPLES CLASES be Cant Curr i cu los + 1

l e t t i n g CANT ESTUDIANTES DE ACTIVIDAD be 3 + Cant Curr i cu los

l e t t i n g EDIFICIO DE UBICACION be 3 + Cant Act iv idades

l e t t i n g TOTAL POSIBLES VALORES EVENTO MATRIZ be 30

El archivo *.eprime contiene las definiciones de las restricciones a tener en cuenta para

crear el modelo optimizado. En conjunto con los datos contenidos en el archivo *.eparam son

los datos de entrada de los propagadores de SavileRow. Para el proceso de simulaciones se

tomo en cuenta la cantidad de restricciones a cubrir por cada caso (el Post-Enrollment y el

Curriculum-Based).

93

Sea n la cantidad de restricciones de uno de los dos casos, se calcula p = 2n−1, siendo p la

cantidad de archivos *.eprime a crear. La estructura de cada uno de los archivos es descrita

a continuacion:

Sea F = {fi/fi es un archivo ∗ .eprime}, 1 <= i <= |F | = p, se cumple que ∀fi[fi ∈

F ∧ nombre archivo(fi) = binario(i)]. Es decir, se crea tal cantidad de archivos, cada uno

nombrado con la representacion binaria de uno de los valores en el dominio [1, p], indicando

que la restriccion asociada al ”bit”x esta contemplada o no en dicho archivo *.eprime. El

archivo 111111.eprime contempla todas las restricciones en su modelado, mientras que el

archivo 110001.eprime solo contempla la primera, segunda y ultima restriccion.

Se tiene entonces, para los dos casos principales trabajados, que un archivo *.eprime que

contemple todas las restricciones tendrıan el siguiente formato:

1. PE-CTT:

language ESSENCE’ 1 .0

g iven C a n t C a r a c t e r i s t i c a s : i n t

g iven Cant Act iv idades : i n t

g iven Cant Eventos : i n t

g iven Cant Lapsos : i n t

g iven Cant Indiv iduos : i n t

g iven Cant Ubicac iones : i n t

g iven Cant Col s Act iv idades : i n t

g iven Cant Cols Lapsos : i n t

g iven Cant Co l s Ind iv iduos : i n t

g iven Cant Col s Ubicac iones : i n t

g iven Act iv idades : matrix indexed by

[ i n t ( 1 . . Cant Act iv idades ) ,

i n t ( 1 . . Cant Col s Act iv idades ) ] o f i n t ( 0 . . )

g iven Lapsos : matrix indexed by [ i n t ( 1 . . Cant Lapsos ) ,

i n t ( 1 . . Cant Cols Lapsos ) ] o f i n t ( 0 . . )

g iven Ind iv iduos : matrix indexed by [ i n t ( 1 . . Cant Indiv iduos ) ,

i n t ( 1 . . Cant Co l s Ind iv iduos ) ] o f i n t ( 0 . . )

94

given Ubicac iones : matrix indexed by

[ i n t ( 1 . . Cant Ubicac iones ) ,

i n t ( 1 . . Cant Col s Ubicac iones ) ] o f i n t ( 0 . . )

g iven INDEX INDIVIDUOS : i n t

g iven INDEX EVENTOS : i n t

g iven INDEX CARACTERISTICAS : i n t

g iven INDEX LAPSOS VETADOS : i n t

g iven INDEX ACTIVIDADES A REALIZAR : i n t

g iven ID : i n t

g iven ACTIVIDAD DE EVENTO : i n t

g iven UBICACION DE EVENTO : i n t

g iven LAPSO DE EVENTO : i n t

g iven TIMESLOT DE LAPSO : i n t

g iven TOTAL POSIBLES VALORES EVENTO MATRIZ : i n t

f i n d Eventos : matrix indexed by [ i n t ( 1 . . Cant Eventos ) , i n t ( 1 . . 4 ) ]

o f i n t ( 1 . . TOTAL POSIBLES VALORES EVENTO MATRIZ) such that

$H1

f o r A l l x : INDEX INDIVIDUOS .

f o r A l l y : INDEX EVENTOS.

f o r A l l z : INDEX EVENTOS.

( y != z )

−>

(

Eventos [ y , LAPSO DE EVENTO] != Eventos [ z , LAPSO DE EVENTO]

\/

(

Ind iv iduos [ x , 1 + Eventos [ y , ACTIVIDAD DE EVENTO ] ] !=

Ind iv iduos [ x , 1 + Eventos [ z , ACTIVIDAD DE EVENTO ] ]

95

)

\/

Ind iv iduos [ x , 1 + Eventos [ y , ACTIVIDAD DE EVENTO ] ] = 0

)

,

$H2

f o r A l l x : INDEX EVENTOS.

f o r A l l i : INDEX CARACTERISTICAS.

(

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] , i ] =

Ubicac iones [ Eventos [ x , UBICACION DE EVENTO] , i ]

)

\/

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] , i ] = 0

,

$H3

f o r A l l x : INDEX EVENTOS.

f o r A l l y : INDEX EVENTOS.

( x != y )

−>

(

Eventos [ x , UBICACION DE EVENTO] !=

Eventos [ y , UBICACION DE EVENTO]

\/

Eventos [ x , LAPSO DE EVENTO] != Eventos [ y , LAPSO DE EVENTO]

)

,

$H4

f o r A l l x : INDEX EVENTOS.

f o r A l l i : INDEX LAPSOS VETADOS.

96

Eventos [ x , LAPSO DE EVENTO] !=

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] , i ]

,

$H5

f o r A l l x : INDEX EVENTOS.

f o r A l l y : INDEX EVENTOS.

( x != y )

−>

(

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

Eventos [ y , ACTIVIDAD DE EVENTO] +

Cant Lapsos+C a n t C a r a c t e r i s t i c a s ] = 0

\/

(

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

Eventos [ y , ACTIVIDAD DE EVENTO] +

Cant Lapsos+C a n t C a r a c t e r i s t i c a s ] = 1

−>

Lapsos [ Eventos [ x , LAPSO DE EVENTO] , TIMESLOT DE LAPSO] >

Lapsos [ Eventos [ y , LAPSO DE EVENTO] , TIMESLOT DE LAPSO]

)

\/

(

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

Eventos [ y , ACTIVIDAD DE EVENTO] + Cant Lapsos+

C a n t C a r a c t e r i s t i c a s ] = −1

−>

Lapsos [ Eventos [ x , LAPSO DE EVENTO] , TIMESLOT DE LAPSO] <

Lapsos [ Eventos [ y , LAPSO DE EVENTO] , TIMESLOT DE LAPSO]

)

97

)

,

$S2

f o r A l l x : INDEX INDIVIDUOS .

f o r A l l z : INDEX EVENTOS.

f o r A l l w : INDEX EVENTOS.

(

z != w

/\

Eventos [ z , ACTIVIDAD DE EVENTO] !=

Eventos [w, ACTIVIDAD DE EVENTO]

/\

Ind iv iduos [ x , Eventos [ z , ACTIVIDAD DE EVENTO] + 1 ] = 1

/\

Ind iv iduos [ x , Eventos [w, ACTIVIDAD DE EVENTO] + 1 ] = 1

)

−>

(

Lapsos [ Eventos [ z , LAPSO DE EVENTO] , TIMESLOT DE LAPSO] −

Lapsos [ Eventos [w, LAPSO DE EVENTO] , TIMESLOT DE LAPSO] != 1

/\

Lapsos [ Eventos [w, LAPSO DE EVENTO] , TIMESLOT DE LAPSO] −

Lapsos [ Eventos [ z , LAPSO DE EVENTO] , TIMESLOT DE LAPSO] != 1

)

2. CB-CTT:

language ESSENCE’ 1 .0

g iven Cant Act iv idades : i n t

g iven Cant Lapsos : i n t

98

given Cant Eventos : i n t

g iven Cant Ubicac iones : i n t

g iven Cant Curr i cu los : i n t

g iven Base Lapsos Vetados : i n t

g iven Base Ubicac iones Vetadas : i n t

g iven Cant Col s Act iv idades : i n t

g iven Cant Cols Lapsos : i n t

g iven Cant Col s Ubicac iones : i n t

g iven Act iv idades : matrix indexed by [ i n t ( 1 . . Cant Act iv idades ) ,

i n t ( 1 . . Cant Col s Act iv idades ) ] o f i n t ( 0 . . )

g iven Lapsos : matrix indexed by [ i n t ( 1 . . Cant Lapsos ) ,

i n t ( 1 . . Cant Cols Lapsos ) ] o f i n t ( 0 . . )

g iven Ubicac iones : matrix indexed by [ i n t ( 1 . . Cant Ubicac iones ) ,

i n t ( 1 . . Cant Col s Ubicac iones ) ] o f i n t ( 0 . . )

g iven ID : i n t

g iven INDEX CURRICULOS : i n t

g iven INDEX EVENTOS : i n t

g iven INDEX ACTIVIDADES : i n t

g iven ACTIVIDAD DE EVENTO : i n t

g iven CAPACIDAD DE UBICACION : i n t

g iven UBICACION DE EVENTO : i n t

g iven LAPSO DE EVENTO : i n t

g iven PROFESOR DE ACTIVIDAD : i n t

g iven DIA DE LAPSO : i n t

g iven MULTIPLES CLASES : i n t

g iven CANT ESTUDIANTES DE ACTIVIDAD : i n t

g iven EDIFICIO DE UBICACION : i n t

g iven TOTAL POSIBLES VALORES EVENTO MATRIZ : i n t

f i n d Eventos : matrix indexed by [ i n t ( 1 . . Cant Eventos ) ,

99

i n t ( 1 . . 6 ) ]

o f i n t ( 1 . . TOTAL POSIBLES VALORES EVENTO MATRIZ)

such that

$H6

f o r A l l x : INDEX EVENTOS.

f o r A l l y : INDEX EVENTOS.

( x != y )

−>

! (

Eventos [ x , LAPSO DE EVENTO] = Eventos [ y , LAPSO DE EVENTO]

/\

Eventos [ x , UBICACION DE EVENTO] =

Eventos [ y , UBICACION DE EVENTO]

) ,

$H7

f o r A l l x : INDEX EVENTOS.

f o r A l l y : INDEX EVENTOS.

(

x != y

/\

! f o r A l l a : INDEX CURRICULOS.

(

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] , a ] !=

Act iv idades [ Eventos [ y , ACTIVIDAD DE EVENTO] , a ]

\/

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] , a ] = 0

)

)

−>

100

(

Eventos [ x , LAPSO DE EVENTO] != Eventos [ y , LAPSO DE EVENTO]

) ,

$H8

f o r A l l x : INDEX EVENTOS.

f o r A l l y : INDEX EVENTOS.

(

x != y

/\

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

PROFESOR DE ACTIVIDAD] =

Act iv idades [ Eventos [ y , ACTIVIDAD DE EVENTO] ,

PROFESOR DE ACTIVIDAD]

)

−>

(

Eventos [ x , LAPSO DE EVENTO] != Eventos [ y , LAPSO DE EVENTO]

) ,

$H9

f o r A l l x : INDEX EVENTOS.

f o r A l l y : INDEX EVENTOS.

(

x != y

/\

Eventos [ x , ACTIVIDAD DE EVENTO] =

Eventos [ y , ACTIVIDAD DE EVENTO]

/\

Eventos [ x , LAPSO DE EVENTO] != Eventos [ y , LAPSO DE EVENTO]

/\

Lapsos [ Eventos [ x , LAPSO DE EVENTO] , DIA DE LAPSO ] =

101

Lapsos [ Eventos [ y , LAPSO DE EVENTO] , DIA DE LAPSO ]

)

−>

(

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

MULTIPLES CLASES] = 1

) ,

$H10

f o r A l l x : INDEX EVENTOS.

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

Base Lapsos Vetados + Eventos [ x , LAPSO DE EVENTO ] ] = 0 ,

$H11

f o r A l l x : INDEX EVENTOS.

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

Base Ubicac iones Vetadas +

Eventos [ x , UBICACION DE EVENTO ] ] = 0 ,

$S4

f o r A l l x : INDEX EVENTOS.

Act iv idades [ Eventos [ x , ACTIVIDAD DE EVENTO] ,

CANT ESTUDIANTES DE ACTIVIDAD] <= Ubicac iones [ Eventos [ x ,

UBICACION DE EVENTO] , CAPACIDAD DE UBICACION] ,

$S7

f o r A l l x : INDEX ACTIVIDADES.

f o r A l l y : INDEX EVENTOS.

f o r A l l z : INDEX EVENTOS.

(

y != z

/\

Eventos [ y , ACTIVIDAD DE EVENTO] =

Eventos [ z , ACTIVIDAD DE EVENTO]

102

/\

Eventos [ y , ACTIVIDAD DE EVENTO] =

Act iv idades [ x , ID ]

)

−>

(

Eventos [ y , UBICACION DE EVENTO] =

Eventos [ z , UBICACION DE EVENTO]

)

6.1.3. Metricas de evaluacion

Con el fin de evaluar el nivel de desempeno de la solucion propuesta, en contraste con las

hipotesis iniciales, se contemplaran las siguientes metricas a la hora de evaluar:

Tiempo de ejecucion:

◦ Por caso:

◦ Menor tiempo.

◦ Mayor tiempo.

◦ Tiempo promedio.

◦ Por data-set :

◦ Menor tiempo.

◦ Mayor tiempo.

◦ Tiempo promedio.

◦ Por subconjunto de restricciones:

◦ Menor tiempo.

◦ Mayor tiempo.

◦ Tiempo promedio.

103

Cantidad de ejecuciones exitosas: se dice que una ejecucion es exitosa cuando,

dado los archivos de entrada a ser procesados por SavileRow, la estructura de los mis-

mos, inherente a los datos que contienen, no exceden la capacidad de procesamiento

del programa (mas en especıfico, de los propagadores de restricciones), sino que, pro-

cesados correctamente, redundan en una salida util para la continuacion de procesos

que complementen los ya desarrollados. Se medira la cantidad de ejecuciones exitosas

en terminos de los tres principales elementos:

◦ Por caso.

◦ Por data-set .

◦ Por subconjunto de restricciones.

Se realizara el analisis de tales valores usando las correspondientes tablas y graficos

comparativos.

6.2. Analisis de resultados

6.2.1. Hipotesis iniciales

A continuacion se describe el conjunto de hipotesis que se busca se cumplan en los resul-

tados de las simulaciones.

Siempre hay una transformacion valida de cualquier condicion del modelo original a

una de las condiciones del modelo general.

Siempre hay una transformacion valida de cualquier entidad del modelo original a una

de las entidades del modelo general.

Sea un caso de prueba, compuesto de:

◦ Un modelo original transformado al modelo general.

◦ Una instancia del mundo real del modelo original, tambien transformada para ser

procesada por el modelo general.

104

El conjunto de algoritmos de propagacion escogidos para optimizar el modelo de entrada

deberıan ejecutarse exitosamente, en el peor de los casos, sobre un porcentaje mınimo

de la poblacion original acordado a la hora de aplicar las metricas de evaluacion.

6.2.2. Resultados obtenidos

Sea R1 el conjunto de restricciones del caso de prueba PE-CTT:

R1 = {H1, H2, H3, H4, H5, S2}

Sea R2 el conjunto de restricciones del caso de prueba CB-CTT:

R2 = {H6, H7, H8, H9, H10, H11, S4, S7}

Sea P1 el conjunto potencia de R1 menos ∅ (P1 = P (R1)− ∅), y P2 el conjunto potencia

de R2 menos ∅ (P2 = P (R2) − ∅). Cada elemento de que cada conjunto potencia tiene su

representacion en un archivo .eprime, como se comento previamente.

Definicion de siglas:

CP : Cantidad de pruebas.

PE: Pruebas exitosas.

AV GE: Porcentaje de exito.

MINSOL: Menor tiempo de solucion (en segundos).

MAXSOL: Mayor tiempo de solucion (en segundos).

AV GSOL: Tiempo de solucion promedio (en segundos).

105

Entrada CP PES AV GE MINSOL MAXSOL AV GSOL

toy 255 255 1.0000 0.80 1.47 1.36

comp01 255 253 0.9921 1.68 2.48 2.17

comp11 255 250 0.9803 1.81 2.73 2.16

test1 255 210 0.8235 4.95 6.42 5.67

test2 255 228 0.8941 5.09 5.37 5.20

EA11 255 199 0.7803 11.23 20.18 16.96

comp15 255 201 0.7882 6.37 10.26 8.95

test4 255 200 0.7843 13.50 17.62 15.90

comp02 255 201 0.7882 14.64 16.05 15.38

EA06 255 195 0.7647 18.78 27.51 22.50

test3 255 190 0.7450 20.92 23.06 21.72

comp08 255 189 0.7411 21.06 26.13 23.43

EA12 255 170 0.6667 26.20 34.45 31.48

Udine4 255 169 0.6627 27.33 43.38 38.53

DDS7 255 168 0.6588 27.47 39.66 35.30

comp14 255 150 0.5882 33.61 48.96 43.54

comp19 255 130 0.5098 32.75 44.58 38.19

comp21 255 125 0.4901 33.89 41.89 38.79

comp13 255 132 0.5176 42.03 54.56 46.49

comp09 255 110 0.4313 39.16 53.35 48.84

Udine3 255 101 0.3960 48.30 61.28 55.26

comp04 255 104 0.4078 47.44 63.85 58.56

EA01 255 53 0.2078 51.58 58.76 54.80

EA08 255 27 0.1058 50.72 78.83 68.65

EA04 255 36 0.1411 51.86 70.22 64.36

Tabla 3: Resultados de Caso de Prueba CB-CTT

106

Entrada CP PES AV GE MINSOL MAXSOL AV GSOL

easy05 63 45 0.7142 1.30 1.44 1.36

easy02 63 45 0.7142 1.31 2.54 2.01

easy03 63 45 0.7142 1.30 1.73 1.64

easy01 63 45 0.7142 1.42 2.56 1.53

easy04 63 45 0.7142 1.47 3.10 2.98

o12 63 34 0.5397 1.36 1.98 1.75

o17 63 30 0.4761 1.78 2.56 1.96

o15 63 37 0.5873 2.16 3.76 3.44

med 4 63 32 0.5079 3.04 5.43 4.46

medium01 63 30 0.4761 5.44 9.65 7.23

o20 63 29 0.4603 3.79 8.17 5.64

medium04 63 31 0.4921 2.94 5.55 3.96

medium03 63 29 0.4603 2.98 7.43 5.11

med 8 63 25 0.3968 5.34 7.83 6.01

medium02 63 31 0.4921 4.93 10.54 7.77

medium05 63 30 0.4761 5.45 9.74 6.74

med 1 63 30 0.4761 5.47 11.83 9.41

med 9 63 27 0.4286 6.11 10.64 8.59

med 3 63 28 0.4444 4.40 7.79 6.74

med 2 63 34 0.5397 6.12 9.19 8.37

big 17 63 7 0.1111 8.41 12.56 9.91

big 7 63 15 0.2381 7.39 12.32 10.56

big 6 63 14 0.2222 5.42 11.98 11.44

big 11 63 18 0.2857 7.44 12.09 9.67

big 10 63 10 0.1587 6.43 10.32 7.90

Tabla 4: Resultados de Caso de Prueba PE-CTT

107

A continuacion se muestran en graficas los valores ya contemplados en las dos tablas

anteriores, en donde se puede contemplar mejor, a modo de analisis, el comportamiento de

la propuesta construida en este trabajo para la optimizacion del modelo de restricciones:

Figura 15: CB-CTT: Proporcion de casos exitosos

108

Figura 16: CB-CTT: Menor tiempo de solucion por caso

Figura 17: CB-CTT: Mayor tiempo de solucion por caso

109

Figura 18: CB-CTT: Tiempo promedio de solucion por caso

Figura 19: PE-CTT: Proporcion de casos exitosos

110

Figura 20: PE-CTT: Menor tiempo de solucion por caso

Figura 21: PE-CTT: Mayor tiempo de solucion por caso

111

Figura 22: PE-CTT: Tiempo promedio de solucion por caso

A modo de ejemplo, se puede contemplar como serıa el modelo optimizado en formato

.minion del ejemplo mostrado en la figura 14 y modelado en posteriormente en Essence en

6.1.2

MINION 3

# CSETopLevel number = 0

# CSETopLeve l e l iminated express ions = 0

# CSETopLeve l tota l s i ze = 0

# CSE active number = 0

# C SE a c t i v e e l i m in a t e d e xp r e s s i o n s = 0

# C S E a c t i v e t o t a l s i z e = 0

**VARIABLES**

DISCRETE Eventos 00000 00000 #

{1 . . 3 0}

DISCRETE Eventos 00000 00001 #

{1 . . 3 0}

DISCRETE Eventos 00000 00002 #

{1 . . 3 0}

112

DISCRETE Eventos 00000 00003 #

{1 . . 3 0}

DISCRETE Eventos 00000 00004 #

{1 . . 3 0}

DISCRETE Eventos 00000 00005 #

{1 . . 3 0}

DISCRETE Eventos 00001 00000 #

{1 . . 3 0}

DISCRETE Eventos 00001 00001 #

{1 . . 3 0}

DISCRETE Eventos 00001 00002 #

{1 . . 3 0}

DISCRETE Eventos 00001 00003 #

{1 . . 3 0}

DISCRETE Eventos 00001 00004 #

{1 . . 3 0}

DISCRETE Eventos 00001 00005 #

{1 . . 3 0}

DISCRETE Eventos 00002 00000 #

{1 . . 3 0}

DISCRETE Eventos 00002 00001 #

{1 . . 3 0}

DISCRETE Eventos 00002 00002 #

{1 . . 3 0}

DISCRETE Eventos 00002 00003 #

{1 . . 3 0}

DISCRETE Eventos 00002 00004 #

{1 . . 3 0}

DISCRETE Eventos 00002 00005 #

{1 . . 3 0}

113

DISCRETE Eventos 00003 00000 #

{1 . . 3 0}

DISCRETE Eventos 00003 00001 #

{1 . . 3 0}

DISCRETE Eventos 00003 00002 #

{1 . . 3 0}

DISCRETE Eventos 00003 00003 #

{1 . . 3 0}

DISCRETE Eventos 00003 00004 #

{1 . . 3 0}

DISCRETE Eventos 00003 00005 #

{1 . . 3 0}

DISCRETE Eventos 00004 00000 #

{1 . . 3 0}

DISCRETE Eventos 00004 00001 #

{1 . . 3 0}

DISCRETE Eventos 00004 00002 #

{1 . . 3 0}

DISCRETE Eventos 00004 00003 #

{1 . . 3 0}

DISCRETE Eventos 00004 00004 #

{1 . . 3 0}

DISCRETE Eventos 00004 00005 #

{1 . . 3 0}

DISCRETE Eventos 00005 00000 #

{1 . . 3 0}

DISCRETE Eventos 00005 00001 #

{1 . . 3 0}

DISCRETE Eventos 00005 00002 #

{1 . . 3 0}

114

DISCRETE Eventos 00005 00003 #

{1 . . 3 0}

DISCRETE Eventos 00005 00004 #

{1 . . 3 0}

DISCRETE Eventos 00005 00005 #

{1 . . 3 0}

**TUPLELIST**

Act iv idades 2 31

3 1 1 1 40 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 3 4 3

4 0 1 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 4 4 3

**VARIABLES**

ALIAS Act iv idades [2 ,31 ]=

[ [ 3 , 1 , 1 , 1 , 40 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 ,

0 , 0 , 0 , 0 , 0 , 0 , 1 , 3 , 4 , 3 ] , [ 4 , 0 , 1 , 1 , 18 , 0 , 0 , 0 , 0 , 0 ,

0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 4 , 4 , 3 ] ]

**TUPLELIST**

Lapsos 20 5

1 1 1 0 0

2 1 2 0 0

3 1 3 0 0

4 1 4 0 0

5 2 1 0 0

6 2 2 0 0

7 2 3 0 0

8 2 4 0 0

9 3 1 1 0

10 3 2 1 0

11 3 3 0 0

12 3 4 0 0

13 4 1 0 0

115

14 4 2 0 0

15 4 3 1 0

16 4 4 1 0

17 5 1 0 0

18 5 2 0 0

19 5 3 0 0

20 5 4 0 0

**VARIABLES**

ALIAS Lapsos [ 2 0 , 5 ] = [

[ 1 , 1 , 1 , 0 , 0 ] , [ 2 , 1 , 2 , 0 , 0 ] , [ 3 , 1 , 3 , 0 , 0 ] ,

[ 4 , 1 , 4 , 0 , 0 ] , [ 5 , 2 , 1 , 0 , 0 ] , [ 6 , 2 , 2 , 0 , 0 ] ,

[ 7 , 2 , 3 , 0 , 0 ] , [ 8 , 2 , 4 , 0 , 0 ] , [ 9 , 3 , 1 , 1 , 0 ] ,

[ 1 0 , 3 , 2 , 1 , 0 ] , [ 1 1 , 3 , 3 , 0 , 0 ] , [ 1 2 , 3 , 4 , 0 , 0 ] ,

[ 1 3 , 4 , 1 , 0 , 0 ] , [ 1 4 , 4 , 2 , 0 , 0 ] , [ 1 5 , 4 , 3 , 1 , 0 ] ,

[ 1 6 , 4 , 4 , 1 , 0 ] , [ 1 7 , 5 , 1 , 0 , 0 ] , [ 1 8 , 5 , 2 , 0 , 0 ] ,

[ 1 9 , 5 , 3 , 0 , 0 ] , [ 2 0 , 5 , 4 , 0 , 0 ] ]

**TUPLELIST**

Ubicac iones 3 5

1 32 0 0 1

2 50 0 1 0

3 40 1 0 0

**VARIABLES**

ALIAS Ubicac iones [ 3 , 5 ] = [ [ 1 , 32 , 0 , 0 , 1 ] , [ 2 , 50 , 0 , 1 , 0 ] ,

[ 3 , 40 , 1 , 0 , 0 ] ]

**SEARCH**

PRINT[

[ Eventos 00000 00000 ] , [ Eventos 00000 00001 ] , [ Eventos 00000 00002 ] ,

[ Eventos 00000 00003 ] , [ Eventos 00000 00004 ] , [ Eventos 00000 00005 ] ,

[ Eventos 00001 00000 ] , [ Eventos 00001 00001 ] , [ Eventos 00001 00002 ] ,

[ Eventos 00001 00003 ] , [ Eventos 00001 00004 ] , [ Eventos 00001 00005 ] ,

116

[ Eventos 00002 00000 ] , [ Eventos 00002 00001 ] , [ Eventos 00002 00002 ] ,

[ Eventos 00002 00003 ] , [ Eventos 00002 00004 ] , [ Eventos 00002 00005 ] ,

[ Eventos 00003 00000 ] , [ Eventos 00003 00001 ] , [ Eventos 00003 00002 ] ,

[ Eventos 00003 00003 ] , [ Eventos 00003 00004 ] , [ Eventos 00003 00005 ] ,

[ Eventos 00004 00000 ] , [ Eventos 00004 00001 ] , [ Eventos 00004 00002 ] ,

[ Eventos 00004 00003 ] , [ Eventos 00004 00004 ] , [ Eventos 00004 00005 ] ,

[ Eventos 00005 00000 ] , [ Eventos 00005 00001 ] , [ Eventos 00005 00002 ] ,

[ Eventos 00005 00003 ] , [ Eventos 00005 00004 ] , [ Eventos 00005 00005 ]

]

VARORDER STATIC [

Eventos 00000 00000 , Eventos 00000 00001 , Eventos 00000 00002 ,

Eventos 00000 00003 , Eventos 00000 00004 , Eventos 00000 00005 ,

Eventos 00001 00000 , Eventos 00001 00001 , Eventos 00001 00002 ,

Eventos 00001 00003 , Eventos 00001 00004 , Eventos 00001 00005 ,

Eventos 00002 00000 , Eventos 00002 00001 , Eventos 00002 00002 ,

Eventos 00002 00003 , Eventos 00002 00004 , Eventos 00002 00005 ,

Eventos 00003 00000 , Eventos 00003 00001 , Eventos 00003 00002 ,

Eventos 00003 00003 , Eventos 00003 00004 , Eventos 00003 00005 ,

Eventos 00004 00000 , Eventos 00004 00001 , Eventos 00004 00002 ,

Eventos 00004 00003 , Eventos 00004 00004 , Eventos 00004 00005 ,

Eventos 00005 00000 , Eventos 00005 00001 , Eventos 00005 00002 ,

Eventos 00005 00003 , Eventos 00005 00004 , Eventos 00005 00005

]

VARORDER AUX[

Eventos 00000 00000 , Eventos 00000 00001 , Eventos 00000 00002 ,

Eventos 00000 00003 , Eventos 00000 00004 , Eventos 00000 00005 ,

Eventos 00001 00000 , Eventos 00001 00001 , Eventos 00001 00002 ,

Eventos 00001 00003 , Eventos 00001 00004 , Eventos 00001 00005 ,

Eventos 00002 00000 , Eventos 00002 00001 , Eventos 00002 00002 ,

Eventos 00002 00003 , Eventos 00002 00004 , Eventos 00002 00005 ,

117

Eventos 00003 00000 , Eventos 00003 00001 , Eventos 00003 00002 ,

Eventos 00003 00003 , Eventos 00003 00004 , Eventos 00003 00005 ,

Eventos 00004 00000 , Eventos 00004 00001 , Eventos 00004 00002 ,

Eventos 00004 00003 , Eventos 00004 00004 , Eventos 00004 00005 ,

Eventos 00005 00000 , Eventos 00005 00001 , Eventos 00005 00002 ,

Eventos 00005 00003 , Eventos 00005 00004 , Eventos 00005 00005 ]

**CONSTRAINTS**

watched−or ({ d i s eq ( Eventos 00003 00002 , Eventos 00000 00002 ) ,

d i s eq ( Eventos 00003 00003 , Eventos 00000 00003 )} )

watched−or ({ d i s eq ( Eventos 00001 00002 , Eventos 00002 00002 ) ,

d i s eq ( Eventos 00001 00003 , Eventos 00002 00003 )} )

watched−or ({ d i s eq ( Eventos 00003 00002 , Eventos 00005 00002 ) ,

d i s eq ( Eventos 00003 00003 , Eventos 00005 00003 )} )

watched−or ({ d i s eq ( Eventos 00004 00002 , Eventos 00000 00002 ) ,

d i s eq ( Eventos 00004 00003 , Eventos 00000 00003 )} )

watched−or ({ d i s eq ( Eventos 00004 00002 , Eventos 00005 00002 ) ,

d i s eq ( Eventos 00004 00003 , Eventos 00005 00003 )} )

watched−or ({ d i s eq ( Eventos 00005 00002 , Eventos 00001 00002 ) ,

d i s eq ( Eventos 00005 00003 , Eventos 00001 00003 )} )

watched−or ({ d i s eq ( Eventos 00000 00002 , Eventos 00005 00002 ) ,

d i s eq ( Eventos 00000 00003 , Eventos 00005 00003 )} )

watched−or ({ d i s eq ( Eventos 00000 00002 , Eventos 00002 00002 ) ,

d i s eq ( Eventos 00000 00003 , Eventos 00002 00003 )} )

watched−or ({ d i s eq ( Eventos 00003 00002 , Eventos 00001 00002 ) ,

d i s eq ( Eventos 00003 00003 , Eventos 00001 00003 )} )

watched−or ({ d i s eq ( Eventos 00004 00002 , Eventos 00001 00002 ) ,

d i s eq ( Eventos 00004 00003 , Eventos 00001 00003 )} )

watched−or ({ d i s eq ( Eventos 00003 00002 , Eventos 00002 00002 ) ,

d i s eq ( Eventos 00003 00003 , Eventos 00002 00003 )} )

watched−or ({ d i s eq ( Eventos 00004 00002 , Eventos 00002 00002 ) ,

118

d i s eq ( Eventos 00004 00003 , Eventos 00002 00003 )} )

watched−or ({ d i s eq ( Eventos 00000 00002 , Eventos 00001 00002 ) ,

d i s eq ( Eventos 00000 00003 , Eventos 00001 00003 )} )

watched−or ({ d i s eq ( Eventos 00005 00002 , Eventos 00002 00002 ) ,

d i s eq ( Eventos 00005 00003 , Eventos 00002 00003 )} )

watched−or ({ d i s eq ( Eventos 00003 00002 , Eventos 00004 00002 ) ,

d i s eq ( Eventos 00003 00003 , Eventos 00004 00003 )} )

**EOF**

Como ya se dijo, el codigo anterior es el resultado de optimizar el modelo en Essence de

6.1.2, que a su vez era representacion de la instancia usada como ejemplo de la figura 14.

Cada una de las sentencias y condiciones sirven como input para el solver Minion, quien se

encargarıa de buscar la asignacion correspondiente entre variables (marcadas con el comenta-

rio **VARIABLES** ) respetando las restricciones planteadas (marcadas con el comentario

**CONSTRAINTS** ). Al tope de lo que serıa el archivo .minion se muestran valores refe-

renciales al proceso previo de optimizacion, tales como la cantidad de expresiones eliminadas,

entre otros.

119

7. Conclusiones y recomendaciones

7.1. Conclusiones de la investigacion

Como se ha podido ver a lo largo de la investigacion, hay dos elementos centrales que

caracterizan al problema de asignacion de horarios y son la base de su alta complejidad a la

hora de resolverlo, el primero es su naturaleza No Polinomial, y el segundo es la creciente

cantidad de instancias que existen del problema, que van desde planeacion de tareas en

entornos laborales como fabricas o empresas [24], hasta contextos academicos, siendo el mas

tratado y desde el cual parten la mayorıa de las investigaciones en el tema la asignacion de

horarios en universidades [33] (University Timetabling Problem).

Tomando como referencia un conjunto limitado de instancias del timetabling problem,

caracterizados por ser los principales representantes del problema en cuanto a generalidad

de sus entidades, relaciones entre las mismas y restricciones aplicadas a esas relaciones, se

crea un modelo general de costos (o visto de manera simplista, una especie de plantilla),

que sirve como puente para, tomado un modelo cualquiera, convertirlo a ese modelo general

para luego, escogiendo un subconjunto de las restricciones del modelo original, ejecutar las

operaciones de optimizacion de formulacion del modelo, basadas en algoritmos de propagacion

de restricciones.

Teniendo los resultados de las simulaciones (ejecutadas durante varias iteraciones), se

pueden concluir similitudes tanto para el caso del Post-Enrollment Course Timetabling como

para el caso del Curriculum-Based Course Timetabling, las cuales vale la pena recalcar:

En ambos casos se nota un decremento aproximadamente lineal en la eficiencia de la

ejecucion de los algoritmos optimizadores, siendo casi nula la existencia de resultados

positivos conforme se tratan casos cada vez mas complejos.

Si bien la intencion original del proyecto era crear un marco de trabajo y de modelado

que asignase de manera realista un peso a cada una de las restricciones de la instancia

del problema a tratar (lo cual sucede cuando se habla de ejecuciones exitosas), los

algoritmos propagadores escogidos (la tecnologıa de SavileRow) muestran (en base a

las metricas obtenidas) un lımite de eficacia en cuanto a tratamiento y asignacion de

120

prioridades a cada una de las restricciones conforme crece el numero de la poblacion a

tratar (Actividades, Eventos y Participantes).

Se plantea entonces la posibilidad de trabajar con versiones alternativas de las formu-

laciones ya realizadas (en relacion a los archivos .eprime en donde estan contenidas las

condiciones y los archivos .eparam en donde se concentra la data de prueba) que man-

tengan el mismo entramado logico, pero que aproveche otras fortalezas de los algoritmos

escogidos para las optimizaciones.

7.2. Trabajos futuros

Propagadores de caracter heurıstico: conociendo el concepto de propagacion de

restricciones, existen trabajos que ya han abordado la posibilidad de desarrollar el mis-

mo concepto pero bajo un marco estocastico, como se puede apreciar en [68] y en [73].

Este se podrıa aplicar en la busqueda de una mejor solucion al problema planteado en el

trabajo actual, ya sea modificando un modulo existente de propagacion de restricciones,

o programando uno nuevo.

El trabajo deberıa servir como punto de partida para la recoleccion de con-

versiones de distintas instancias del problema de asignacion de horarios al

esquema general aquı planteado, y en consecuencia para el conjunto de restriccio-

nes reformuladas. Ası mismo, conforme aumente la cantidad de instancias recolectadas,

estas deben ser progresivamente de mayor complejidad en cuanto a estructura de enti-

dades, relaciones y restricciones, con el fin de robustecer el modelo general construido.

121

Referencias

[1] Cassowary. https://sourceforge.net/projects/cassowary/. 55

[2] Choco. http://www.choco-solver.org. 53

[3] Constraint 0.4.1. https://pypi.python.org/pypi/constraint/. 54

[4] Eclipseclp. http://eclipseclp.org. 53

[5] Facile. https://hal-enac.archives-ouvertes.fr/hal-00938018. 55

[6] Fpcs. http://www.i3s.unice.fr/~cpjm/misc/fpcs.html. 55

[7] Gecode. http://www.gecode.org. 55

[8] Gurobi. http://www.gurobi.com. 55

[9] Haifacsp. http://ie.technion.ac.il/~ofers/HCSP/. 55

[10] Ibex. http://www.ibex-lib.org/. 55

[11] Ibm ilog cplex. http://www-03.ibm.com/software/products/es/

ibilogcpleoptistud. 54

[12] Jacop. http://www.jacop.eu/. 55

[13] Lingo. http://www.lindo.com/index.php?option=com_content&view=article&id=

2&Itemid=10. 55

[14] Loom. http://www.isi.edu/isd/LOOM/. 55

[15] Mistral. http://www.academia.edu/2659313/Mistral_a_constraint_

satisfaction_library. 55

[16] Mozart programming system. https://mozart.github.io/mozart-v1/doc-1.4.0/

cpitut/index.html. 54

[17] Opta planner. http://www.optaplanner.org/. 55

122

[18] python-constraint. https://labix.org/python-constraint. 54

[19] Scip. http://scip.zib.de/. 55

[20] Simple theorem prover (aka smt solver). http://stp.github.io/. 55

[21] Soplex. http://soplex.zib.de/. 55

[22] Swi-prolog. http://www.swi-prolog.org. 54

[23] Xpress. http://www.maths.ed.ac.uk/hall/Xpress/. 55

[24] Amnon Meisels, E. G., and Solotorevsky, G. Combining Rules and Constraints

for Employee Timetabling. Intern. Jou. Intell. Syst. (1997). 120

[25] Apt, K. R. The essence of constraint propagation. Theor. Comput. Sci. 221, 1-2 (June

1999), 179–210. 3, 20

[26] Arora, S., and Barak, B. Computational Complexity: A Modern Approach, 1st ed.

Cambridge University Press, New York, NY, USA, 2009. 18

[27] B, S. Modelling for Constraint Programming. Cork Constraint Computation Centre,

University College Cork, Ireland (2005). 20

[28] Bartak, R. Theory and Practice of Constraint Propagation. Proceedings of the 3rd

Workshop on Constraint Programming in Decision and Control (2001). 3, 20

[29] Bessiere, C., and Regin, J.-C. Refining the basic constraint propagation algorithm.

In IJCAI (2001), vol. 1, pp. 309–315. 42

[30] Burke, E., Jackson, K., Kingston, J. H., and Weare, R. Automated university

timetabling: The state of the art. The computer journal 40, 9 (1997), 565–571. 25

[31] Burke, E. K., Kingston, J. H., and Pepper, P. A. A standard data format for

timetabling instances. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998, pp. 213–222.

11

123

[32] Calle, D. Curso de introduccion al modelado matematico. Publicado por la Univer-

sidad Javeriana, accesible en htpp://mathmodeling.org. 5, 30, 31, 32, 33, 34

[33] Carter, M. W. A comprehensive course timetabling and student scheduling system at

the university of waterloo. In Selected Papers from the Third International Conference

on Practice and Theory of Automated Timetabling III (London, UK, UK, 2001), PATAT

’00, Springer-Verlag, pp. 64–84. 120

[34] Clay-Mathematics-Institute. Millennium prize problems, 2000. http://www.

claymath.org/prizeproblems/. 20

[35] Cook, S. A. The complexity of theorem-proving procedures. Proceedings of the Third

Annual ACM Symposium on Theory of Computing (1971), 151–158. 19

[36] Cooper, T. B., and Kingston, J. H. The complexity of timetable construction

problems. In Selected Papers from the First International Conference on Practice and

Theory of Automated Timetabling (London, UK, UK, 1996), Springer-Verlag, pp. 283–

295. 3, 7, 16

[37] Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E. Introduction to

Algorithms, 2nd ed. McGraw-Hill Higher Education, 2001. 18

[38] D, D. An introduction to timetabling. European Journal of Operations Research (1984).

3, 7, 16

[39] Di Gaspero Lucas, McCollum Barry, S. A. The Second International Timeta-

bling Competition (ITC-2007): Curriculum-Based Course Timetabling (Track 3). Tech.

rep., University of Udine and School of Electronics, Electrical Engineering and Computer

Science, Queen’s University SARC Building, Belfast, United Kingdom, 2007. 59

[40] Edwar, B. An Introduction to Mathematical Modeling. Dover Publications, Inc., Mi-

neola, New York, USA, 1978. 42

[41] Christian Bessiere. Constraint propagation - technical report. Tech. rep., University of

Montpellier, 2006. 3, 20

124

[42] Even, S., Itai, A., and Shamir, A. On the complexity of time table and multi-

commodity flow problems. In Proceedings of the 16th Annual Symposium on Foundations

of Computer Science (Washington, DC, USA, 1975), SFCS ’75, IEEE Computer Society,

pp. 184–193. 20, 25

[43] FET. Software de generacion automatica de horarios, 2015. Disponible en http://

lalescu.ro/liviu/fet. 14

[44] for Emergent Computing, C. New ”HarderInstances for the University Course

Timetabling Problem. http://www.soc.napier.ac.uk/~benp/centre/timetabling/

harderinstances.htm, 2006. 65

[45] Fortnow, L., and Homer, S. A short history of computational complexity. beatcs

80 (jun 2003). Computational Complexity Column. 18

[46] Frisch Alan, H. W. Essence: A Constraint Language for Specifying Combinatorial

Problems. Journal Constraints (September 2008). 57

[47] G, P. How To Solve It, 2nd ed. Princeton University, 1973. 30

[48] Garcia J, M. J. Modelos y Metodos de Investigacion de Operaciones. Procedimientos

para Pensar. Grupo de Investigacion ROGLE, 2011. 30

[49] Garey, M. R., and Johnson, D. S. Computers and Intractability: A Guide to the

Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. 18

[50] Gent Ian, J. C. MINION: A Fast, Scalable, Constraint Solver. Proceedings of the 17th

European Conference on Artificial Intelligence (2006). 57

[51] Glover, F. Future paths for integer programming and links to artificial intelligence.

Comput. Oper. Res. 13, 5 (May 1986), 533–549. 7, 12

[52] Grobner, M., Wilke, P., and Buttcher, S. A Standard Framework for Time-

tabling Problems. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003, pp. 24–38. 7,

10

125

[53] Guido, T. Constraint Propagation - Models, Techniques, Implementation. PhD thesis,

Saarland University, 2009. 3, 20

[54] Hartmanis J, S. R. On the computational complexity of algorithms. Transactions of

the American Mathematical Society (1965). 19

[55] Hillier, F. S., and Lieberman, G. J. Introduction to Operations Research, 4th Ed.

Holden-Day, Inc., San Francisco, CA, USA, 1986. 15

[56] IBM. Constraint programming technology, 2001. Articulo dispo-

nible en http://www-01.ibm.com/software/commerce/optimization/

constraint-programming-technology/. 20

[57] ITC. International timetabling contest 2011. http://www.utwente.nl/ctit/hstt/

itc2011/welcome. 15

[58] J, K. Timetable Construction: The Algorithms and Complexity Perspective, 2006. 3, 7,

16

[59] J, P. Constraint programming next challenge: Simplicity of use, 2004. M. Wallace (Ed.),

Principles and Practice of Constraint Programming - CP 2004, LNCS 3258, Springer.

20

[60] Jeffrey, K. Data Formats for Exchange of Real-World Timetabling Problem Instances

and Solutions. School of Information Technologies - The University of Sidney (2006).

13

[61] Karp, R. M. Combinatorics, complexity, and randomness, Feb. 1986. 19

[62] Kingston, J. Modelling Timetabling Problems with STTL. Selected papers from the

Third International Conference on Practice and Theory of Automated Timetabling III

(2001), 309–321. 12

[63] Kristiansen, Simon; Stidsen, T. J. R. A comprehensive study of educational

timetabling - a survey, 2013. 13

126

[64] L, S. The polynomial-time hierarchy. Theor. Computer Science (1976). 19

[65] Lach, G., and Lubbecke, M. E. Curriculum based course timetabling: new solutions

to udine benchmark instances. Annals of Operations Research 194, 1 (2012), 255–272.

59

[66] Lewis, R. A survey of metaheuristic-based techniques for university timetabling pro-

blems. OR spectrum 30, 1 (2008), 167–190. 34

[67] Lewis, R., Paechter, B., McCollum, B., et al. Post enrolment based course

timetabling: A description of the problem model used for track two of the second inter-

national timetabling competition. Cardiff Business School, 2007. 57

[68] Meinolf SEllman, W. H. Heuristic constraint propagation, 2002. M. Wallace (Ed.),

Principles and Practice of Constraint Programming - CP 2004, LNCS 3258, Springer.

121

[69] Modelling, C. Minion. http://constraintmodelling.org/minion/, 2015. 56

[70] Muhlenthaler, M., and Wanka, R. Fairness in academic course timetabling. CoRR

abs/1303.2860 (2013). 13

[71] Muller, T., and Murray, K. Comprehensive approach to student sectioning. Annals

of Operations Research 181, 1 (2010), 249–269. 41

[72] Muller Thomas, R. H. Real-life Curriculum-based Timetabling. PATAT (June 2012).

59

[73] Narendra Jussien, O. L. Local search with constraint propagation and conflict-based

heuristics. Artificial Intelligence - ELSEVIER (2002). 121

[74] of St Andrews, U. Savile Row. http://savilerow.cs.st-andrews.ac.uk, 2014.

55, 56

[75] Ozcan, E. Towards an xml-based standard for timetabling problems: Ttml. Multidisci-

plinary Scheduling: Theory and Applications: 1st International Conference, MISTA ’03

Nottingham, UK, 13–15 August 2003 Selected Papers (2005), 163–185. 13

127

[76] PATAT. Practice and theory of automated timetabling. http://www.

patatconference.org/. 15

[77] PATAT. International Timetabling Competition - Datasets. http://www.cs.qub.ac.

uk/itc2007/Login/SecretPage.php, 2007. 65

[78] PATAT, M. N. International Timetabling Competition. http://sferics.idsia.ch/

Files/ttcomp2002/, 2002. 65

[79] Pawlan, M. Essentials of the Java Programming Language, Part 1. http://www.

oracle.com/technetwork/java/index-138747.html, March 1999. 56

[80] Ranson, D., and Ahmadi, S. An extensible modelling framework for timetabling pro-

blems. Practice and Theory of Automated Timetabling VI: 6th International Conference,

PATAT 2006 Brno, Czech Republic, August 30–September 1, 2006 Revised Selected Pa-

pers (2007), 383–393. 12

[81] Reis, L. P., and Oliveira, E. A language for specifying complete timetabling pro-

blems. In Selected Papers from the Third International Conference on Practice and

Theory of Automated Timetabling III (London, UK, UK, 2001), PATAT ’00, Springer-

Verlag, pp. 322–341. 12

[82] Rossi-Doria, O. A Comparison of the Performance of Different Metaheuristics on the

Timetabling Problem. http://iridia.ulb.ac.be/supp/IridiaSupp2002-001/, 2002.

65

[83] Rossi-Doria, O. Curriculum-Based Course TimeTabling - Instances. http://satt.

diegm.uniud.it/ctt/index.php?page=instances, 2016. 70

[84] Rozi M, Tajudin A, M. A. University course timetabling: A general model. The

2nd International Conference on Research and Education in Mathematics (ICREM 2)

(2005). 7, 10

[85] Simeone, M. A. R., and Carnevale, J. Logic models: a systems tool for performance

management. Evaluation and Program Planning, 24 (2001), 73–81. 42

128

[86] Sturton, C., Sinha, R., Dang, T. H., Jain, S., McCoyd, M., Tan, W. Y.,

Maniatis, P., Seshia, S. A., and Wagner, D. Symbolic software model validation.

In Formal Methods and Models for Codesign (MEMOCODE), 2013 Eleventh IEEE/ACM

International Conference on (2013), IEEE, pp. 97–108. 46

[87] Taha, H. A. Operations Research: An Introduction (8th Edition). Prentice-Hall, Inc.,

Upper Saddle River, NJ, USA, 2006. 15

[88] Talbi, E.-G. Metaheuristics: From Design to Implementation. Wiley Publishing, 2009.

5, 18, 19

[89] UniTime. Comprehensive academic scheduling solutions., 2015. Disponible en http:

//www.unitime.org/. 14, 54

[90] WC3. Mathml. https://www.w3.org/Math/. 13

[91] Winston, W. L., and Goldberg, J. B. Operations research: applications and algo-

rithms, vol. 3. Duxbury press Belmont, CA, 2004. 25

129