Resource allocation problems in queueing systems are notoriously nonlinear and it is often the case that when there exists no closed form solution, we rely on heuristics to find good solutions. In this paper, we look at a front-room/back-room workforce allocation problem and demonstrate how constraint programming and problem decomposition techniques can be used to find provably optimal solutions. The main techniques used in Constraint Programming and Logic-based Benders Decomposition will be introduced along the way. This is joint work with Daria Terekhov, Tony Tran, and Doug Down.