Abstract

Scheduling is one of the important components of operation management in different services. The goal of scheduling is to allocate limited available resources over time for performing a set of activities such that one or more objectives are optimized. In this thesis, we study several interesting applications of scheduling in health care and logistics. We present several formulations and algorithms to efficiently solve the scheduling problems that arise in these areas.

We first study static and dynamic variants of a multi-appointment, multi-stage outpatient scheduling problem that arises in oncology clinics offering chemotherapy treatments. We present two integer programming formulations that integrate numerous scheduling decisions, features, and objectives of a major outpatient cancer treatment clinic in Canada. We also develop integrated and sequential scheduling strategies for the dynamic case in which arriving requests are processed at specific points of time.
The results of computational experiments show that the proposed scheduling strategies can achieve significant improvements with respect to the several performance measures compared to the current scheduling procedure used at the clinic.

We next present a daily outpatient appointment scheduling problem that simultaneously determines the start times of consultation and chemotherapy treatment appointments for different types of patients in an oncology clinic under uncertain treatment times. We formulate this stochastic problem using two two-stage stochastic programming models. We also propose a sample average approximation algorithm to obtain high quality feasible solutions. We use an efficient specialized algorithm that quickly evaluates any given first-stage solution for a large number of scenarios. We perform several computational experiments to compare the performance of proposed two-stage stochastic programming models. In the next part of the experiments, we show that the quality of the first-stage solutions obtained by the sample average approximation is significantly higher than those of the expected value problem, and the value of stochastic solution is extremely high specially for higher degrees of uncertainty.

Finally, we address two variants of a cross-dock scheduling problem with handling times that simultaneously determines dock-door assignments and the scheduling of the trucks. In the general variant of the problem we assume that unit-load transfer times are door dependent, whereas in the specific case variant, unit-load transfer times are considered to be identical for all pairs of doors. We present constraint programming formulations for both variants of the problem, and we compare the performance of these models with mixed integer programming models from the literature. For the specific case, we propose several families of valid inequalities that are then used within a branch-and-cut framework to improve the performance of a time-index model. To solve the general problem efficiently, we also develop an approximate algorithm that first solves the specific case problem with the developed branch-and-cut algorithm to obtain a valid lower-bound, and then applies a matheuristic to obtain a valid upper-bound for the general problem and to compute the optimality gap. According to the computational experiments, we show that the proposed formulations and algorithms are able to solve the studied problems efficiently, and they outperform other models and heuristics that were previously developed for the problem in the literature.