Optimization Models For Appointment Scheduling Under Patients' Behaviors

This thesis studies several optimization models of outpatient scheduling,in which incorporate patients' behaviors,like walk-ins,no shows and patients' preference so on.Specifically,we consider the following problems from both theoretical and practical perspective:First,prior studies on appointment scheduling reported that the optimal schedule has a“dome”shape when the service durations are i.i.d.In order to analyze the theoretical performance of“dome”shape like policy,we study a simple but effective scheduling policy-the so called plateau policy for the appointment systems,which allocates a constant job allowance for each appointment.Under the i.i.d.service time setting,we derive an explicit upper bound for the performance gap between the plateau policy and the optimal schedule,and prove that there exists a plateau policy which is asymptotically optimal when the number of appointments grows to infinity.We extend this result to a more general setting in which the service durations have different distributions for appointments in different time blocks of a day,and prove that in that case a piecewise plateau policy is asymptotic optimal.Second,we consider a general appointment scheduling problem in the presence of walk-ins.For this kind of scheduling problem,we separate the potential walk-ins and scheduled patients into two different groups.On this basis,we first formulate that problem as a two-agent optimization model with two different performance regimes.Then we introduce a series of chance constraints to make a trade-off between walk-ins' waiting time and the service level.When we do not consider no-shows,we derive the no-hole property of the optimal schedule under a mild condition.Then we exploit SAA-based method to reformulate our problem as a mixed integer linear program(MILP).In the presence of no-shows,some Symmetry-Breaking constraints are introduced to the corresponding MILP to solve the problem more efficiently.Finally,we observe the common phenomenon in Chinese hospitals that the number of walk-ins dominates that of patients who make appointments in advance,which is quite different from western countries such as United States and Canada.Motivated by this phenomenon,we consider an appointment scheduling problem with two types of patients,the scheduled patients and walk-in patients.Each patient has preference on the service time windows captured by the Multinomial Logit(MNL)Model.The objective of the problem is to maximize the total reward from the serviced patients less the total costs of patients waiting.We consider two cases when a walk-in patient is in service: the service of the walk-in patient can be preempted by arrival of a scheduled patient,and the service of a walk-in patient cannot be preempted by arrival of a scheduled patient.For the preemptive case,we study structural properties of optimal policy and formulate the problem as a Second Order Cone Program(SOCP).For the non-preemptive case,we employ dynamic programming with constraints of knapsack structure to solve the problem,and develop a heuristic to solve the problem as well.