Augmented patterns for decomposition of scheduling and assignment problems

Scheduling and assignment are relevant decisions widespread in complex organizations that produce goods or deliver services. Industrial companies and service providers periodically make these decisions that take into account their specific context in terms of objectives and constraints. As a consequence, a multitude of mathematical models for solving specific scheduling and assignment problems have been investigated in the literature. This paper tackles the problem differently by proposing a general two-phase decomposition framework in which the first phase grasps the key elements of the problem, while the second phase customizes the solution to the specific application addressed. Both phases are based on a mathematical model. The first model considers a set of kernel constraints and generates a set of patterns that link scheduling to assignment decisions. This model is flexible in the criteria used to generate the patterns and considers the finite and heterogeneous capacity of the critical resources to schedule and assign. The second model benefits from the patterns identified by the first phase, that reduce the solution space; this reduction is fundamental because the second model considers all the problem features. To show the generality of the approach, the methodology was applied in diverse application contexts by formulating the augmented pattern generation model with objective functions and constraints custom to the application context. Computational results, obtained from a pool of small to large instances generated from a case study in the Home Care sector, are also presented.