We present a distributed CLP-based approach for solving a real workforce management problem (BT's DT-250-118). The problem consists of a set of jobs that we want to assign to engineers in order to serve as many of them as possible at a minimum cost. We first divide the problem into sub-problems and then assign each of them to a solving agent. Each agent works independently to solve its own sub-problem and then co-operates with its peers to optimize further the intermediate results. In the sub-problem solving stage, our agents use a CLP based approach which has been used in the past in a centralized, global way. Our method allows naturally distributed scheduling and resource allocation problems to be solved in a short time with minimal disruption to the quality of solutions when compared against global approaches.