A workforce management problem in service industries is to determine how to allocate employees to jobs such that the service demand can be satisfied as much as possible at minimum cost. It has been studied in the Operations Research, Genetic Algorithms and other areas. Recently, Constraint Logic Programming (CLP) has provided a declarative and powerful tool which has been successfully used to solve scheduling and resource allocation problems. In this paper, we present our experience in solving a real world application, a workforce management problem from British Telecom, by using this new technology. We propose a user-defined forward checking method to optimise the quality of solution. We also discuss some interesting heuristics. A workforce management system based on our approach has been implemented and tested on a set of real data. The work demonstrates that constraint techniques can easily be applied to solve real-world optimisation problems, and achieve reasonably good results.