Université de Montréal. École Polytechnique de Montréal. Montréal, Canada.
Title: Grammar-Based decomposition Methods for Multi-Activity Tour Scheduling Problems (MATSP)
My Ph.D. thesis is divided into three projects, each one introducing different modeling approaches to address several variants of the MATSP. In the first project, I present two branch-and-price algorithms to address the personalized MATSP when employee requirements are deterministic. Two formulations are introduced: a Daily-based formulation and a Tour-based formulation in which columns correspond to shifts and tours, respectively. A theoretical and experimental comparison of the two formulations showed that the Tour-based formulation is stronger in terms of its LP relaxation lower bound when compared with the Daily-based formulation. In the second project, I had the opportunity to do an internship at JDA software. There, I worked with the optimization team to implemented an approach that combines Benders decomposition and column generation to solve the anonymous MATSP under deterministic demand. This approach takes advantage of the special block structure of the problem to decompose it into smaller problems, easier to solve. Since Benders primal subproblems do not possess the integrality property, an alternative algorithmic strategy that combines the generation of integer Benders cuts with classical Benders cuts is proposed in order to guarantee the convergence of the method to an optimal solution to the original problem. Because alternative personnel scheduling approaches that include demand uncertainty can lead to significant reductions in labor cost, I decided to finish my thesis with the implementation of a heuristic multi-cut L-shaped method to solve the anonymous MATSP when demand is uncertain.
Universidad de los Andes. Bogotá, Colombia
Title: Multi-Activity Shift Scheduling Problem: a Column Generation Approach
My master's thesis addressed a personnel scheduling problem from a company that owns and operates over 140 parking lots in Bogotá, Colombia. The thesis is divided into two parts: the modeling of the behavior of the demand and the development of a heuristic approach to solve a shift scheduling problem where multiple activities had to be scheduled. The first part deals with the statistical analysis of the historical client-arrival data, in order to unveil the demand pattern over the planning horizon and to estimate, for each parking lot, the required number of employees at each time period. The second part includes the modeling and implementation of a heuristic column generation approach to generate the employee schedules over a one-week planning horizon.
Universidad de Antioquia. Medellín, Colombia