This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column Generation (ColGen) is thought to be the ideal approach to attack large-scale linear problems, it has been found that the textbook variety of ColGen algorithms are rather problematic during the Heading-in Phase. To alleviate the Heading-In Effect, and to start with good and valid lowerbounds, strategies for constructing the initial dual vector are provided, which is guaranteed to be feasible for the first Restricted Master Problem (RMP). Dual vectors obtained from RMP's at any iteration are further manipulated in order to prevent parallel and astray columns, which cause degeneracy and stalling. A subproblem selection scheme is also proposed to accelerate the convergence. The proposed techniques are thoroughly covered in the first two chapters of this thesis for the Workforce Planning with Cross-Training Problem and they provide superior results to CPLEX by being 10 times faster on average and having 20% better solution gap quality in the same amount of time.