Metaheurísticas para problemas de Scheduling con múltiples recursos

Resumen

Los problemas de scheduling consisten en organizar en el tiempo un conjunto de operaciones que compiten por el uso de un conjunto limitado de recursos, todo ello sujeto a una serie de restricciones y tratando de optimizar una o varias funciones objetivo. Se trata de problemas que aparecen con profusión en muchos entornos sociales y productivos, y en general presentan una alta complejidad computacional. Por estas razones, los problemas de scheduling tienen un gran interés tanto desde el punto de vista económico como desde el punto de vista académico, por lo que han sido objeto de investigación intensiva durante las últimas décadas por parte de las comunidades de Investigación Operativa e Inteligencia Artificial. Esta tesis tiene como objetivo avanzar en el estudio y resolución de problemas de scheduling en los que las tareas requieren el uso de varios tipos de recursos, materiales y humanos. Concretamente, consideramos dos familias de problemas: en primer lugar algunas variantes de uno de los problemas más conocidos en la literatura como es el job shop scheduling (JSP), en las que cada tarea requiere no solamente una máquina para realizarse, sino también un operario que la asista durante todo su tiempo de procesamiento. El segundo problema es un caso particular del problema de asignación de vehículos y conductores a rutas de transporte de viajeros, conocido en la literatura como VCSP (Vehicle and Crew Scheduling Problem). Dada la alta complejidad de estos problemas y el tamaño de las instancias de interés, consideramos que las metaheurísticas constituyen una aproximación razonable. Así, utilizaremos metaheurísticas híbridas que combinen métodos basados en poblaciones, como los algoritmos genéticos, en la fase de diversificación con métodos de búsqueda, como algoritmos de escalada o búsqueda tabú, en la fase de intensificación. Como metodología de trabajo, proponemos el uso de modelos gráficos disyuntivos para representar instancias de los problemas y sus soluciones. Estos modelos son útiles para estudiar las propiedades de los problemas, para diseñar algoritmos de generación de planificaciones o schedules, y también para diseñar estructuras de vecindad. Un generador de schedules es un algoritmo no determinista que se puede utilizar en distintos contextos para el cálculo de soluciones; las características más importantes de un generador de schedules que deben ser objeto de estudio son el tamaño del espacio de búsqueda que genera, la calidad media de las soluciones de este espacio y sus propiedades de dominancia. Una estructura de vecindad es una función que dada una solución devuelve un conjunto de soluciones próximas en el espacio de búsqueda a la solución de partida; en este caso, las características que se deben estudiar son el tamaño de la vecindad y la probabilidad de que esta vecindad contenga soluciones que mejoren a la solución de partida. Los generadores de schedules se utilizarán como evaluadores de cromosomas en los algoritmos genéticos y las estructuras de vecindad como generadores de nuevas soluciones en la búsqueda local. El primero de los problemas abordados es el job shop scheduling con operarios (JSO). Este es un problema propuesto recientemente en la literatura. En este caso partimos de un modelo disyuntivo y de un generador de schedules, denominado OG&T, propuestos en trabajos previos del grupo de investigación. La principal contribución en este problema es el diseño de una estructura de vecindad a partir de la cual se desarrolló un algoritmo memético que combina un algoritmo genético con un algoritmo de búsqueda local. Este algoritmo mejora los resultados de los métodos anteriores y resulta incluso muy competitivo con una implementación sobre el solver CPLEX CP Optimizer. Si tenemos en cuenta que este solver está especialmente diseñado para tratar con las características propias del JSO, como son las restricciones disyuntivas y los recursos acumulativos, se trata sin duda de un resultado muy interesante. En el algoritmo memético el generador de schedules OG&T se utiliza como decodificador, y la estrategia de vecindad que explota el algoritmo de búsqueda local se define a partir de inversiones de arcos en el grafo solución. El segundo problema que consideramos es una extensión del JSO en la que no todos los operarios tienen las mismas habilidades para atender a las tareas y además las restricciones de precedencia entre las tareas no definen un conjunto de trabajos como ocurre en el JSO o en el JSP. De este modo, el problema modela con más precisión muchas situaciones reales. Es también un problema propuesto recientemente en la literatura con la denominación JSSO (Job Shop Scheduling with Skilled Operators). Nuestra principal contribución para este problema es el diseño de un modelo disyuntivo y un generador de schedules denominado SOG&T. Hemos estudiado las propiedades de dominancia de distintos espacios de búsqueda generados por este algoritmo y lo hemos utilizado como decodificador en un algoritmo genético. Este algoritmo proporciona los mejores resultados conocidos hasta el momento en los bancos de ejemplos propuestos en la literatura. El desarrollo de estrategias de vecindad es un problema abierto que planteamos como trabajo futuro. El tercero de los problemas es una versión real del VCSP. Este tipo de problemas viene siendo considerado en la literatura desde hace casi dos décadas y hasta el momento las principales soluciones utilizan métodos de programación matemática. En el caso más general, en este problema se parte de un conjunto de trayectos programados y de un conjunto de autobuses y conductores distribuidos en distintas bases. El objetivo es asignar vehículos y conductores a cada uno de los trayectos, sujeto a un gran número de restricciones espaciales, temporales y de normativa laboral; con el objetivo de optimizar el número de vehículos y conductores, además de racionalizar las jornadas laborales de los conductores y optimizar el consumo energético. Entre otras características propias del VCSP, consideramos opciones como realizar viajes sin pasajeros (deadheads), desplazar conductores como pasajeros o programar tareas de mantenimiento a lo largo del horizonte de planificación, por las que el problema presenta una altísima complejidad computacional. En este caso nuestra principal contribución es el estudio del problema en colaboración con expertos de una compañía de transporte de viajeros por carretera, y el resultado es un modelado del problema en el marco de los problemas de satisfacción de restricciones. Siguiendo la metodología utilizada con los problemas anteriores, hemos propuesto un modelo gráfico para representar instancias del problema y soluciones. El desarrollo de generadores de schedules y de otros algoritmos de resolución es un tema de trabajo actual en el grupo de investigación. RESUMEN (en Inglés) Scheduling problems consist in organizing over time a set of operations that compete for the use of a limited set of resources, all subject to a series of constraints and trying to optimize one or several objective functions. These problems appear profusely in many social and productive environments, and in general present a high computational complexity. For these reasons, scheduling problems are of great interest from both the economical and the academical points of view, and have therefore been the object of intensive research during the last decades by the communities of Operations Research and Artificial Intelligence. This thesis has as main objective to advance in the study and resolution of scheduling problems in which tasks require the use of various types of resources, material and human. Specifically, we consider two families of problems: first, some variants of one of the most well-known problems in the literature, the job shop scheduling problem (JSP), where we consider that each task requires not only a machine to be processed, but also an operator who attends it throughout its processing time. The second problem is a particular case of the problem of assigning vehicles and drivers to passenger transport routes, known in the literature as VCSP (Vehicle and Crew Scheduling Problem). Given the high complexity of these problems and the size of the instances of interest, we consider that metaheuristics constitute a reasonable approximation. Thus, we will use hybrid metaheuristics that combine population-based methods, such as genetic algorithms, in the diversification phase with search methods, such as hill-climbing or tabu search, in the intensification phase. As working methodology, we propose the use of disjunctive graphic models to represent problem instances and their solutions. These models are useful for studying the properties of the problems, for designing schedule builders, and also for designing neighborhood structures. A schedule builder is a non-deterministic algorithm that can be used in different contexts for calculating solutions; the most important characteristics of a schedule builder that must be studied are the size of the search space it generates, the average quality of the solutions in this space and its properties of dominance. A neighborhood structure is a function that given a solution, it returns a set of nearby solutions in the search space to the starting solution. In this case, the characteristics to be studied are the size of the neighborhood and the probability that this neighborhood contains solutions that improve the starting solution. The schedule builders will be used as evaluators of chromosomes in the genetic algorithms and the neighborhood structures as generators of new solutions in the local search. The first of the addressed problems is the job shop scheduling with operators (JSO). This is a problem recently proposed in the literature. In this case we start with a disjunctive model and a schedule builder, called OG&T, proposed in previous works of the research group. The main contribution in this problem is the design of a neighborhood structure from which a memetic algorithm was developed combining a genetic algorithm with a local search algorithm. This algorithm improves the results of the previous methods and is even very competitive with an implementation on the CPLEX CP Optimizer solver. Considering that this solver is specially designed to deal with some characteristics of the JSO, such as disjunctive constraints and cumulative resources, this is undoubtedly a very interesting result. In the memetic algorithm the schedule builder OG&T is used as a decoder, and the neighborhood structure exploited by the local search algorithm is defined from arc reversals in the solution graph. The second problem we consider is an extension of the JSO in which not all operators have the same skills to assist the tasks and also the precedence relations between the tasks do not define a set of jobs on the contrary of what happens with the JSO and the JSP. This way, the problem models more precisely many real situations. It is also a problem recently proposed in the literature with the denomination JSSO (Job Shop Scheduling with Skilled Operators). Our main contribution to this problem is the design of a disjunctive model and a schedule builder called SOG&T. We have studied the dominance properties of different search spaces generated by this algorithm and we have used it as a decoder in a genetic algorithm. This algorithm yields the best results known so far in the benchmarks proposed in the literature. The development of neighborhood strategies is an open problem that we consider as future work. The third of the problems is a real version of the VCSP. This type of problems has been considered in the literature for almost two decades and until now the main solutions use mathematical programming methods. In the most general case, in this problem we start with a set of scheduled trips and a set of buses and drivers distributed in different bases or depots. The objective is to assign vehicles and drivers to each of the trips, subject to a large number of space, temporary and labor regulation constraints; with the objective of optimizing the number of vehicles and drivers, as well as rationalizing the working days of the drivers and optimizing the energy consumption. Among other characteristics of the VCSP, we consider options such as the possibility of doing trips without passengers (deadheads), displacing drivers as passengers or scheduling maintenance tasks throughout the planning horizon, by which the problem presents a very high computational complexity. In this case our main contribution is the study of the problem in collaboration with experts of a passenger transport company, and the result is a modeling of the problem in the framework of constraint satisfaction problems. Following the methodology used in the previous problems, we have devised a graphical model to represent problem instances and solutions. The development of schedule builders and other solvers is a current topic of work in the research group.