Optimal Multi-Agent Scheduling with Constraint Programming

Willem-Jan van Hoeve, Carla P. Gomes, Michele Lombardi, Bart Selman

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.

Subjects: 7.1 Multi-Agent Systems; 15.2 Constraint Satisfaction

Submitted: Apr 2, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.