Programación de tareas: Interval Scheduling

Abstract

El objetivo de este Trabajo de Fin de Grado es realizar una revisión de algunas de las variantes más importantes o conocidas de los problemas de Interval Scheduling y otros problemas relacionados. En concreto, para cada problema, se establece una descripción del mismo y se explican los métodos más notables para encontrar una solución. La descripción de cada problema consta de los datos de entrada con los que se cuenta inicialmente y del objetivo que se pretende cumplir una vez obtenida la solución del mismo. Además de esto, en aquellos casos en los que se considera necesario, se establece la formulación de programación entera correspondiente. Para algunos problemas, junto con una descripción de los diferentes algoritmos utilizados para obtener soluciones y sus demostraciones, se establece la implementación en Xpress realizada en base a estas; así como las soluciones obtenidas para diferentes ficheros de datos con un formato acorde a la correspondiente variante del problema.

The aim of this Final Degree Project is to go over thoroughly all the most known and important variants of the Interval Scheduling problems and other related problems. Specifically, for each problem, it can be found a description and also an explanation of the most relevant methods used to find out a solution. The description of each problem consists on the input data that is known in the beginning and also the goal that should be reached when a solution is obtained. In addition, it has been added the integer programming formulation for those cases when it is considered necessary. For some problems, along with the description of the different algorithms used to get solutions and their proofs of correctness, it is explained the implementation in Xpress based on their explanation. Some results are also shown for the diferent data files with the appropiate format for the corresponding problem.