Scheduling policies for multi-period services

Abstract

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.

En muchas situaciones los recursos en las organizaciones se usan para satisfacer requerimientos de demanda (o servicios) los cuales se repiten con cierta periodicidad. Estos servicios recurrentes aparecen en una gran variedad de procesos de manufactura, logística y varios otros tipos de servicios. Esta tesis aborda una familia de problemas en donde los recursos deben ser asignados para ofrecer servicios recurrentes sobre un horizonte de planeación. Estos problemas tienen ciertas características que los hacen distintos a los problemas típicos de calendarización encontrados en la literatura. Una de ellas es que los servicios son tareas de periodo unitario. Esto es, el tiempo necesario para comenzar y terminar un servicio nunca excede de un periodo de tiempo del horizonte de planeación. Además, en este tipo de problemas no enfocamos en determinar los periodos en los que cada servicio será repetido, en lugar de la secuenciación en que los diferentes servicios son ejecutados. En particular, nos concentramos en aspectos de modelización para los problemas de servicios recurrentes con duración de periodo simple así como en técnicas de resolución para encontrar soluciones eficientes. Hacemos particular énfasis en el estudio de la estrategia a seguir para ofrecer los servicios, esto es, la política de calendarización. Nuestro propósito es el análisis de distintas opciones para tales políticas. El objetivo es proveer soporte suficiente para los tomadores de decisiones en cuanto a la conveniencia de usar (o no) políticas flexibles como alternativa a estrategias regulares. Para ello estudiamos modelos alternativos para dos diferentes políticas de calendarización. Estos modelos se estudian desde una perspectiva de programación matemática y, por tanto, se presentan varias formulaciones de programación lineal mixta entera. En esta tesis desarrollamos dos tipos de formulaciones: el primer tipo puede verse como un acercamiento natural al problema y produce matrices con coeficientes dispersos mientras que el segundo tipo se enfoca en determinar el primer periodo de servicio para cada cliente y da como resultado matrices densas. Para cada tipo de formulación presentamos dos versiones: una extensa y una compacta. En la primera, las variables de decisión están asociadas a clientes individuales mientras que en la segunda, las variables de decisión se asocian con clases de clientes con características similares. Para la política regular desarrollamos formulaciones de las dos versiones mientras que para la política flexible únicamente estudiamos formulaciones extensas. Las formulaciones para cada política son comparadas por medio de una amplia experiencia computacional. Debido a que la política flexible resulta más difícil de resolver que la regular, usamos técnicas de optimización combinatoria que permiten métodos alternativos de solución. En particular, proponemos dos formulaciones distintas, ambas adecuadas para generación de columnas (GC). Para cada formulación estudiamos el subproblema de pricing para generar nuevas columnas, la fase de inicialización así como un procedimiento para atacar temas de infactibilidad. Además, aplicamos procedimientos de estabilización con el objetivo de evitar la generación de un número excesivo de columnas. Cada algoritmo de GC ha sido incrustado dentro de una estructura de branch-and-price (BP), el cual combina diferentes estrategias de ramificación. El BP ha sido implementado para cada formulación de GC produciendo resultados interesantes los cuales presentamos y analizamos. En este trabajo también proponemos un algoritmo heurístico adaptable para ambas políticas de calendarización. Las heurísticas producen soluciones de buena calidad para los problemas estudiados, especialmente para la política flexible. Finalmente, la estructura de las soluciones obtenidas con ambas políticas se analizan, obteniendo ideas importantes en cuanto a la compensación entre las políticas regulares y las flexibles.