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