Optimal Multi-Agent Scheduling with Constraint Programming

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 study 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.

This is joint work with Carla P. Gomes (Cornell U.), Michele Lombardi (U. Bologna), and Bart Selman (Cornell U.).

Speaker Bio

Willem-Jan van Hoeve is Assistant Professor of Operations Research in the Tepper School of Business of Carnegie Mellon University. Prior to this, he was a postdoctoral associate in the Department of Computer Science of Cornell University. His main research interests are combinatorial optimization, constraint programming, and the integration of operations research methods and constraint programming.