Desarrollo de técnicas de búsqueda metaheurísticas en problemas de scheduling multiobjetivo

Abstract

In Artificial Intelligence field, scheduling problems are applied to multiple real environments and its main objective is to find optimized solutions by using centralized and static search techniques. However, the reality is far from this approach, where a lot of scheduling problems take place in distributed and dynamic environments. This dynamic and distributed nature of scheduling problems, along with new objectives to optimize such as energy efficiency, force us to manage them in a efficient way in order to improve computing time while it adapts to new constraints of the problem. Each available resource usually has and associated energy consumption and it is variable depending on its use time or the assigned power work. Given a context in which more and more efficient processes are needed, we need to obtain energy efficient solutions. This represents a new view in the way that we approach scheduling problems called ¿Green Scheduling¿.

In this project we present a multi-agent model as a tool to solve Green Scheduling offline problems in production system with high energy consumption. In the proposed model, agents collaborate with each other in order to achieve an agreement in which we optimize a multiobjective function based on minimizing 3 factors: the total tardiness of the jobs, the total setup time and the total energy consumption that machines need to perform all the assigned jobs. Later, we add an online system integrating it in the offline system previously mentioned. This online system monitors the execution of the plan scheduled offline, waiting until an incidence appears. When an incidence occurs, the online system carries out a rescheduling of the affected machine in real time, redistributing the jobs originally assigned to it, if possible, and trying to minimize the impact of the incidence on the global costs of the whole production context.

The developed systems have been evaluated on several test cases and the obtained results show the utility of the proposals.

Los problemas de scheduling en Inteligencia Artificial, centrados en la asignación de recursos o tiempo a las acciones de un plan, se aplican en diversos entornos reales y su principal objetivo reside en encontrar soluciones optimizadas mediante el uso de técnicas de búsqueda centralizadas, donde, por lo general, se pretende optimizar la duración total del scheduling (makespan). Sin embargo, la realidad dista mucho de este planteamiento, donde muchos problemas de scheduling ocurren en entornos distribuidos y dinámicos. Esta naturaleza distribuida y dinámica de los problemas de scheduling, junto con los nuevos objetivos a optimizar, como la eficiencia energética, hacen pertinente gestionarlos de forma eficiente para mejorar los tiempos de cómputo a la vez que el sistema trata de adaptarse a las nuevas restricciones del problema. Por otro lado, cada recurso disponible suele tener un consumo energético asociado y variable en función del tiempo durante el que se usa o de la potencia de trabajo asignada. En un contexto en el que requieren procesos cada vez más sostenibles, surge la necesidad de obtener soluciones energéticamente eficientes. Esto representa una línea novedosa en la resolución de problemas de scheduling llamada ¿Green Scheduling¿.

En este proyecto presentamos un modelo multiagente para la resolución de Green Scheduling offline en sistemas de fabricación de intenso consumo energético. En el modelo propuesto, los agentes, representando cada uno las distintas máquinas del entorno, deben colaborar para conseguir un acuerdo con la finalidad de obtener una solución multiobjetivo basada en minimizar 3 factores: el retraso total de los trabajos, el tiempo total de preparación (o configuración) entre tareas y el consumo total de energía que realiza la maquinaria. Posteriormente, a este sistema offline le integramos un segundo sistema online que monitoriza la ejecución del plan a la espera de que ocurran incidencias. En caso de que éstas ocurran, el módulo online realiza un rescheduling en tiempo real de la máquina afectada por la incidencia, redistribuyendo las tareas que tenía asignadas en caso de ser posible y tratando de minimizar el impacto que tiene la incidencia sobre los costes globales del entorno completo de fabricación.

Los sistemas desarrollados han sido evaluados sobre diversos casos de prueba y los resultandos obtenidos muestran la utilidad de las propuestas realizadas.