Abstract

Appointment Scheduling is an increasingly challenging problem for service-centers, healthcare, production and transportation sector. Challenges include meeting growing demand and high expectation of service level among the customers and ensuring an efficient service system which reduces the expenditure related to idle times and underutilization of the system. The problem becomes more complicated in the presence of processing time uncertainty, varying from customer to customer. In this regard, Appointment Scheduling can improve the system efficiency drastically and significant savings can be achieved. Specially, in developed countries where expenditures are huge for service centres, a good appointment schedule is crucial.

In this study, a Robust Appointment Scheduling model is developed using Min-max Optimization to provide appointment dates for jobs which will be processed sequentially with a highly utilized single processor. When a job finishes earlier than the next job’s appointment date, the processor and the associated recourses remain idle until the next job’s appointment time resulting in underutilization of the system. Whereas if a job takes more time than assigned, the system experiences overage cost due to the waiting of the next jobs. Therefore, an optimal appointment schedule is required considering the trade-off between the underutilization and overtime of both the processor and the jobs. Our objective is to minimize the worst cost of the appointment schedule by minimizing earliness and tardiness of both the jobs and the processor for any realization of the processing durations.

The proposed methodology requires less information regarding the uncertain parameters and can provide optimal solution while only considering the extreme values of the uncertain processing durations. Hence, scenario realization and computational effort for the robust model have reduced to a great extent without loss of optimality compared to other modelling approaches. The robust model does not require to assign probabilities to the future uncertain instances and is therefore applicable to any probability distribution of the uncertain parameters.

At first a Non-linear Robust Appointment Scheduling model is developed. To remove the nonlinearity, a Mixed Integer Linear Programming model is proposed. Since the proposed Robust Appointment Scheduling model is NP- hard, an Iterative Search Procedure is provided for solving the lager instances of the problem in polynomial time. The objective of the Iterative Search Procedure is to selectively choose the scenarios that incur worst cost and then optimizing among those scenarios to provide an appointment schedule that will work well for all other scenarios. For finding the worst case scenario, a Dynamic Programming model is proposed which allows to find the worst case scenario among all the scenarios in  time. Propositions that support the robust model are provided along with their theoretical proofs. Appointment scheduling of two case studies, a Dentist’s clinic and VIA Rail Canada, are performed. Both case studies exhibit high performance of the proposed robust model in terms of cost savings and computational efforts. This work will contribute both to the literature related to uncertainty handling in decision making and to the industries, which aim to achieve an efficient service system.