Scheduling problems in the service industry : theory and applications

Scheduling problems belong to the classical optimization problems in operations research due to their practical significance and theoretical elegance. This thesis focuses on both the theory and applications of scheduling and contributes new methodologies and insights in both aspects. With this aim, four scheduling problems from different research areas have been considered in this thesis:

- The Budgeted Job Coverage Problem (BJCP), where the goal is to find a set of subsets, over a set of jobs with costs and weights, that maximizes the total weight while not exceeding a budget, - The European Crew Scheduling Problem (ECSP), where the goal is to assign trips with fixed departure and arrival times to bus drivers, while fulfilling constraints on driving, resting and duty times that apply to bus drivers in the European Union,

- The Room and Ward Planning Problem (RWPP), where the goal is integrate the planning of patients on operating rooms and wards in a stochastic setting (i.e., uncertain number of available patients, procedure times and hospitalization times), subject to a variety of constraints on the procedures, rooms and wards, and - The Periodic Event Scheduling Problem (PESP), where the goal is to schedule a given set of events to times within a cyclic framework, subject to constraints that impose bounds on the time difference of pairs of events. For all four problems is proven in this thesis that the problem is NP-hard, meaning that it is unlikely that an algorithm exists that can solve the problem efficiently. For this reason, alternative approaches are required that are proposed for (special cases of) every scheduling problem. These methods include graph algorithms (BJCP, ECSP, PESP), (mixed) integer linear programming (ECSP, RWPP, PESP), approximation algorithms (BJCP), fully polynomial time approximation schemes (BJCP), dynamic programming (BJCP, ECSP, PESP), column generation (ECSP) and heuristics (ECSP, RWPP, PESP). First, algorithms are proposed to solve special cases efficiently. Subsequently, it will be argued how these algorithms can be used a subroutine to solve the main problem, which usually comes with an exponential running time. In case heuristics are used, the analyses also include computational experiments and results that are based on online benchmarks, real-world datasets and/or extensive case studies, with varying results. Even though the algorithms may be too time-consuming for large instances, the algorithms has shown adequate results and reasonable running times for small and medium-sized instances.Scheduling problems belong to the classical optimization problems in operations research due to their practical significance and theoretical elegance. This thesis focuses on both the theory and applications of scheduling and contributes new methodologies and insights in both aspects. With this aim, four scheduling problems from different research areas have been considered in this thesis: - The Budgeted Job Coverage Problem (BJCP), where the goal is to find a set of subsets, over a set of jobs with costs and weights, that maximizes the total weight while not exceeding a budget,

- The European Crew Scheduling Problem (ECSP), where the goal is to assign trips with fixed departure and arrival times to bus drivers, while fulfilling constraints on driving, resting and duty times that apply to bus drivers in the European Union,

- The Room and Ward Planning Problem (RWPP), where the goal is integrate the planning of patients on operating rooms and wards in a stochastic setting (i.e., uncertain number of available patients, procedure times and hospitalization times), subject to a variety of constraints on the procedures, rooms and wards, and - The Periodic Event Scheduling Problem (PESP), where the goal is to schedule a given set of events to times within a cyclic framework, subject to constraints that impose bounds on the time difference of pairs of events. For all four problems is proven in this thesis that the problem is NP-hard, meaning that it is unlikely that an algorithm exists that can solve the problem efficiently. For this reason, alternative approaches are required that are proposed for (special cases of) every scheduling problem. These methods include graph algorithms (BJCP, ECSP, PESP), (mixed) integer linear programming (ECSP, RWPP, PESP), approximation algorithms (BJCP), fully polynomial time approximation schemes (BJCP), dynamic programming (BJCP, ECSP, PESP), column generation (ECSP) and heuristics (ECSP, RWPP, PESP). First, algorithms are proposed to solve special cases efficiently. Subsequently, it will be argued how these algorithms can be used a subroutine to solve the main problem, which usually comes with an exponential running time. In case heuristics are used, the analyses also include computational experiments and results that are based on online benchmarks, real-world datasets and/or extensive case studies, with varying results. Even though the algorithms may be too time-consuming for large instances, the algorithms has shown adequate results and reasonable running times for small and medium-sized instances.