Study On Modelling And Scheduling Algorithms For Outpatient Appointment Problems

With the economical and social development, the gradual impovement of residents’ social security system and health care system, diverse appointment approaches are provided by large hospitals. Common habit makes the patients flow overcrowded during some time of the day. If the patients are dispersed evenly in different intervals of the day, long waiting time can be mitigated. Booking appointments in different time intervals, constructing uniform platform for patients to search for the specialty of physicians and date on duty effectively reduce the blindness of patients and mitigate the congestion in the waiting room.A well designed appointment scheduling system determines the appointment time for each arrival in order to provide patients convenient access to medical care, smooth the patients flow, and matching the preference of patients and doctors. From the standpoint of operations research, the essence of appointment scheduling is matching patients’preference to physicians, time interval and the idle time of the clinic. Many practioners and researchers have designed optimization algorithms and developed decision support tools through IE/OR technique. Based on previous work, this dissertation provides decision method of reducing waiting time of patients and improving efficiency of the clinic simultaneously, designs the response mechanism to the difference of scheduled patients and actual arrivals, optimizes the procedure of appointment service.This dissertation focuses on the five key aspects:(1) Under the assumption of exponential distributed service time, a single server queueing model with no-show is built for traditional system, whose performance is compared with two kinds of open access system, same-day system and same-or-next-day system, when the expected workload is the same. For the traditional model, analytical solution is given for the two patients case, the numerical solution is derived by matlab for general case. Having analyzed the influences of no-golf policy, the day length, no-show probability, the expected workload and the relative overtime cost in numerical experiments, it is noted same-day policy outperforms traditional policy after some threshold, and same-or-next-day policy is always preferable except when the no-show probability is small and the weight of patients’waiting is low.(2) The schedule minimizing the total operational cost is found for appointment system serving both routine and urgent patients. For deterministic service time is, it is proved that all the urgent patients are scheduled before the routine patients, the optimal solution can be found by an implicit enumeration method. For exponential service time, it’s proved theoretically the local search algorithm based on multimodular function can’t guarantee optimality. Therefore, a heuristic algorithm with two shifting policies is proposed to find good solutions. Numerical results testify the effectiveness of the algorithm, and suggest reducing no-show probability, shrinking interval length, lowering average service time and adding the proportion of urgent patients benefit both patients and the clinic.(3) The joint capacity and scheduling problems for deterministic and exponential service time are modeled, maximizing the total utility defined as the system revenue minus the cost of waiting, idleness and overtime. It’s proved that the objective function is multimodular function when the waiting cost and overtime cost are monotonically increasing and convex function. Exact algorithms are developed to find the optimal number of scheduled patients and the corresponding schedule. Numerical experimets indicate the optimal schedule overbooks the first interval, no-show probability has a significant impact on the overbooking and system performances. Overbooking policy is preferable to mitigating the negative effect of no-show compared to allowing walk-in patients.(4) For a random generated sequence of appointment requests, two sequential scheduling algorithms are poposed to maximize the total profit minus the cost of waiting, idleness and overtime with and without fairness constraint, determing the optimal number of appointed patients and the assigned interval simultaneously. It’s proved the objective function without fairness constraint is unimodal function. Several properties are demonstrated to accelerate the search in each iteration. Patients’ preference increases the number of patients seen by the doctor but lower down the system profit. The cost of maintaining uniformity of patients’ waiting is low mean and large variance of the expected profit. Numerical results indicate lowering the proportion of patients with large no-show probability, compressing the interval length and reserving capacities for potential requests can increase the system profit.(5) For the sequential appointment scheduling problem with walk-in booking requests and without predetermined intervals, an algorithm is designed to find the optimal number of appointed patients and the arrival time scheduled, maximizing the total profit. After the proof that the cost function is convex, a sufficient condition that the objective function is unimodal is given. Numerical experiments testify the effectiveness of the algorithm, suggest reducing no-show probability and walk-in proportion can increase system profit and improve the efficiency, potential arrival is an alternative method to mitigate no-show.