Modeling and Solution Approaches for Resource Assignment with Deployment Restrictions

Since personnel and equipment costs constitute a large portion of the operating expenses for most organizations, judiciously using these resources to perform the organization’s activities is important to ensure cost-effective operations. This paper addresses a class of resource management problems that entail assigning resources to perform a given set of ordered tasks while meeting policies and restrictions governing the deployment of these resources. We consider two particular kinds of restrictions, called span limits and work content restrictions, that specify upper and lower limits on pairwise and cumulative metrics based on the tasks assigned to each resource. We refer to this problem as the Resource Assignment with Deployment Restrictions (RADR) problem. We discuss several alternative ways to model the problem as a network-based integer program, and contrast these models in terms of the tightness of their linear programming relaxations and model size. This discussion serves to highlight the benefits of developing extended formulations and embedding constraints within the network representation, underscoring the importance of using strong formulations to effectively solve integer programs such as the RADR problems. We also outline three additional strategies—problem reduction, tightening the model with valid inequalities and coefficient lifting, and optimization-based heuristics—to further accelerate solution procedures for the RADR problem. Results from a prior study confirm the computational benefits of incorporating these strategies jointly in the solution method.