Scheduling policies for multi-period services

Resumen

In many situations, the resources in organizations are employed to satisfy some demand (or services) requirements, which are repeated with some periodicity. These recurrent services appear in a large variety of processes such as manufacturing, logistics and several other types of services. In this thesis, we focus on a particular family of problems involving the planning of recurrent services. In these problems resources are assigned to offer recurrent services over a planning horizon. Even if these problems can be classified as scheduling problems, this specific characteristic makes them differ from the typical scheduling problems studied in the literature. A very special characteristic of the problems that we study is that services are considered as single-period tasks. That is, the time needed to start and complete a service never exceeds one time period of the planning horizon. Furthermore, we focus on identifying the single periods when each service is repeated within the time horizon, instead of on the sequence according to which the different services are executed along the time horizon. We concentrate on modelling aspects for recurrent service problems with single-period duration,and on solution techniques for efficiently finding solutions. Particular emphasis is placed on the study of the strategy that is followed to offer the services over the planning horizon, that is, the policy for scheduling. Our aim is to analyze different options for such scheduling policies.The purpose is to provide enough support to decision makers to determine the convenience of using (or not) flexible policies as an alternative to regular strategies.For this, we study alternative models for two different scheduling policies. These models are addressed from a mathematical programming point of view and, therefore, we present several Mixed Integer Linear Programming (MILP) formulations. We develop two different types of formulations: the first type can be seen as a natural initial approach to the problem and produces sparse coefficients matrices whereas the second type is focused on determining the very first service period for each customer and gives dense matrices. For each type of formulation, we present two versions: an extensive and a compact one. In the first one decision variables are associated with individual demand customers whereas in the second one decision variables are associated with classes of customers with similar characteristics. For the regular policy we develop the both types of formulations whereas for the flexible policy we only study the extensive formulation. The formulations for each policy are compared trough extensive computational experience. Since the flexible policy results harder to solve than the regular one, we make use of combinatorial optimization techniques that permit alternative solution methods.In particular, we propose two different formulations suitable for column generation (CG).For each formulation we study the pricing subproblem that allows generating new columns, the initialization phase, as well as a procedure to tackle infeasibility issues. Additionally, we apply stabilization procedures in order to avoid the generation of an excessive of columns. Each CG algorithm is embedded within a branch-and-price (BP) framework, which combines different branching strategies. The BP was implemented for each CG formulation producing very interesting results that we present and analyze. Heuristics are alternative combinatorial optimization techniques that provide optimal and near optimal values within small computational times. In this thesis we also propose a heuristic algorithm suitable for both of scheduling policies.The heuristic produces good quality solutions for the studied problems, specially for the flexible policy. Finally, the structure of the solutions obtained with both scheduling policies are analyzed giving important insights on the trade-off between the regular and the flexible policies.