We consider the problem of computing optimal schedules in multi-agent systems. In these problems, actions of one agent can influence the actions of other agents, while the objective is to maximize the total 'quality' of the schedule. More specifically, we focus on multi-agent scheduling problems with time windows, hard and soft precedence relations, and a nonlinear objective function. We show how we can model and efficiently solve these problems with constraint programming technology. Elements of our proposed method include constraint-based reasoning, search strategies, problem decomposition, scheduling algorithms, and a linear programming relaxation. We present experimental results on realistic problem instances to display the different elements of the solution process.
Titolo: | Optimal multi-agent scheduling with constraint programming | |
Autore/i: | Willem Jan van Hoeve; Carla P. Gomes; Bart Selman; LOMBARDI, MICHELE | |
Autore/i Unibo: | ||
Anno: | 2007 | |
Titolo del libro: | PROCEEDINGS OF THE NINETEENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE | |
Pagina iniziale: | 1813 | |
Pagina finale: | 1818 | |
Abstract: | We consider the problem of computing optimal schedules in multi-agent systems. In these problems, actions of one agent can influence the actions of other agents, while the objective is to maximize the total 'quality' of the schedule. More specifically, we focus on multi-agent scheduling problems with time windows, hard and soft precedence relations, and a nonlinear objective function. We show how we can model and efficiently solve these problems with constraint programming technology. Elements of our proposed method include constraint-based reasoning, search strategies, problem decomposition, scheduling algorithms, and a linear programming relaxation. We present experimental results on realistic problem instances to display the different elements of the solution process. | |
Data prodotto definitivo in UGOV: | 4-dic-2014 | |
Appare nelle tipologie: | 4.01 Contributo in Atti di convegno |