A global constraint model for integrated routeing and scheduling on a transmission network

Abstract

This paper presents a novel approach to planning the sending of messages along a meshed transmission network with limited bandwidth paths. The approach allows determining the topological route-ing of messages and a feasible time schedule satisfying three basic constraints: maximum bandwidth capacity per path, integrity of packages and maximum receiving time for each message. Constraint Logic Programming (CLP) is used to solve the combined problem of routeing and scheduling in an integrated mariner. To this end, a finite-domain model with global constraints has been derived for a generic transmission network. The model implementation, in the CLP language CHIP, is explained in detail. An implementation has been run on extensive test cases, showing the efficiency of this approach.