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.

Optimal multi-agent scheduling with constraint programming

LOMBARDI, MICHELE
2007

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.
PROCEEDINGS OF THE NINETEENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE
1813
1818
Willem Jan van Hoeve; Carla P. Gomes; Bart Selman; Michele Lombardi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/390360
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact