Work allocation planning is a vital and notoriously difficult task in areas characterized by large work forces, contiguous and sometimes overlapping shifts, regulatory and corporate constraints, and tightly managed work force establishments. In the allocation of nurses to ward shifts, forward planning is widely acknowledged to be essential, but the majority of efforts in this highly constrained area rely on manual techniques. Health service policy is being driven increasingly towards maximum efficiency and accountability, resulting in the need for more accurate long-term planning. This paper discusses an approach to this problem, using a strategy of distributing and devolving the computational effort required. In the pre-processing stage, the staff to be rostered are treated as semi-autonomous agents, each with individual responsibility for their initial assignment, and communication with a global constraint solving (CLP) agent. This has proved to be intuitive to build and effective in use.