Revue: | Computación y sistemas |
Base de datos: | PERIÓDICA |
Número de sistema: | 000383405 |
ISSN: | 1405-5546 |
Autores: | Ita Luna, Guillermo de1 Zacarias Flores, Fernando1 Altamirano Robles, L. Carlos1 |
Instituciones: | 1Benemérita Universidad Autónoma de Puebla, Departamento de Ciencias de la Computación, Puebla. México |
Año: | 2015 |
Periodo: | Ene-Mar |
Volumen: | 19 |
Número: | 1 |
Paginación: | 17-28 |
País: | México |
Idioma: | Inglés |
Tipo de documento: | Artículo |
Enfoque: | Analítico, descriptivo |
Resumen en inglés | The paper focuses on solving the Resource-Constrained Project Scheduling (RCPS) problem with a method based on intelligent agents. Parallelism for performing the tasks is allowed. Common and limited resources are available to all agents. The agents are non-cooperative and compete with each other for the use of common resources, thereby forming instances of RCPS problem. We analyze the global joint interaction of scheduling via a congestion network and seek to arrive at stable assignments of scheduling. For this class of network, stable assignments of scheduling correspond to a pure Nash equilibrium, and we show that in this case there is a guarantee of obtaining a pure Nash equilibrium in polynomial time complexity. The pure Nash equilibrium point for this congestion network will be a local optimum in the neighborhood structure of the projects, where no project can improve its completion time without negatively affecting the completion time of the total system. In our case, each state of the neighborhood represents an instance of the RCPS problem, and for solving such problem, we apply a novel greedy heuristic. It has a polynomial time complexity and works similar to the well-knowing heuristic NEH |
Disciplinas: | Ciencias de la computación |
Palabras clave: | Programación, Agentes inteligentes, Congestión de redes, Multicalendarización, Recursos limitados, Equilibrio puro de Nash |
Keyword: | Computer science, Programming, Intelligent agents, Network congestion, Multi-scheduling, Constrained resources, Pure Nash equilibrium |
Texte intégral: | Texto completo (Ver HTML) |