Minimizing average project team size given multi-skilled workers with heterogeneous skill levels

• The task of assigning multi-skilled workers to concurrent projects is considered.
• We present a mixed-integer linear program that aims at forming small project teams.
• We outline valid inequalities that support a commercial branch-and-cut solver.
• We prove that the problem is strongly NP-hard and devise three heuristics.
• A computational analysis reveals the heuristic that performs best.

Many firms face the challenging task of staffing concurrent projects such that the skill requirements of each project can be satisfied by the respective team of workers. We consider a staffing problem where each worker can be assigned to several projects at a time. A high total number of assignments implies large project teams and scattering of workers across projects. Large teams come along with productivity losses due to increased coordination effort and social loafing while scattering incurs losses due to frequent switching between projects. To curb these inefficiencies, we formulate a mixed-integer linear program that minimizes average project team size and, thus, scattering. The program accounts for multi-skilled workers with heterogeneous skill levels who must also fulfill duties within their departments. We prove that the problem is NP-hard in the strong sense and outline valid inequalities that accelerate the solution by a commercial branch-and-cut solver. For large-scale instances, we devise three construction heuristics, each of which is embedded in a multi-pass procedure. Our performance analysis reveals that a heuristic based on the drop principle offers the best compromise between solution quality and computation time. Limitations of the proposed approach, managerial insights, and areas of application are discussed.