This paper presents a model and procedure for determining crew composition for a new technology like the Navy’s DDX. Here the prototype DDX manpower scheduling problem is modeled as a project scheduling problem with multi-purpose resources (PSMPR) where multi-skilled sailors form teams to accomplish interrelated onboard tasks. A hybrid decomposition algorithm that incorporates constraint programming (CP) and a tabu search (TS) metaheuristic is developed for solving this NP-hard problem. In computational experiments, the performance of our hybrid algorithm is tested and compared with solutions found using mixed-integer linear programming (MILP) with CPLEX and with lower bounds obtained from a bin packing problem with conflicts (BPC).