Multi-agent Learning by Trial and Error for Resource Leveling during Multi-Project (Re)scheduling

Abstract

In a multi-project context within enterprise networks, reaching feasible solutions to the (re)scheduling problem represents a major challenge, mainly when scarce resources are shared among projects. Thus, the multi-project (re)scheduling must achieve the most efficient possible resource usage without increasing the prescribed project constraints, considering the Resource Leveling Problem (RLP), whose objective is to level the consumption of resources shared in order to minimize their idle times and to avoid overallocation conflicts. In this work, a multi-agent solution that allows solving the Resource Constrained Multi-project Scheduling Problem (RCMPSP) and the Resource Investment Problem (RIP) is extended to incorporate indicators on agents’ payoff functions to address the Resource Leveling Problem in a decentralized and autonomous way, through decoupled rules based on Trial-and-Error approach. The proposed agent-based simulation model is tested through a set of project instances that vary in their structure, parameters, number of resources shared, etc. Results obtained are assessed through different scheduling goals, such as project total duration, project total cost and leveling resource usage. Our results are far better compared to the ones obtained with alternative approaches. This proposal shows that the interacting agents that implement decoupled learning rules find a solution which can be understood as a Nash equilibrium.

En un contexto de múltiples proyectos dentro de redes empresariales, alcanzar soluciones factibles al problema de (re)scheduling representa un gran desafío, principalmente al compartir recursos escasos entre proyectos. Así, el (re)scheduling de múltiples proyectos debe lograr el uso de recursos más eficiente posible sin incrementar las restricciones de proyecto planteadas, considerando el Problema de Nivelación de Recursos, cuyo objetivo es nivelar el consumo de recursos compartidos para minimizar tiempos ociosos y evitar conflictos de sobre-asignaciones. En este trabajo, una solución multi-agente para resolver el Problema de Scheduling de Múltiples Proyectos con Restricción de Recursos y el Problema de Inversión de Recursos es extendida para incorporar indicadores en las funciones de recompensa de los agentes para abordar el Problema de Nivelación de Recursos de manera autónoma y descentralizada a través de reglas desacopladas basadas en el enfoque de Aprendizaje por prueba y error. El Modelo de Simulación basado en agentes propuesto es verificado mediante un conjunto de instancias de proyecto que varían en estructura, parámetros, número de recursos compartidos, etc. Los resultados obtenidos se evalúan mediante diferentes objetivos de scheduling, como duración total del proyecto, costo total del proyecto y nivelación en el uso de recursos. Nuestros resultados presentan mejoras en comparación a los obtenidos en enfoques alternativos. Esta propuesta muestra que los agentes interactuantes que implementan reglas de aprendizaje desacopladas encuentran una solución que puede entenderse como un equilibrio de Nash.