Solving scheduling problems using parallel message-passing based constraint programming

Abstract

We discuss some of the engineering challenges in implementing a constraint programming based scheduling engine to scale well on massively parallel computer hardware. In particular, we have been targeting our solvers to work in high performance computer environments such as the IBM Blue-Gene/P supercomputer. On such hardware parallelism is enabled at the software level using message passing, based on the MPI standard. We investigate a parallelization scheme based on a dynamic decomposition and reallocation of the search space during search. We present initial results of our research showing good scaling behaviour on challenging resource-constrained project scheduling problems up to 1024 processors on the IBM BlueGene/P supercomputer. © 2009, Association for the Advancement of Artificial Intelligence.