Models And Algorithms For Outpatient Capacity Allocation And Appointment Scheduling

Outpatient appointment service is an advanced management method,which can arrange patients scientifically,make full use of the medical resources,and improve the efficiency of the outpatient system and satisfaction of both the doctor and patients.High patient demand,no-show probability and unpunctuality are challenges for outpatient departments in China.The utilization of medical resources becomes inadequate under uncertainties.How to add and allocate capacity scientifically and how to schedule patients with uncertain arrivals optimally are concerns of hospital managers and the whole society.Systematic researches of capacity-addition policy and optimization of unpunctuality appointment scheduling system received few attentions.The capacity-addition policy has been carried out in most of the hospitals in China.Managers consider adding some potential capacity beyond the regular daily capacity to meet demands and improve the profit.When all regular capacity is used and there are still requirements for appointments,the policy starts to work.There are two kinds of them:the fixed capacity-addition policy(F-CAP)and the variable capacity-addition policy(V-CAP).Under the F-CAP,the additional capacity is a constant,and under the V-CAP,it is a decision variable.The previous researches mainly use the case-study method and the results are lack of the theoretical formulation and optimization.In addition,the unpunctuality of patient arrival is a common phenomenon and inevitable in practice,which greatly affects the appointment system.The performances are not the optimal in the unpunctuality environment if using the scheduling determined under the assumption of strict-punctuality.The unpunctuality of patients has aroused only a few concerns,and most of them are studied in the simulation and case-study methods.It is difficult to formulate the analytical model and determine the global optimal solution.Therefore,determining the optimal solutions and providing management methods for the capacity-addition policy and the unpunctuality arrival are worth attentions.To deal with the challenges effectively,this paper studies the capacity allocation under the capacity-addition policy,and the scheduling considering the patient unpunctuality for the outpatient appointment system.The optimization is conducted for both interests of doctor and patient.Problems are formulated in stochastic programming models in the analytical method.This paper devotes to determining the global optimal solutions by proving properties of models and proposing the corresponding search algorithms.A large amount of numerical experiments are designed to analyze the results and summarize effective insights for hospital managers.The research is highly close to the practice.The content mainly includes the following four parts:(1)The research focuses on capacity allocation under the F-CAP.According to the reality,the diagram of the capacity allocation procedure facing the routine patients and the same-day patients is illustrated,and the cases of relationship between supply and demand are modeled.Firstly,this paper considers a basic environment,where demands of two types of patient are independent,and the no-show of same-day patient is not considered.The unimodality of expected profit function is proved and the condition for the optimal capacity allocation scheme is derived from the property of unimodality.Then a general environment is further studied.This paper formulates the expectation and variance models to reflect the matching degree and stability between supply and demand.This paper proposes a replacement rule to determine the outpatient capacity allocation scheme with high revenue and low variability.Experiments show that capacity allocation scheme is more sensitive to no-show under the condition of adding capacity.The replacement rule in this paper is effective to balance the expectation and the variance.(2)The research compares the F-CAP and the V-CAP.The V-CAP definitely achieves the optimal expected profit.Since the F-CAP is widely used in many first-class hospitals in practice,this paper attempts to explore in which situations the F-CAP can achieve a similar improvement of the V-CAP.We formulate linear integer programming models of F-CAP and V-CAP to maximize the expected profit.Several propositions and corollaries are proved to cut off the solution space and accelerate the search process.The optimal additional capacity can be directly determined by these properties.Numerical experiments indicate that the F-CAP is recommended to the environments with low no-show probabilities of routine patients and same-day patients,moderate expected total demand,correlation coefficient of demands and regular capacity,where the reduction of the expected profit is less than 5%between two policies.(3)The research focuses on capacity allocation under the V-CAP.The impact of the uncertainty of patient no-show on the overload is further incorporated.The overload is not directly calculated by the number of appointments beyond the regular capacity.The overload model is formulated as a piecewise function of the joint decision.In the basic environment,we prove that the expected profit monotonously decreases when the additional capacity exceeds a threshold.The property effectively cut off the solution space.Then a general environment is further studied.When consider same-day patients no-shows,the threshold-conditional unimodality alternates the monotonously decreasing property,and the expression of threshold is more complicated.A two-tier enumeration search algorithm is designed based on the proof.Numerical experiments indicate that the designed algorithm performs efficiently on solving the model.It is deserved to consider the no-shows when modeling and optimizing the overload.(4)The research focuses on appointment scheduling considering unpunctuality.6 cases that patients arrival order is different from their appointment order are summarized.It is illustrated that the model has an exact and unified formula for both cases of patients arriving in the appointment order or arriving out of order.This paper addresses the outpatient scheduling problem considering unpunctuality(OS-U)by developing a stochastic programming model.The OS-U problem is solved by a Benders decomposition combined with the sample average approximation(BD-SAA)technique so as to determine the global optimal set of appointment intervals.Numerical experiments indicate that the appointment rule changes if considering unpunctuality,though the set of optimal appointment intervals still presents like the shape of dome(interval width increases firstly,and then stays almost constant until it decreases for the last patients).The schedule requires a longer slot for the first patient if patients tend to arrive early rather than late.The no-show probability has greater influences on the system performances in an OS-U system than in an OS-P system.