Dynamic Patient Scheduling for a Diagnostic Resource by Jonathan Patrick B.Arts & Sc. McMaster University 1997 M.Sc. The University of British Columbia 1999 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF DOCTOR OF PHILOSOPHY in T H E FACULTY OF G R A D U A T E STUDIES (Business Administration) T H E UNIVERSITY OF BRITISH COLUMBIA October 2006 ©Jonathan Patrick, 2006 Abstract We take an in-depth look at the scheduling of patients for a diagnostic resource. Our aim is to schedule patients in order to maintain reasonable waiting times for minimal cost. We assume a fixed capacity with stochastic demand coming from multiple priority classes. We further assume that it is the lower priority patients that must be booked first, therefore requiring the resource manager to implement a booking policy to assure room for later arriving higher priority patients. If too much capacity is reserved for higher priority patients then there will inevitably be unused capacity resulting in longer waiting times than might otherwise be the case. If not enough capacity is reserved then higher priority patients will have to be served through overtime or forced to wait longer than recommended. We begin, in Chapter 1, with an international overview of efforts to reduce waiting times. Chapter 2 proposes a scheduling policy assuming only two priority classes and a fixed limit on expected overtime. The higher priority class are inpatients who must be served the day the demand for a scan is placed. The lower priority class consists of outpatients who may be booked weeks in advance. We present a model that gives the optimal reservation policy and examine the benefit of introducing some flexibility into the higher priority (inpatient) class. Chapter 3 then restricts the modeling to outpatients where demand is divided into multiple priority classes. We present a Markov Decision Process that we solve through approximate dynamic programming in order to derive an approximately optimal booking policy that maintains reasonable waiting times for minimal cost. ii Chapter 4 presents some strong theoretical results as to the nature of the optimal policy from chapter 3 as well as providing bounds on the "deviation from optimality" associated with our approximation. Chapter 5 then adds inpatients to the model in chapter. 3 and compares the results of the full model to those given in chapter 2. Finally, we conclude with possible enhancements to the model and policy insights for the resource manager. iii Contents Abstract ii Contents iv List of Tables vii List of Figures viii Acknowledgements ix Dedication x Chapter 1. Meeting the Waiting Time Challenge 1 1. The Challenge 1 2. Limiting Demand 5 3. Increasing Capacity 10 4. Improved Efficiency 12 5. The Impact of Scheduling on Waiting Times 16 6. Diagnostic Imaging 18 7. Related Literature in Operations Research 19 Chapter 2. Improving Resource Utilization through Inpatient Scheduling . . 25 1. Introduction 25 2. The Problem 25 3. The Proposed Scheduling Approach 27 iv 4. Is The Proposed System Practical? 31 5. Choosing L and H 33 6. What Improvement Can We Expect? 37 7. The Simulation Model 38 8. Implementation Challenges 51 9. Conclusion 53 Chapter 3. Dynamic Multi-Priority Patient Scheduling with Uncertain Demand 55 1. Introduction 55 2. The Model . 55 3. The Form of the Optimal Approximate Value Function 67 4. Simulation Results 74 5. Conclusion 83 Chapter 4. The Optimal Approximation and Bounding the Optimality Gap . 86 1. Introduction 86 2. The Form of the Optimal Policy with Overtime 86 3. The Form of the Optimal Policy with Demand Rejection 96 4. How Good is the Approximation? 102 5. Conclusion I l l Chapter 5. Comparing Models 112 1. Introduction 112 2. Extending the M D P to include Inpatients 113 Chapter 6. Further Enhancements and Policy Recommendations 118 1. Further Enhancements 118 2. Policy Insights 127 Bibliography 130 vi List of Tables 2.1 Illustrative IP Demand Data for One Week 30 2.2 Performance of the Proposed Policy (H = 65, L = 10) 31 2.3 Performance for the Policy (H = 75, L = 0) 31 2.4 Simulation Results (mean with 95% confidence limits) 41 2.5 Effect of OT Limit on Capacity Usage 44 2.6 Multiple Exam Lengths Comparison 48 2.7 Stochastic Service Times 51 3.1 A Comparison of Three Scheduling Policies 78 3.2 Optimal Approximation Policy with Increasing Rejection Costs 78 3.3 Impact of the Overtime Policy 80 3.4 Capacity of 30 Scans per Day 82 5.1 The Impact of LIP on a Small Sized Hospital 114 5.2 A Larger Hospital 115 5.3 Mirroring Chapter 2 Simulation 116 vii List of Figures 2.1 Daily Weekday IP Demand for V G H (May-December 2003) 36 2.2 Constrained Policy vs Current Practice (Simulation standard error of 0.01) . . . 43 2.3 Varying IP Arrival Rate (Simulation standard error of 0.01) 46 2.4 Varying Capacity (Simulation standard error of 0.01) 47 2.5 Varying Percentage of OP On Call (Simulation standard error of 0.01) 49 3.1 Waiting Time With Rejection by Priority Class 76 3.2 Waiting Time With Overtime by Priority Class 81 3.3 Average Cost for a Variety of Demand Streams 83 5.1 Average Number of Daily OT Scans as a Function of Capacity 117 viii Acknowledgements First and foremost, let me thank my supervisor Dr. Martin Puterman whose unwavering encouragement and insightful direction have truly been all that I could have asked for. I only hope to one day give the same level of supervision to my own graduate students. Secondly, the two other members of my committee, Dr. Maurice Queyranne and Dr. Michael Friedlander, have both given of their time to insure that this thesis did, in fact, reach completion. Dr. Queyranne was especially helpful in insuring that the proofs in chapter 4 were complete and coherent. Thirdly, the timely visit of Dr. Dan Adelman to Vancouver was pivotal in giving this research momentum. I am very much indebted both for his initial help and his continued advice along the way. Fourthly, it would be remiss not to mention Elaine Cho who has guided this administratively challenged student through the numerous pitfalls of a university bureaucracy - all with unwavering good will. I am sure at times she was tempted to roll her eyes at my incompetence! Finally, no PhD student can underestimate the importance of his fellow students. In particular let me thank Jeffrey Colpitts, Benny Mantin, Frederik Odegaard and Anita Parkinson who helped assure me that my own thesis struggles were not unusual!-ix Dedication I dedicate this work to my wife, Jennifer, and my children, Rhys and Corwin, who have endured with great patience, providing encouragement to my sometimes lagging spirits, while I have struggled to complete this PhD. Thank you somehow doesn't seem adequate! Nonetheless, thank you for your patience and your support and may God continue to direct our steps together. "In His will, our peace". C H A P T E R 1 Meeting the Waiting Time Challenge 1. The Challenge A middle-aged man reports to his doctor complaining of mild but persistent headaches and some hearing loss in one ear. His doctor recommends he visit a spe-cialist and books him for an appointment in one month. On seeing the specialist, an M R I is recommended but cannot be performed for two weeks. Upon analysis, it is shown that he has a tumour growing on the right side of his brain requiring surgery. Two weeks later, the surgery is performed but turns out to be significantly more diffi-cult than expected due to the size of the tumour. The patient survives the operation but is now paralyzed on one side of his face and has lost all hearing in one ear. The question that keeps recurring to him is this - what would have been the outcome if the surgery had been performed two months earlier? The above story is, of course, anecdotal but not unusual. Nor is the challenge of potentially damaging wait times unique to brain surgery. A Brit ish article reported that an elderly patient waited 28 hours for treatment at an emergency center [29] while in Saskatchewan, waiting time for a magnetic resonance imaging (MRI) scan reportedly reached 22 months [19]. A recent case in Canada concerned an eighteen month girl who over several weeks suffered severe pain, her limbs swelling to the point that she could not walk. A bone scan was deemed necessary but there remained a three week wait for the M R I . Her parents drove her out of province where she was finally diagnosed with leukemia [42]. l On top of this growing list of tragic stories there are now numerous studies that demonstrate alarmingly long and growing waiting lists in a variety of O E C D countries. Australia, Canada, Denmark, Finland, Ireland, Italy, Netherlands, New Zealand, Nor-way, Spain, Sweden and the U K have all reported significant waiting time challenges within their health care systems [51]. A 2002 report stated that 38% of patients wait at least four months for elective surgery in the U K , 27% in Canada, 26% in New Zealand and 23% in Australia [27]. A 1995 study showed that 89% of patients waited more than 3 months for cardiovascular procedures in the U K , 47% in Canada and 18% in Sweden [8]. The excessive nature of these waiting times is highlighted by a Canadian study that surveyed physicians across the provinces and across specialties. Each physician was asked to give both the length of time a patient should expect to wait for treatment as well as their own assessment as to what would be the maximum recommended waiting time. In 88% of the cases (each case representing a different specialty and province), the expected waiting time was significantly longer [20]. The same study suggested that overall average waiting time was 92% higher in 2004 than it was in 1993. In a separate study, 19% of patients who were surveyed after having visited a specialist reported having been adversely affected by the length of the wait-ing time [47]. Both these studies face the obvious criticism that they are based on surveys and not concrete waiting time data but they nonetheless highlight the fact that, in the opinion of both the professionals in the system and the patients using it, waiting times within Canada at least, have reach unacceptable levels. The erosion of public confidence in the Canadian health care system is highly correlated with this apparent increase in waiting time over the last decade and a half. In 1991, 61% of Canadians ranked the health care system as "excellent" or 2 "very good". B y 1995 this number had dropped to 52% and by 1999 it was as low as 24% [46]. Even more recently, a 2006 Statistics Canada survey reported that waiting times were the number one health care barrier for those have difficulty gaining access to the health care system [21]. The importance placed on the expected waiting time for treatment as a measure of the well-being of our health care system was raised by Romanow in his influential report on the future of health care in Canada in 2002. In his estimation, "long waiting times are the main, and in many cases, the only reason some Canadians say they would be willing to pay for treatments outside of the public health care system" [45]. While there is almost universal agreement on the necessity of reducing these wait-ing times, there is little consensus as to the most appropriate means of doing so. One of the obstacles to coming to any agreement is that data on waiting times for hospital procedures are notoriously difficult to obtain and analyze. One challenge is the paucity of reliable data making it difficult even to know the extent of the current challenge. A second is that there is no agreed upon standard of what constitutes the official definition of "waiting time" making comparisons difficult. While the end date of the waiting time period is clear (the day of the treatment or diagnostic test), there are at least three potential candidates for the start date: (1) The initial visit to the family doctor, (2) The initial visit to the specialist who recommends treatment or, (3) The date the request for treatment is placed. While it may be reasonable to assume that the latter two are not significantly differ-ent, there is plenty of evidence that the time between the initial visit to the family doctor and the visit to the specialist can differ substantially [20]. From the patient's 3 perspective, total waiting time clearly includes the initial wait between the family doctor visit and the specialist visit. However, this data is rarely available for analysis and thus much of the reported waiting times actually represent the third option -from the day the request for treatment is placed to the day of treatment. Moreover, there is some logic to breaking total waiting time down into the two parts (family doctor to specialist and specialist to treatment) as the causes and potential responses to the waiting time challenge may differ between the two. Irrespective of this disagreement as to the definition of waiting time, there are clearly three options available to anyone seeking to address the issue. One can seek to limit demand, increase capacity and/or improve efficiency. Which alternative is preferred depends very much upon the assumed causes for the existing waiting time challenge. If one believes that a large portion of the challenge is the result of an abuse of the system by the user then it is a reasonable strategy to attempt to eliminate this unnecessary demand. On the other hand, if one believes that it is simply a question of too much legitimate demand for too little capacity, then increasing current capacity becomes the only viable option. Finally, if one believes that the major cause behind excessive waiting times has to do with the mismanagement of existing resources then improving current capacity usage is paramount. Of course, there is no reason why a situation might not warrant the implementation of more than one, if not all, of the above options simultaneously as a health care system may be dealing with too much legitimate demand for current capacity while still facing potentially unnecessary demand and attempting to improve the efficiency of current capacity usage. Incidentally, it is worth noting that zero waiting time is generally considered not to be optimal [48]. Queuing theory clearly demonstrates that to have zero waiting 4 time requires significant excess capacity [58]. Nor is the reasoning difficult to grasp. Demand for hospital resources can vary dramatically from one day to the next. Thus, any system that seeks to meet all demand immediately must build enough capacity to satisfy peak demand levels. However, on days when demand is less than expected, this inevitably results in unused capacity. The existence of waiting patients allows the resource manager to improve capacity utilization through prior scheduling, smoothing out some of this variability in demand. On the other hand, a growing waiting list brings its own challenges. First, and most importantly, there is the potential for deterioration in the patient's health ([47], [51]). Secondly, there is an increase in resources being used simply to maintain the waiting list [54]. A l l this suggests that there are optimal queue lengths, depending on the severity of the condition being treated, that lie above zero but undoubtedly below the current levels in most countries with universal health care. Below is a very brief analysis of various responses to the waiting time challenge divided into the three broad classes of limiting demand, increasing capacity and improving efficiency. 2. Limi t ing Demand There are at least three methods for reducing demand - one involving rationing de-mand and the other two seeking to eliminate unnecessary demand. The first involves imposing a financial burden on the user. The most obvious example is the United States where there is little to no waiting time problem for most medical services -provided you have the means to pay for it [51]. This is due to an excess of capacity resulting from the high cost to the user in the private system. Of course, the more affordable public versions of health care within the United States do experience the 5 usual waiting time challenges. Less radical methods impose a co-payment on the user that, while failing to cover the entirety of the cost, nevertheless acts as a disincentive to users. One variation on this theme involves subsidizing users who seek care outside of the public health care system. Thus, rather than forcing users to pay a fee for service in the public system, this scheme seeks to minimize the financial barriers associated with seeking help in a co-existing private health system so as to relieve the stress on the public one. Australia has recently gone this route by agreeing to pay 30% of private insurance costs as well as providing a tax incentive for taking out a private insurance package [18]. Secondly, one can reduce demand by giving the professional experts the opportu-nity to sift out potentially unnecessary demand. New Zealand has taken this option by giving hospital doctors the ability to send patients back to the referring physician if they deem the request to be insufficiently urgent [35]. Finally, there is a whole area of demand reduction through health promotion and prevention. Much like improving efficiency, there is little argument raised against the idea of prevention as a means of demand reduction. The debate comes simply in terms of its potential impact. Here there is legitimate disagreement as it is extremely difficult to assess what demand might have been had a method of prevention not been put into effect. Thus, assessing prevention methods depends very much on subjective assumptions [24]. 2.1. Demand Rationing Through Pricing. Turning first then to demand rationing through co-payments, Siciliani and Hurst [51] demonstrated that there is a significant correlation between a country not reporting significant waiting times for 6 hospital procedures and the presence of some form of co-payment. However, they suggest that the co-payments are often so low as to bring into question whether price rationing is really playing a major role. Two options are available to those seeking to impose a financial constraint. The first is to develop a secondary (invariably private) health system that requires the user to pay a significant cost while still maintaining a public system open to all. England is the most obvious example. A second method is to impose a more nominal co-payment for all users and maintain a single health system. Sweden and Ireland both fall under this category [51]. Critics of the first method are not hard to find. It is pointed out that while such methods may decrease the mean waiting time by allowing some patients to receive treatment much more promptly, it does so only at the expense of increasing the length of time to treatment for those who remain in the public system. The rationale is that though a private health care system will remove some demand from the public system, it will also inevitably siphon off doctors and nurses as well. Even if, as in the U K , doctors are required to work part-time in the public system in order to maintain their license, there still remains the fact that a certain portion of their working hours has been removed from the public system. If the total pool of resources (doctors and nurses) remains the same when broken into two separate systems of private and public health care then it is self-evident that any decrease in the waiting time for those in the private system must necessarily come at the expense of an increase in the waiting time for those in the public system. Queuing theory has long known that dividing a single queue, originally serviced by a single pool of servers, into multiple 7 queues with dedicated servers for each queue will inevitably increase waiting times provided the number of servers (and the average service rate) remains the same [58]. Two potential refutations of this line of reasoning are one, that the introduction of private health care increases the number of doctors and nurses by attracting more people to these fields and two, that a private system will increase throughput without having to increase resources. It would seem reasonable therefore to explore whether either of these two claims have in fact proved true in past instances where private heath care has been introduced and whether the potential increase in throughput is sufficient to mitigate the negatives associated with dividing one queue into two. Only then would we have a true grasp on whether private health care can in fact help reduce waiting times for the majority of patients. Finally, there is good reason for believing that the introduction of a concurrent private system may actually increase per capita spending on heath care. The United States per capita spending on health care is significantly higher than any other OECD country [51]. Australia's health care spending has increased from 8.5% of the GDP to 9.5%, perhaps due to the subsidies given to those taking the private health care option [18]. Imposing a more nominal co-payment fee on all users is most obviously open to the criticism that, no matter how nominal the fee, it necessarily marginalizes the poor. And herein lies the real challenge to these methods of demand reduction - is it legitimate to ration demand for health care services through pricing? If we accept the premise that health care should be available to all and if the aim, therefore, is to remove unnecessary demand then, unless we have reason to believe that it is the poor who are imposing this unnecessary burden on the system, surely pricing is a poor 8 method of rationing. Is it not possible to determine a better means of identifying and rejecting unnecessary demand - if it indeed exists? 2.2. Demand Rationing Through Priori t izat ion. This is precisely what New Zealand has attempted to do in taking a somewhat different route to demand reduction. In 2001, New Zealand introduced a booking system relying on a priority score assigned to patients, coupled with a maximum six-month waiting time guaran-tee. Each hospital sets a priority threshold that corresponds to the level at which they can maintain a maximum six month wait. Any patient who receives a priority score below that threshold is referred back for clinical review (essentially delaying their surgery) and re-enters the system at a later date (eventually receiving a score that allows them to be booked). Patients who score below a second threshold are referred back to their family doctor [35]. While this does mean that no patient waits more than six months from the time of booking to the time of surgery, it does so only at the expense of leaving a portion of the demand in limbo. Thus, actual waiting times may significantly exceed the six-month limit. Again, such a policy only makes sense if one believes that there is a portion of the demand that is essentially unnec-essary and thus can reasonably be put off without incurring a cost to patient health. The advantage of the New Zealand solution is that it places the decision of whether a medical procedure is unnecessary in the hands of the medical experts whereas a form of co-payment has the effect of placing that decision in the hands of the patient prior to consultation with a physician. The disadvantage is that even patients who are deemed not to need treatment still need to be prioritized and thus such a policy incurs a significant administrative cost that would not be incurred with a co-payment plan. Nor is a priority system free from controversy as doctors will inevitably disagree 9 on what is and what is not necessary. However, prioritizing patients is unavoidable so it is difficult to see how this subjectivity can be avoided by any system. It seems reasonable to suppose that, in a system where the user pays nothing, there is potentially a tendency to overuse the service. However, it is also clear that placing too great a roadblock can often lead potential patients to ignore symptoms until they reach a certain level of severity. A t that point, it may very well be more costly to treat than it would have been initially. Finding an intelligent means of removing unnecessary demand while at the same time not deterring legitimate demand is a delicate and complicated task that may in fact turn out to be the illusive pot at the end of the rainbow. 2.3. Demand Rationing Through Prevention. Finally, there is the option of reducing demand through prevention as opposed to rationing. Is it possible to find means of reducing the demand for a resource by providing other, less costly, alternatives? This option has been most extensively explored in the case of emergency departments. Some examples include ambulatory services that allow some patients to be treated without having to be seen at the hospital, short stay units and fast track systems [9]. There is, of course, little disagreement over whether or not one should reduce demand through prevention if possible. However there is plenty of disagreement over what methods are appropriate - meaning that they are effective without harming patient health. 3. Increasing Capacity In most countries with universal health care attempts to limit demand are highly contentious and thus the focus often shifts to increasing throughput - either through 10 increased capacity and/or improved efficiency. Political pressure in Spain has led to a number of initiatives designed to increase capacity. From 1996 to 1998, Spain managed to reduce mean waiting time (from request to treatment) for surgery by five months; largely as the result of increased day surgery and improved hospital management. The size of the waiting list shrunk from 190,000 to 132,221. However, by 2000, about a third of that improvement had been lost putting the pressure back on the government. Initiatives were put in place to provide additional surgery time by having surgeries performed during the evening. As a last resort, the government promised to pay for private sector treatment for any patient whose waiting time had become excessive ([10], [11])- One of the arguments against increasing capacity has always been that it wi l l lead to a resulting increase in demand. It is difficult to know whether this was the case in Spain or whether it was simply that hospitals reverted to old practices, leading to a rebound in waiting times. The international experience of attempting to improve waiting time through in-creased capacity has not generally been very positive. Ireland [38], the Netherlands [50], the U K [29] and Canada [39] have all earmarked significant funds (ranging from $100 million to $4 billion) to initiatives designed to reduce waiting times but with little evidence of success (though, to be fair, for some it may be too early to judge). Whether this is a necessary outcome of attempts to increase capacity or simply the result of poor choices on the part of each country is much too detailed a question for this introductory survey. It does seem to demonstrate, however, that simply in-creasing funding does not necessarily lead to reduced waiting times. In fact, at least two studies have documented an increase in waiting time following an increase in l l capacity. In Manitoba, the volume of cataract procedures increased considerably be-tween 1992 and 1997. However, over the same period, the median waiting time also increased. A second study on surgical services in Britain found that as the number of hospital admissions increased, so too did the length of the waiting list [46]. The most common explanation for this rather surprising result is that demand is proportional to expected waiting time. Reduce the expected waiting time and demand increases bringing waiting times back up to what they originally were or even higher. The implication is that waiting times act as a form of rationing already deterring some demand or diverting it elsewhere. A specialist may, for instance, determine that an M R I scan would be helpful for diagnosis but that, due to the length of wait, it might be easier simply to treat and see whether the patient improves. Were waiting times less lengthy, he might choose instead to confirm the diagnosis first. 4. Improved Efficiency While every resource manager would love to have greater capacity, the reality is that there are limits to how much capacity can be made available. Given the already high financial burden associated with running a public health care system, it is perhaps not surprising that the major policy for tackling the waiting time challenge is improving the use of available resources. Street and Duckett present the argument that a large factor in current waiting times is the result of poor funding methods rather than too much demand for too little capacity. "If governments exhibit a positive willingness to pay in reaction to waiting list increases and hospitals give greater weight to increased admissions than reducing waiting times, then waiting times will grow beyond what is optimal" [54]. Thus, this argument would suggest that current 12 funding policies give incentives to hospitals to maintain long waiting lists precisely to secure more funding. Implicit in this argument is the belief that there is the potential for improving efficiency if only the funding scheme gave hospitals the incentive to do so. In Australia, attempts have been made to remove such negative incentives. The first measure was to link hospital funding to activity rather than to the size of the waiting list. Each treated case at a hospital attracts payment according to the pa-tient's diagnostic type. Thus hospitals are rewarded for increased throughput but are not (if the weighting has been done correctly) penalized for taking on long-term patients. Approximately 50% of all hospital funding in Australia is now linked to the number and type of patients treated. Additional funding was also made available to those hospitals that reduced their waiting list. Specifically, hospitals were not per-mitted to claim this additional funding unless they had reduced their priority one patients' waiting times to acceptable levels by December 1993. Priority two patients' waiting times were to be within acceptable limits by Apr i l 1994. The results were dramatic for the top two priority levels with little change in the lower priority levels [54]. This would seem to suggest that the implicit assumption that there is room for improved efficiency given the right incentive is justified. However, it is possible that some demand was going unmet in order to keep waiting times at the levels required for the additional funding. The more recent Australian study mentioned earlier [18] also suggests that despite the initially good results, waiting times have not remained within "acceptable limits". The danger here is of a "Catch 22" situation where one can only receive additional funding if the queue size is reduced but one can only reduce the queue size if given additional funding. This is especially the case if it is 13 true that any reduction in waiting times leads to an increase in demand. Moreover, though removing the incentive for long waiting lists, the Australian funding scheme gives a decided incentive towards rushing patients through the system. Might this not be a case of substituting one poison for another? A second method of improving efficiency, applying primarily to emergency depart-ments, is to create a separate stream for patients whose treatment time is relatively short. A study in the U K looked at the implementation of a separate stream policy at an emergency department. They collected data for the five weeks prior to the introduction of the policy change as well as for the five weeks after and demonstrated significant improvements in the percentage of patients whose waiting time was less than an hour. These findings were duplicated in a Canadian study published in 2006 [9]. Again, queuing theory would have predicted as much. Intuitively, one can imag-ine the benefit of such a system by considering two people in a queue - one with a long service time and one with a short service time. It is clear that average waiting time is minimized by allowing the shorter service time patient to go first. This is essentially what a fast-track separate stream does. Such a policy would seem rea-sonable provided the separate stream was kept constantly busy. Queuing theory can easily determine how much slack in the separate stream would be necessary in order to negate the potential benefit. Finally, a number of countries (including Sweden, New Zealand, Canada and the UK) have sought to improve efficiency by imposing maximum waiting time limits in an effort to force hospitals into greater efficiency ([26], [35], [59]). Again, the implicit assumption is that there is room for improved throughput if the appropriate incentive is provided. The Australian answer was to dangle the proverbial "carrot" 14 of extra funding. These countries chose instead to wield the "stick" of imposed waiting time guarantees. Sweden is perhaps a good model of the consequences. In 1992, Sweden introduced a maximum waiting time guarantee of 12 weeks for 12 key procedures. In the first year, an additional $70 million was set aside to help hospitals meet those targets but after that they were required to maintain the same targets without additional funding. At the beginning of the initiative there was 51 000 patients in the queue. B y the end of the first year, this was reduced by 21%. Those waiting more than 13 weeks went from being 50% of patients to 10% of patients. A t the same time, throughput increased from 161 300 to 180 000. Interestingly, waiting times began to improve as soon as the decision to introduce maximum limits was introduced but before the additional funding was provided. However, during the second year waiting times once again began to rise [26]. What was not reported, and what is surely of vital importance to the analysis, is whether or not the improvement in the 12 key procedures was achieved at the expense of other procedures not subject to the maximum waiting time guarantee. For instance, one study found that imposing a two week rule on the maximum waiting time for urgent cancer patients resulted in a doubling of the waiting time for routine cancer referrals [59]. " A tank of water under pressure, if plugged in one area will simply explode in another". Likewise, unless the pressure to the health system is relieved (i.e. capacity made sufficient to meet demand), it is difficult to imagine maximum waiting time guarantees doing anything other than transferring the problem from one class of patients to another. Is there enough inefficiency in the system for improved efficiency to relieve the pressure? That question can surely only be answered on a case by case basis. Cer-tainly, it seems reasonable that, before increasing capacity, we seek to use the capacity 15 that we already have as efficiently as possible. As mentioned earlier, one of the major barriers to doing so has persistently been the lack of consistent, reliable data. Most medical databases are designed primarily for diagnosis and treatment and not policy. Thus, the data necessary for monitoring the efficiency of the system is often lacking. As one Canadian report states, The waiting list "nonsystem" in Canada is a classic case of forced decision-making in the absence of good management information. There is a surfeit of non-standardized data and a dearth of usable policy-oriented information about waiting lists. The most serious consequence is that information and management defects are almost always prema-turely diagnosed as financial shortages [33]. Most governments have realized this and are taking steps towards rectifying the lack of data ([36], [52]). In the mean time, it is difficult in the extreme to determine whether there is sufficient capacity, if managed efficiently, to meet demand or whether any initiative to improve efficiency must be coupled with increased capacity. Nevertheless, it stands to reason that any improvement in the efficient use of current resources can only help to mitigate the negative impact of the waiting time challenge. 5. The Impact of Scheduling on Waiting Times It is not the intention, in this introductory chapter, to give an exhaustive survey of all that has been done to maintain reasonable waiting times. Rather, we seek to give the reader a sense of the urgency of the waiting time challenge as well as the incredible variety of possible responses. This urgency is heightened by the well-known fact that, for most O E C D countries, the proportion of the total population above 65, 16 who are the largest users of the health care system, is increasing rapidly. The research presented in this thesis necessarily focuses much more narrowly on a specific aspect of the waiting time challenge - namely the optimal scheduling of patients to a hospital resource. Scheduling for a hospital resource is most often complicated by the fact that de-mand for the resource comes from numerous sources with varying degrees of urgency. Since the lower the urgency of a patient, the further in advance treatment is booked, it is unavoidable that, for any given day, it is the lower priority patients who are booked first. Booking too many lower priority patients into a day may result in there being insufficient capacity left to meet the later arriving higher priority demand. Booking too few lower priority patients into a day may result in unused capacity which might otherwise have been used to serve these lower priority patients sooner. Thus, either way, sub-optimal scheduling policies may lead to excessive waiting times for certain priority classes. There are two angles to attacking the scheduling challenge. First, there is the issue of how to optimally schedule patients given there is a fixed available capacity. Chapter 2 takes this approach placing a limit on available capacity and then seeking to determine the effect on patient waiting time for the various priority classes when an optimal scheduling policy is put into practice. Secondly, and perhaps more importantly, there is the issue of determining how much capacity you need in order to meet the waiting time limits recommended for each patient priority class. Chapter 3 takes this approach presenting policies that seek to meet the waiting time limits with minimum capacity. Of course, how much capacity is needed depends heavily on how efficiently one uses the capacity available. For the purposes of meeting the scheduling challenge we will assume that there is a fixed number of patients who can be served in 17 a given day with some additional capacity available through overtime. We leave aside the issue as to whether there might be efficiencies to be gained through procedural improvements so that more patients might be served during regular hours. 6. Diagnostic Imaging To be more concrete, the research focuses particulary at the scheduling of patients for a diagnostic resource. This resource faces precisely the challenge mentioned above as demand comes from three sources. Of highest priority is demand coming from the emergency department that must be met immediately. Second, there is a highly variable demand from the inpatient (IP) population within the hospital that must either be served today or, in some cases, by tomorrow at the latest (though current practice seems to serve all IP demand the day the request is received). The third source consists of outpatient (OP) demand. This demand arrives in the form of faxed requisitions coming from specialist physicians in the region serviced by the hospital. Upon arrival, these requisitions are given to a radiologist who breaks the total OP demand into numerous priority classes - each one with a maximum recommended waiting time assigned to it. The requisitions are then returned to the booking clerk who is responsible for booking these O P days or even weeks in advance. Thus, diagnostic resources are a classic example where a scheduling policy is crucial as, for any given day, lower priority demand must be booked prior to knowing the extent of the higher priority demand that may arrive between now and the day in question. Though the mathematical models developed in the following chapters will focus on diagnostic resources, it is hoped that the above description of the scheduling challenge makes it clear that the methods and insights developed here are applicable to any 18 hospital resource (such as surgery or cancer treatment) facing demand from multiple priority classes. It is not difficult to show that diagnostic imaging faces, and wil l continue to face, the challenge of excessive waiting times. According to the World Health Organization, "about 30% of medical cases around the world require diagnostic imaging in order for referring physicians to make a proper diagnosis" [53]. This number is most likely to increase as more and more potential uses for C T (computed tomography) and M R I scans are discovered. In the last decade alone, the number of M R I scans performed in Canada has quadrupled [37] so that currently 35 million diagnostic scans are performed every year with an annual increase of 6% [53]. Two Canadian studies mentioned earlier ([20], [47] both reported a significant portion (more than 50% in the one, just under 50% in the other) of patients who waited more than a month for a C T scan. Considering the maximum recommended waiting time for the lowest priority class in both Alberta and British Columbia is 28 days, this would suggest that waiting times are in fact excessive. The reasons behind this massive increase in the use of diagnostic imaging are numerous and better documented elsewhere [31] but the salient fact is that the demand continues to outstrip the capacity exacerbating the need to use the available capacity as efficiently as possible. Answering the scheduling challenge is one necessary step towards doing so. 7. Related Literature in Operations Research Our research, using mathematical models to manage queues, falls under the gen-eral operations research field of queueing theory. A helpful overview of research within 19 queueing theory applied directly to health care is provided by Preater from Keele Uni-versity [40]. The specific issue of servicing demand from multiple priority classes has received extensive coverage within operations research. The two main applications have been airline revenue management ([6], [12] and [60]) and call center management ([4], [14] and [30]). Though useful for comparison, there are significant differences between these applications and the scheduling challenge within health care. The airline revenue management has the advantage of generally looking at a small number of flights over a finite horizon. In our situation, each potential booking day could be viewed as a flight and, though the booking horizon (the maximum number of days in advance patients are booked) is finite, it is also continuously evolving, leading to an infinite, rolling horizon problem. Moreover, the objective in airline revenue management is, understandably, to maximize revenue which allows for a different formulation than for the case where the objective is to minimize excessive waiting times. Most notably, minimizing excessive waiting times forces one to take into consideration the whole horizon rather than truncating the horizon to a finite setting. The call center management papers deal with similar issues of minimizing wait-ing times with limited capacity so that it is perhaps here that the comparisons are potentially most useful. Here too the trade-off is between service level (often given in terms of waiting time guarantees) and cost. Moreover, if there are multiple priority categories, they are generally differentiated according to a maximum waiting time guarantee that necessitates some kind of reservation policy for later arriving higher priority clients. However, there are some significant differences. For instance, in call center management, clients are not booked days in advance but held in a queue. 20 Essentially, this means that call centers are equivalent to hospitals that serve only inpatients as all "clients" are there and can be served immediately if space becomes available. Secondly, call centers do not deal with a booking horizon as all clients are either serviced within a specified time frame or lost to the system. Thus, each day the call center begins with an empty queue. This allows for a finite horizon model as opposed to the rolling, infinite horizon model necessary in the hospital setting. Nonetheless, there are clearly useful comparisons to be made. When turning directly to health care applications, the scope of research nar-rows considerably. Two distinct branches of the literature emerge. In the first, the trade-off modeled is between unused capacity (resulting in longer waiting times) that results from under-scheduling a resource and excessive overtime that results from over-scheduling that resource. Gerchak, Gupta and Henig model this trade-off in the case of elective surgery scheduling [22]. The challenge is to schedule elective surgeries while leaving room for possible emergency surgeries. Strum et al. develop a minimal cost analysis model based on over-utilization and under-utilization applied to O R blocked time for subspecialties ([55], [56]). L iu and L i u analyse an O P clinic with multiple doctors with the complication that doctor arrival times are stochastic [34] and Ridge et al. model the effect of balancing the cost of unused beds in the I C U against the cost of insufficient capacity [43]. Finally, Rohleder and Klassen present a simulation based model that compares various potential methods for reducing waiting lists in the presence of uncertain demand with a fixed number of slots reserved for emergencies [44]. A second branch of research looks to choose the optimal schedule in order to maximize revenue ( [23], [25]). Such models are only reasonable in the private health 21 care setting. For a resource manager in public health care, it is not revenue but accessibility and efficiency that are the objectives. Excessive waiting times address both these objectives. Both papers mentioned here present finite horizon models that do not capture the effect of the scheduling policy on the waiting times of the patients. As far as we know, no paper has modeled how to schedule more than two priority classes to a given resource in such a way as to minimize excessive waiting times. Chapter 2 of the thesis mirrors a situation very similar to Gerchak, Gupta and Henig as we assume only one OP priority class and examine the optimal reservation policy for IP and emergency demand. Our analysis differs in that we directly examine the impact of the scheduling policy on OP waiting times as well as demonstrating the significant advantage of introducing some flexibility into the scheduling of the highest priority class. The end result is an optimal reservation policy for IP and emergency demand under a strict limit on expected overtime per day. Chapter 3 turns the attention towards booking the remaining capacity amongst the various OP priority classes. The extension to more than two priority classes scheduled over a longer period of time makes for a much more involved scheduling challenge. Chapter 3 models the scheduling process as a Markov Decision process (MDP). However, the state space for the MDP is much too large for a direct solu-tion so we derive an approximately optimal scheduling policy through approximate dynamic programming (ADP). ADP is an emerging and highly promising field of re-search. The two main textbooks in the area are Neuro-Dynamic Programming [5] and Reinforcement Learning [57]. More recent insights into the field have been provided by Adelman ([1], [2] and [3]) and by De Farias and Van Roy ([15], [16] and [17]). Both textbooks provide an array of potential approximation methods that will be 22 discussed briefly in Chapter 3. Our own work follows that of Adelman and De Farias and Van Roy in transforming the M D P into the equivalent linear program (LP) and then solving the L P by approximating the value function in the objective. Chapter 4 of the thesis provides some strong theoretical results of the model presented in Chapter 3. We first establish analytically the form of the optimal linear approximation to the value function. As far as we know, this result is unique in the literature. The significance of these results is that it allows us, under mild constraints on the cost parameters, to derive the optimal value function approximation without having to solve the L P and, moreover, demonstrates the robustness of our results to changes in parameter values. Secondly, we present a discussion of potential bounds on the difference between what might have been achieved could we have solved the original M D P and the results we did in fact achieve through approximation. This remains a wide open area of research as practical bounds on this difference are not readily available. Chapter 5 then seeks to compare the models presented in Chapters 2 and 3 sug-gesting some practical policy insights for the resource manager in terms of allocating available capacity to the various sources of demand. Finally, Chapter 6 discusses some potential enhancements to the model as well as discussing the challenges that may arise in applying the methods and results presented in this thesis to other potential hospital resources outside of diagnostic imaging. It is gratifying to note that the recent report by the Canadian federal advisor on Wait Times specifically encouraged the use of queueing theory to address the waiting time challenge [39]. We trust that the work presented in this thesis wil l help convince those working within the health care sector that operations research, and particularly 23 queueing theory and optimization, can play a significant role in improving resource utilization within hospitals. 24 C H A P T E R 2 Improving Resource Utilization through Inpatient Scheduling 1. Introduction Throughout the health system, both within Canada and elsewhere, excessive wait-ing times are severely hampering our ability to provide adequate health care. While there can be little argument that the primary reasons for excessive waiting times are limited resources and increasing demands, there are secondary factors which im-pede the efficient use of existing resources. Among these secondary factors, perhaps none are more important than the variability in the demand. One day a resource is stretched beyond its capacity, the next it stands idle for large portions of the day. We will address the challenge of excessive waiting times by developing an approach to improve resource utilization and then demonstrate via simulation the resultant effect on the growth rate of outpatient (OP) waiting time. We will concentrate on the growth rate in OP waiting time as the most relevant statistic since the issue of waiting time is of most import in those instances where demand exceeds capacity and therefore where queues are long and growing. 2. The Problem At the most general level, this chapter addresses a situation where there is a fluctuating demand for a limited resource with two priority classes. Such a scenario occurs for instance in scheduling patients for operating room time (e.g. [22], [55] and [28]), or else booking MRI (magnetic resonance imaging) or CT (Computed 25 Tomography) scans. The key challenge is that the low priority demand must be booked prior to knowing the high priority demand. Therefore, a significant portion of the total capacity must be reserved for this unknown high priority demand - leading inevitably to unused capacity on those days when the high priority demand is lower than expected. We develop a policy that reserves a certain amount of resource time to each priority level. Gerchak, Gupta and Henig demonstrated that such a cut-off policy (in the case of booking elective and emergency surgeries) is potentially sub-optimal but they do so under the assumption that there are no fixed limits on overtime [22]. In reality, most hospitals do work with a limited overtime budget. Gerchak et al. also acknowledge that the relative difference between the optimal policy and the cut-off policy is minor. Their main contention is that optimal cut-off policies are computationally difficult to determine. However, in the case of limited overtime there is, as we will show, a very simple means of determining an optimal cut-off policy. The potential for improving the ability to achieve reasonable waiting times for outpatients by following Gerchak, Gupta and Henig's approach of allowing a varying overtime limit will be explored in chapter 3 and chapter 5. The motivation for this paper grew out of a detailed analysis of CT operations at the Vancouver General Hospital (VGH) where there is a large and fluctuating inpa-tient (IP) demand and three OP priority classes. OP priority levels are broken down according to the maximum recommended waiting time. What makes this a scarce resource problem is that waiting times for OP are, at present, significantly longer than recommended. One long-term goal of the project is to provide a reservation policy that will cover all priority levels. This larger model is addressed in chapters 3 26 and 5. For the purposes of this chapter, however, we will assume only one OP cate-gory. A l l IP are currently viewed as high priority - meaning that the demand must be met the day it arrives. Since OP demand is booked weeks in advance, it is clear that, for any given day, the low priority demand (OP) is booked prior to knowing the high priority demand (IP) for that day. In order not to overtax the system on days when IP demand is high, the department is forced to reserve a significant portion of scanning time for this unknown IP demand, leaving little room for OP. This results in unused capacity on days when IP demand is low and thus longer waiting times for OP than might be the case if this unused capacity could be utilized. 3. The Proposed Scheduling Approach Our attempt to make use of the unused capacity in the system hinges on the fact that, contrary to current practice, not all IP need to be scanned the day the request for a scan is placed. Our proposal is as follows: • Divide IP into two categories - high priority inpatients (HIP) who must be scanned the day the request is placed and low priority inpatients (LIP) whose scans can be delayed one day. • Identify a group of OP who will be on call for scans with one-day notice. • Reserve a specified number of slots for IP on each day. • Reserve a specified number of slots for possible carry over of LIP to the next day. • Limit overtime (OT) usage. How to make this operational will be described in the remainder of this chapter. A division of inpatients as suggested above already exists at Vancouver General Hospital. 27 The prioritization scheme recently put in place contains a category for IP that can wait up to twenty-four hours. This group contains pre-operative investigation for head and neck, routine follow-up for intracranial disease, pre-operative oncology staging, numerous fractures and some chest infections. However, this distinction is currently being ignored since all IP are scanned the day the request arrives regardless of the priority classification. The advantage of such a division is that there is a pool of patients who are available to be scanned on the current day but do not necessarily need to be. One might liken LIP to stand-by passengers on flights. Just as stand-by passengers provide the airlines with the ability to fill last minute unused capacity, so LIP would provide the hospital with the same flexibility. The major difference is that LIP must be scanned within the next 24 hours. As mentioned in chapter 1, there is potentially some useful crossover here as substantial research has gone into developing reservation policies for numerous priority levels within the airline industry. However, the airline industry is generally dealing with a small number of flights at a time over a finite horizon whereas a CT department is booking over an infinite rolling horizon where each day could be viewed as a separate flight. We assume that the resource units are 15 minute scanning slots since the vast majority of scans are scheduled for 15, 30, 45 or 60 minutes. Thus a 60 minute long scan would equate to four units of resource time. The capacity of the system is the number of 15 minute scanning slots that can be scheduled for any given day. Initially, we will assume that all scans are scheduled for 15 minutes and later investigate, through simulation, the effect of introducing multiple exam lengths. Of course, actual exam lengths are stochastic and vary quite substantially from the scheduled length 28 (see [56] for a comparison of normal vs. log normal exam lengths). However, from a booking point of view, it is the scheduled length of the exam rather than the actual length that is relevant. We will discuss the effect of introducing stochastic exam lengths later in the chapter. We assume there are a total of C regular hour slots available per day. Our proposed scheduling policy works as follows. Each day, H slots are reserved for IP and an additional L slots for any LIP carried over from the previous day. The remaining C — H — L slots are available for booking OP demand. Note that the trade-off is clear - the more slots reserved for IP (H + L), the less scanning time is available for OP resulting in longer OP waiting times. On any given day perform all HIP scans and as many LIP scans as possible in the H reserved slots. At the end of the day, any additional LIP scans not performed are booked into the L slots reserved for tomorrow. If any of the L slots are not filled, then on call OP from the waiting list are called to fill the remaining slots - reducing the total number of reserved slots for tomorrow's IP to H. In other words, looking forward days in advance, the policy reserves a total of H + L slots for IP but on the day before, it reduces this to H reserved slots by booking any remaining LIP scans and/or additional OP scans into tomorrow's L slots. (We impose the further restriction that no more than L LIP scans are carried over to the following day in order to avoid any snowball effect. If more LIP scans arrive on any given day than can be dealt with through the H slots reserved for IP today and the L slots reserved for carry-over to tomorrow, then the excess is dealt with through overtime.) A short numerical example further illustrates the proposed reservation policy. Table 2.1 presents hypothetical daily IP demand for a given week. (Note that although 29 T A B L E 2.1. Illustrative IP Demand Data for One Week Day 1 Day 2 Day 3 Day 4 Day 5 HIP demand 60 45 75 55 55 LIP demand 10 12 15 13 12 Total demand 70 57 90 68 67 the demand for the whole week is given, each day's demand is not known until the day it arrives.) Assume that the number of IP reserved slots, H, is set at 65 and the number of carryover reserved slots, L, is set at 10. On day 1, all 60 HIP and 5 LIP are scanned while the other 5 LIP are carried over to day 2. No overtime is required and there are no empty slots. Since only 5 of the 10 carryover slots are used by LIP, an additional 5 on-call OP can be scheduled for day 2. This reduces the total number of reserved slots on day 2 to H. On day 2 demand is low so all HIP and LIP patients can be accommodated (45 + 12 < H) without requiring overtime or holding any LIP over to day 3. However, there are 8 (65 - 57) unused slots. Since no LIP are held over, an additional 10 on-call OP can be booked for day 3. On day 3, total IP demand spikes and 10 overtime scans are required just to meet the HIP demand. In addition, since no more than 10 LIP can be held over from one day to the next, 5 of the third day's LIP must be scanned using overtime with the other 10 being carried over to day 4. No additional OP can be booked for day 4 as all L slots are filled with LIP. For the week, the number of unused slots, the overtime required, the number of LIP carried over and the number of additional OP booked are given in Table 2.2. The units again are the number of 15 minute scanning slots. 30 T A B L E 2 . 2 . Performance of the Proposed Policy (H = 65, L = 10) Day 1 Day 2 Day 3 Day 4 Day 5 Total Unused Capacity 0 8 0 0 0 8 Overtime Scans 0 0 15 0 0 15 LIP held over to next day 5 0 10 3 2 20 Additional OP booked 5 10 0 7 8 30 T A B L E 2 . 3 . Performance for the Policy (H = 75, L = 0) Day 1 Day 2 Day 3 Day 4 Day 5 Total Unused Capacity 5 18 0 7 8 38 Overtime Scans 0 0 15 0 0 15 Additional OP Booked 0 0 0 0 0 0 Contrasting this with the policy that simply reserves 75 slots for IP (Table 2.3) gives an indication (despite the fictitious nature of the data) of the potential increase in resource utilization gained by the introduction of LIP. In particular, under the proposed policy, we have been able to fill 30 of the 38 unused slots that arose under the current policy. Note that this is done without increasing overtime. 4. Is The Proposed System Practical? It is worth, at this point, pausing to consider the practicality of implementing the proposed policy. First, while it is known that several patients fall into the LIP category, no data is currently available to determine the proportion of the total IP demand that would fit such a classification. What we will show however is that the number of patients in the LIP category need not be a large percentage of the total IP demand in order to have a significant impact on OP waiting time. Second, there 31 is the practical issue of having a pool of on-call OP able to respond to a single day's notice. Again, we will show that the proportion of OP willing to be on call need not be a large percentage of the total OP demand. It seems reasonable, at least for a reasonably large city, to assume the existence of a pool of OP within easy distance of the hospital who would gladly be on call in order to shorten their waiting time. Gerchak, Gupta and Henig assume, not unreasonably, that all OP can be called in to receive their surgery earlier than initially scheduled [22]. Third, there is a question of increased workload on the department staff. However, the only additional work placed on the staff is that of calling the on-call OP the night before. In our opinion, this added load is more than justified by the benefits of improved resource utilization. (In fact, one recommendation of the V G H study was to call OP the night before their scan in order to minimize no-shows so, in reality, there would be no additional work.) Fourth, there is a legitimate concern that such a system would increase costs due to increased IP hospitalization time. However, judicial use of the LIP category (i.e. not classifying as LIP those whose hospital stay might be shortened by a prompt scan) should alleviate this problem. Finally, we will show that such a system does not, as might be supposed, increase overtime. The initial feedback that we have received both from hospital administration and the staff within the CT department has been favorable. Their major concern regards the size of the LIP category. No one could give us much insight as to what numbers to expect though they were cautiously optimistic that our proposed scheme could work - perhaps not at Vancouver General which is a tertiary care hospital, but at a community hospital where patients spend extended periods of time in hospital. 32 5. Choosing L and H Of course, the obvious question concerns the choice of L and H. From a practical standpoint, the most likely scenario is that a hospital will have a set overtime budget that should not be exceeded. Thus, one possible approach is to choose L and H to minimize the expected number of empty slots subject to a constraint on OT. The papers referred to above do not put a limit on OT but rather assign a penalty to OT and then seek a policy to minimize cost. This is mathematically much more difficult and the benefit is dubious. Assigning a "cost" to unused capacity is complex and thus one ends up adjusting the parameters to see what works regardless. Our approach is to impose an OT limit and then adjust to see the effect. From a practical standpoint this is reasonable as hospitals do have a budget that they are trying not to exceed. The above scenario generates a simple optimization problem that can be solved for any given breakdown of IP demand into HIP and LIP. For instance, if we assume the daily arrival rates for HIP and LIP follow independent, stationary Poisson distributions (see later discussion for validation) with means A# and XL respectively then the optimization problem is to minimize subject to an OT constraint. The random variables DHIP and DLIP are the demand for HIP and LIP respectively. Since they are independent, their sum is Poisson with parameter \ H + XL- The above equation follows from the fact that there is only unused capacity if the sum of all IP demand is less than H. The OT constraint can H (2.1) . Expected Number of Unused Slots = ^ k * Pr(DHiP + DLIp = H - k) fc=0 33 take one of two forms - a limit a on the probability of OT or else a limit f3 on the expected number of units of OT. These lead to two optimization problems minimize: Expected Number of Unused Slots subject to: Pr(Overtime) < a and minimize: Expected Number of Unused Slots subject to: E[overtime] < (5. The probability of overtime can be written as: H (2.2) P r ( Z W >H) + YJ P*(DHIP + DLIp >H + L\DHIP = j) * Pv{DHIP = j) j=o j=H+l J ' V j=0 i=H+L-j+\ ' Note that the H in the above equation refers to today's H reserved slots and the L refers to tomorrow's L slots for carryover LIP demand, as it is these two numbers that determine today's OT. This also holds true in the following equations. Computing expected overtime is more complicated as it depends on whether the OT is due to HIP, LIP or both. Thus, the expected amount of OT is given by (2.3) fSc * ( E P r ( ^ = H + i) * p*(dLIP = L + k-j)\ k=2 ^ 0<j<fc ' oo ^-+ k * P r ( L W = k + H) * Pr{DLIP < L) fc=0 oo / H \ + E f c * ( J 2 F r ( D m p = t i * ' P T ( D L i p = H + L + k ~ j n fe=0 ^ j=\ ' where the three sums refer to the overtime due to both HIP and LIP, HIP only and LIP only respectively. Again, if we assume independent, stationary Poisson 34 distributions for the arrival rates of both HIP and LIP we get the following equation for the expected amount of OT In our opinion, the second OT constraint is more appropriate since it is easier to place a dollar figure on the expectation than on the probability. Note that the OT constraint does not impose a strict limit on the number of OT scans performed per day but rather places a limit on the expected number of OT scans each day. Our assumption of Poisson arrival rates is based on the data we collected for IP arrivals at Vancouver General Hospital (VGH) covering 8 months (see Figure 2.1). The larger than expected left-hand tail may plausibly be attributed to regular main-tenance on the CT machines that causes a reduction in throughput on certain days. We also tested the data both for a 'day of the week' effect and for any autocorrela-tion with negative results in both cases. There is thus very little ability to predict tomorrow's IP demand in advance. There are, however, no figures on how much of the total IP demand could be classified as LIP. Thus our assumption that the two IP categories form two independent Poisson distributions, though reasonable, needs to be verified. V G H did not collect data on OP arrivals and thus the only data avail-able to us was a two week period in which we collected the data manually. Thus our assumption of poisson arrivals rates for OP is based more on theory than data. Given that OP demand arises from numerous independent sources (GP and specialist (2.4) 35 offices), it seems reasonable to assume that the sum total of daily demand would be Poisson. There is definitely the possibility (though we didn't see it in the small data set we have) of a day-of-the-week effect that would be worth investigating. F I G U R E 2 . 1 . Daily Weekday IP Demand for V G H (May-December 2003) 3 0 2 5 wmm 1 5 1 0 iljl '-*y>i ii JLcJi LI I I II n D a i l y I P D e m a n d The optimization problem with a constraint on expected overtime was solved by a simple directed search in M A T L A B . The code searches for the smallest H for which there exists an L so that the pair (H, L) satisfies the OT constraint. This will minimize unused capacity (subject to the OT constraint) since unused capacity depends only on H. (We are assuming here that there is enough OP on call to fill any of the L slots not used by carryover LIP.) The algorithm starts with an H large enough so that, together with L = 0, it satisfies the OT constraint. It proceeds by reducing H until the OT constraint is violated and then, holding H constant, increasing L until the constraint is once more satisfied. While keeping L constant, the program then reduces H by one and attempts to find an L so that the combination (H, L) once again satisfies the OT constraint. It terminates when no such combination can be 36 found and returns the last viable combination. This combination minimizes expected unused capacity. 6. What Improvement Can We Expect? System performance can be measured by two metrics - the expected throughput rate (expected number of scans per day) and the expected growth rate in OP waiting time. The first can be calculated analytically and the second will be analyzed through a simulation of the scheduling process. Once H and L have been specified, it is a straightforward calculation to determine the expected throughput of the system. In such a scenario, the expected number of scans per day in the case where all IP are treated as HIP is given by: where H is the number of slots reserved for IP and C is the total capacity. The first term represents the number of scheduled OP scans and the second the expected number of IP scans performed per day. Here we are assuming that there is enough OP demand to fill however many scanning slots (C — H) are made available. If a certain percentage of IP can be classified as LIP, the expected number of scans per day can be calculated as follows (provided we assume that we can fill all slots that are made available for on-call OP): (2.5) (C-H) + E[DHIP\ = C-H + XH (2.6) (C - H) + E[DHIP + LIP not carried over] oo oo *Pv{DHIP = i)Pv{DLIP = j). 37 (Note that the H here may be different from the H generated for the initial case with zero LIP.) The three terms that constitute the coefficient multiplying the probabilities consist respectively of the number of HIP, the number of LIP scanned due to excess capacity (i.e. low number of HIP) and the number of LIP scanned due to having more than L LIP carried over. The above throughput rates as well as the resulting OP waiting times depend heavily on certain parameters - namely, the limit placed on OT, the IP demand rate, the percentage of IP classified as LIP and the capacity of the system. The rest of the paper will analyze system performance based on a simulation model of the scheduling process and study the sensitivity of results to variations in the parameters. Finally, we will consider the effect of introducing multiple exam lengths and stochastic service times as well as varying the percentage of OP willing to be on-call. 7. The Simulation Model Our simulation model, created in A R E N A , allows us to compare the effect of the model parameters on the growth rate in OP waiting time over any given period. We assume independent Poisson arrival rates for all priority levels. (Thus when we talk about LIP being 10% of total IP demand we mean that the mean arrival rate for HIP is nine times that of LIP.) A more contentious assumption is that all incoming IP demand for any given day arrives at the beginning of the day. This is unrealistic since, though most IP demand is known at the beginning of the day, emergency demand occurs throughout the day and is therefore not known at the outset. However, our results are a comparison of three possible reservation policies. If anything, the intra-day variation would be more detrimental (increasing OT and unused capacity) in the 38 case where all IP are assumed to be HIP than under our proposed policies since LIP patients would be identified early in the day (they would not be emergencies) and therefore would act as a pool of patients who could be scanned if and when space was available. As long as OP are generally scheduled earlier in the day (as at VGH) the intra-day variation will have little impact. Our own observation of the CT department revealed that for the majority of the day, the department had a pool of IP waiting for a scan that they called down when space was available. Thus unused capacity is unlikely to be affected by intra-day variation in IP demand. As for OT, it is possible that a late arriving emergency could cause additional OT but this scenario is equally likely under all reservation policies and therefore does not affect the comparison. We assume that OP demand arrives at the beginning of the day and is scheduled for the earliest day available. Chapter 3 looks at more interesting scheduling policies for OP. For now, with only one priority class, there is no need to do anything other than book incoming demand in the first available slot. A certain percentage of the total OP demand is tentatively booked but also set aside as "on call". These are the OP who can be called the day before to fill any of the L carry-over slots not filled by LIP for the next day. After each day, the simulation cycles through these "on-call" OP and places them into the available slots (on days when less than L LIP have been carried over to the next day) on a first in first out basis. As the simulation progresses, waiting times are recorded by priority level along with the arrival rates for the various categories, the amount of daily OT or unused capacity as well as the growth in OP waiting time from the previous day. We assume that an OP cannot be booked the day the request arrives. 39 Our initial testing of the simulation consisted of 100 replications of 1000 days each. We did not collect data for the first 500 days in order to mitigate the effect of initial conditions. We assumed a mean arrival rate for IP of 120 (15 minute scans) per day and a mean arrival rate for OP of 50 per day. This is clearly a large scale hospital (or multiple hospitals) with numerous CT machines. The regular-hour capacity is set at 165 which is five less than the average daily demand. We initially assume that all scans are 15 minutes and that an expected OT of five scans per day is acceptable. Thus the total capacity including OT is equal to the average demand. Actual practice at V G H tries to avoid OT completely which makes the use of LIP even more vital as shown below. Finally, we assume that 10% of OP are willing to be on-call and that 10% of IP can be classified as LIP. The results of the replications were very similar so we present the combined results with a 95% confidence interval. The reason for doing 100 replications of 1000 days each rather than one longer replication is that, since we are dealing with the case where demand outstrips capacity, OP waiting time is increasing without bound. This is not realistic as, after a time, either overtime will be used to meet demand or else demand will slacken as people go elsewhere rather than face the lengthening waiting times. The purposes of this model is simply to show that the rate of increase in OP waiting time can be greatly reduced by introducing the LIP category meaning that the amount of OT required to meet demand is reduced. These findings are confirmed in the larger model presented in Chapter 5. We assess three reservation policies that we will call: (1) The constrained reservation policy (2) The unconstrained reservation policy (3) Current practice (i.e. treating all IP as HIP). 40 T A B L E 2.4. Simulation Results (mean with 95% confidence limits) Average Constrained Policy Unconstrained Policy Current Practice H = 110 L = 9 +/ - H = 107 L = 15 +/- H = 119 L = 0 +/-Daily IP Arrivals 119.98 0.09 119.98 0.09 120.01 0.08 Daily OP Arrivals 50.01 0.06 50.01 0.06 49.97 0.06 Regular Hour Scans 163.96 0.01 163.93 0.02 161.12 0.02 Overtime Scans 4.98 0.06 4.03 0.07 4.89 0.06 Unused Capacity 1.04 0.03 1.07 0.04 3.88 0.05 Throughput (Scans/day) 168.94 0.07 167.96 0.09 166.01 0.01 Weekly Growth in OP W T (days/week) 0.10 0.01 0.21 0.01 0.43 0.01 The constrained policy, (H = 110, L = 9), is the optimum of the above optimization problem under the additional constraint that the total H + L should be no more than would be reserved if all IP were HIP. This policy will perform at least as well as current practice since the same number of slots is reserved. This modified optimization problem can be solved in precisely the same manner as the previous one except that the viable combinations of L and H are restricted. The unconstrained policy, (H = 107, L = 15), is the optimum of the above optimization problem without the additional constraint. Finally, we compare both of these to the current practice (H = 119, L = 0) of treating all IP as HIP. Table 2.4 shows the average per day over all replications for the relevant statistics as well as the average weekly growth rate. Both the constrained and unconstrained policies have significantly higher through-put rates and lower growth rates in OP waiting time than current practice. After 1000 41 days (starting from empty queues), the waiting time for OP under current practice grows to approximately 84 days while the waiting time for OP under the constrained optimal policy (column 1) only increases to 29 days. This significant reduction is achieved by identifying only 10% of total IP demand as LIP. It is accomplished with no additional expenditure (note that OT remained the same) and would seem to more than justify the procedural changes required. The fact that the more conservative constrained policy (column 1) outperforms (in reducing growth rate and increasing throughput) the optimal unconstrained policy (column 2) can be attributed (as will be shown later) to the fact that a 10% on call rate for OP is simply not large enough to take full advantage of the flexibility provide by the (H = 107, L = 15) policy. Thus the higher L value is detrimental since it means that there is less scanning time available for those OP not on call. The effect of classifying 10% of IP as LIP is to increase the number of scans per day by almost 3. This may not seem like a huge increase but, as Preater points out, it has been shown within queuing theory that "small changes to a heavily congested systems bring disproportionate changes in queue size" and hence waiting times [40]. Where demand outstrips throughput (under current practice) by just 4 scans per day, increasing the number of daily scans by almost 3 is a substantial step towards meeting total demand. Three additional scans per day over 1000 days results in 3000 more scans being performed than under the current practice. In that light it is perhaps understandable why there is such a significant difference in OP waiting time. Clearly, none of the three policies satisfy demand in the above instance (average number of scans per day for all three is less than the combined arrival rate) thus waiting times are increasing in all cases. However, as Table 2.4 indicates, it is the 42 rate of increase in OP waiting time that is significantly reduced. Figure 2.2 shows the growth in OP waiting time from a typical simulation run of 500 days in length for the constrained reservation policy and for current practice demonstrating the significantly lower growth rate in OP waiting time. FIGURE 2.2. Constrained Policy vs Current Practice (Simulation stan-dard error of 0.01) 45 -• 40 -35 -to >. 30 -re a> 25 -e i— o> 20 • c ' i • "re 15 • «S 10 -5 -0 -100 150 200 250 300 350 400 450 SOO D a y The rest of the paper seeks to demonstrate the robustness of these results to variations in the simulation parameters. 7.1. Varying the O T L imi t . Table 2.5 presents the expected unused capacity and expected number of scans per day, based on equations (2.5) and (2.6), as a function of the limit on expected OT for the three reservation policies. As one would expect, the more OT allowed, the less potential for unused capacity and therefore the less difference between the three cases. It is worth noting that we are assuming here that there is sufficient capacity to be able to reserve enough scanning time for IP so as to keep OT as low as required. The trade-off is simply that the more scanning 43 T A B L E 2.5. Effect of O T Limit on Capacity Usage Reservation Policy Constrained Policy Unconstrained Policy Current Practice O T H L Unused Scans H L Unused Scans H Unused Scans Limit Capacity per Day Capacity per Day Capacity per Day 1 121 10 4.89 161.09 118 17 3.43 162.56 131 11.94 154 2 116 11 2.63 164.28 114 15 1.98 165.00 127 8.77 158 3 113 11 1.70 166.21 111 16 1.23 166.71 124 6.68 161 4 112 9 1.45 167.53 109 15 0.86 168.01 121 4.89 164 5 110 9 1.03 168.96 107 15 0.59 169.3 119 3.88 166 6 107 11 0.59 170.25 105 16 0.39 170.56 118 3.43 167 7 106 10 0.48 171.43 104 14 0.32 171.55 116 2.63 169 8 108 6 0.72 172.26 102 16 0.20 172.26 114 1.98 171 slots reserved for IP, the less slots available for OP booking resulting in longer OP waiting times. Of note is the fact that the overall number of reserved slots (H + L) is less under the current practice of treating all IP as HIP than it is under the unconstrained policy. This is precisely the reason for including the constrained policy in the analysis, restricting the number of reserved slots to be the same as under current practice. The row with a limit of (an average of) 5 OT scans per day, demonstrates that the simulation results given earlier are a very good fit to the theoretical results presented here. The unconstrained policy under-performs in the simulation but this will be shown to be due to the lack of OP on call. Significantly, the current policy must increase the OT limit to 8 before throughput matches demand. In contrast, both the constrained and unconstrained policies require 44 an OT limit of 6 in order for throughput to match demand. At Vancouver General Hospital, CT technicians are paid time and a half for OT giving an approximate cost of $60 per hour of OT. Thus, assuming two technicians per scan, an increase in OT by half an hour costs $60 in technician salaries per day yielding a $15,000 cost over the year. However, if OT exceeds two hours then technicians are paid double leading to a cost of $80 in technician salaries for 2 scans yielding a $20,000 cost over the year. CT technician salaries are clearly only the most obvious cost associated with OT. Increased OT would also imply longer hours for CT support staff, radiologists and porters. Thus the true cost of increased OT is undoubtedly significantly higher. 7.2. Varying IP demand. In order to determine the effect of the IP demand rate on the growth rate in OP waiting time, we ran the simulation with the IP arrival rate being 60 per day and 90 per day. Capacity was set at five under the total demand rate while all other parameters remained the same. Figure 2.3 compares the effect on the growth rate in OP waiting time for the three reservation policies, optimized for the different demand rates. It is clear that reducing IP demand does not negate the benefit of the proposed reservation policy. Note also that the unconstrained policy is only outperformed by the constrained policy when the IP arrival rate reaches 120. This confirms the fact that the poorer results of this policy are due to having insufficient numbers of OP on call in order to take advantage of the flexibility provided by a policy with a large L value. 7.3. Vary ing the Percentage of L I P . As the percentage of LIP patients in-creases, the expectation is that the added flexibility would improve system through-put. To substantiate this we ran the simulation assuming that 20% of IP could be 45 F I G U R E 2.3. Varying IP Arrival Rate (Simulation standard error of 0.01) CD CD CD CO s J5* CD T 3 CD -—-0 . 5 0 . 4 5 0 . 4 0 . 3 5 0 . 3 0 . 2 5 0 . 2 0 . 1 5 0 . 1 0 . 0 5 0 • 9 0 % H I P - c o n s t r a i n e d D 9 0 % H I P U n c o n s t r a i n e d D 1 0 0 % H I P 6 0 9 0 1 2 0 I P A r r i v a l R a t e (# o f 1 5 m i n . s c a n s ) classified as LIP and with 100% of OP on call to determine the maximum benefit that might arise from an additional 10% LIP. Again we ran the simulation for the optimal unconstrained policy (H — 94, L — 35) together with the optimal constrained policy (H = 100, L — 19) and compared them to the current practice. The growth rate in OP waiting time was dramatically reduced (from .432 days/week to 0.018 days/week) with throughput coming very close to matching demand. This was ac-complished without increasing OT thus the improvement is due entirely to a reduction in unused capacity. 7.4. Varying Capacity. To determine the effect of increased capacity, we ran the simulation with the same initial conditions but increasing regular hour capacity. It is clear from Figure 2.4 that as capacity approaches demand the effect of in-troducing LIP becomes less pronounced though percentage wise the reduction in the growth rate in OP waiting time increases. Moreover, as capacity approaches demand 46 F I G U R E 2.4. Varying Capacity (Simulation standard error of 0.01) 0 . 5 0 . 4 5 "ST 0 . 4 -§0 .35 E 0 . 3 ' " 0 . 2 5 •j§ 0 . 2 "ro 50 .15 o 0.1 0 . 0 5 0 1 6 5 jifi pi||||il iii! 1B1I1H • M jjli HHii 0 9 0 % H I P H = 1 1 0 . L = 9 H 9 0 % H I P H = 1 0 7 , L = 1 5 • 1 0 0 % H I P H - 1 1 9 L - 0 ff MB i.•!s^ i . • 111 II^BIiH^Hi^B H '• • wm 1 1 1 6 7 C a p a c i t y 1 6 9 some of the benefit derived from introducing a LIP category is transferred from in-creasing throughput to decreasing OT. With a capacity of 169, the average OT per day for the three policies was 3.39, 2.92 and 4.84 respectively. Thus, even in a system that is meeting demand through OT, there is some benefit to introducing LIP. 7.5. Effect of Mul t ip le E x a m Lengths. The above results are based on the unrealistic assumption that all exams are 15 minutes long. In reality, scan lengths can be scheduled for anywhere from 15 minutes to 90 minutes (though scan lengths greater than 60 are rare). Thus, though it is possible to simply view a 60 minute scan as four 15 minute scans, the result is that arrivals now come in batches which would, of course, affect the theoretical calculations. To determine the effect of multiple exam lengths we ran the simulation with exam lengths varying from 15 to 60 minutes. For both OP and IP, we assigned 50% of total demand to 15 minutes scans, 30% to 30 minutes scans, 10% to 45 minute scans and the remaining 10% to 60 minutes scans. We adjusted the overall arrival rates so that the total demand on the resource was 47 T A B L E 2.6. Multiple Exam Lengths Comparison Average Constrained Policy Unconstrained Policy Current Practice H = 110 L = 9 +/- H = 107 L= 15 +/- H = 119 L = 0 +/-Daily IP Arrivals 120.03 0.16 120.03 0.16 119.95 0.16 Daily OP Arrivals 49.98 0.09 49.98 0.09 49.98 0.09 Regular Hour Scans 162.24 0.15 161.99 0.16 158.82 0.16 Overtime Scans 7.70 0.07 6.22 0.08 7.13 0.08 Unused Capacity 2.77 0.1 3.01 0.11 6.17 0.1 Throughput (Scans/day) 169.94 0.15 168.21 0.16 165.95 0.16 Weekly Growth in OP W T (days/week) 0.0048 0.01 0.186 0.01 0.433 0.01 unchanged at 120 scanning slots (of 15 minutes each) per day for IP and 50 scanning slots per day for OP. The results given in Table 2.6 show that the effect is to increase the advantage of introducing LIP to the system. However, once multiple exam lengths are added, the amount of OT increases beyond the allowable limit for all three policies considered. Again, the units are the number of 15 minute scanning slots. 7.6. Increasing O n C a l l Percentage. One of the challenges facing this pro-posed reservation policy is the need to have a pool of OP who are on 24-hour call - that is, willing to be scanned if given a call the night before. In a city the size of Vancouver, this is unlikely to be a major problem. To test the range of results possible for the different reservation policies, we tested both the constrained policy (H = 110, L = 9) and the unconstrained policy (H = 107, L = 15) with the on call 48 percentage being 0, 10, 20, 30 and 100 percent of the total OP demand. The resultant effect on the weekly growth rate in OP waiting times is given in Figure 2.5. FIGURE 2.5. Varying Percentage of OP On Call (Simulation standard error of 0.01) 0 . 9 O -I 1 1 1 1 O 1 0 2 0 3 0 1 0 0 P e r c e n t a g e o f O P o n - c a l l As per expectation, increasing the percentage on OP on call increases the benefit of the proposed system up to a point, after which it makes little difference. (Note that the policy (H = 110, L = 9) with 0% on call gives the same growth rate in waiting time for OP as the current practice of treating all IP as HIP.) Clearly, as the percentage of OP on call is reduced to zero, the effect on OP waiting times of introducing LIP is lost though there remains the advantage of reduced OT. In fact, for the policy (H = 107, L = 15), the effect is detrimental since the sum of H + L is greater than would be reserved under current practice. Conversely, if the percentage of OP on call is sufficient to take advantage of the flexibility provided by LIP, then the policy (H = 107, L = 15) is the most effective at reducing the growth rate in OP waiting time. However, the potential gain by using the unconstrained optimal policy is minimal and thus the more conservative policy (H = 110, L = 9) that insures that 49 you do no worse than under the current practice of treating all IP as HIP would seem to be the wiser option. The salient message however is that the percentage of OP on call does not need to be a significant portion of the total OP demand in order for the introduction of LIP to have a significant impact on OP waiting times. 7.7. Stochastic Service Times. The above results assume that a 15 minute scan takes 15 minutes which is, of course, highly unrealistic. For instance, at VGH, the time required for a scan is systematically overestimated. Thus unused capacity would be much higher than reported in the simulation. However, our proposal looks at reducing the number of scheduling slots that stand idle in a given day. The efficiency within each scheduling slot is another issue entirely and largely depends on aligning the actual scanning time required for a given exam with the time scheduled. The overall impact on OT that would result from introducing stochastic scanning times is not, in our opinion, a significant factor - provided scheduled times are a fair reflection of the actual required scanning time and provided that regular hour capacity is sufficiently large. If these two criteria are met then the law of averages will mitigate the effect on OT of introducing stochastic scanning times. Moreover, whatever the effect produced, it would be the same for each policy and therefore would not affect the comparison. To substantiate the above claim we ran the simulation with the same reservation policies but allowing for stochastic service times. We ran the simulation with the original parameters and allowed service times to follow a triangular distribution from 10 to 20 minutes. The results in Table 2.7 are almost identical to the initial results given in Table 2.4 with only a slight increase in OT. 50 T A B L E 2.7. Stochastic Service Times Average Constrained Policy Unconstrained Policy Current Practice H = 110 L = 9 +/- H = 107 L = 15 +/- H = 119 L = 0 +/-Daily IP Arrivals 119.97 0.09 119.97 0.09 119.98 0.1 Daily OP Arrivals 49.99 0.06 49.99 0.06 50 0.06 Regular Hour Scans 163.73 0.07 163.64 0.06 161.07 0.1 Overtime Scans 5.2 0.06 4.31 0.06 4.91 0.06 Unused Capacity 1.23 0.03 1.35 0.02 3.93 0.06 Throughput (Scans/day) 168.93 0.07 167.95 0.06 165.98 0.1 Weekly Growth in OP W T (days/week) 0.1 0.01 0.21 0.01 0.43 0.01 8. Implementation Challenges There are, no doubt, a number of implementation challenges associated with any attempt to improve a system through process modification. We briefly discuss a few of the more obvious ones. Firstly, our simulation assumes a five-day workweek whereas reality is somewhat different. V G H conducts OP scans Monday through Friday but performs IP scans 7 days a week. Since the weekends are only IP, the situation is actually better (favouring the proposed scheme over current practice) in that Monday starts off fresh with no carry over LIP and all of Friday's carry over LIP can be finished on the weekend (capacity is currently under-utilized on weekends). Our proposed scheduling scheme would therefore fit the current true situation with the only adjustment being that one 51 need only reserve H slots on Monday (as you know in advance there will be no LIP) and hence can book more OP for Monday. Secondly, though our own data collection suggests that a Poisson distribution is a reasonable fit to the data, this may not be true in other instances. It would be interesting to see the effect of running the simulation with different underlying arrival distributions. For instance, it could be argued that the Poisson does not represent enough variation. However, our simulation runs under the Poisson assumption with mean of 120 results in a standard deviation of about 11. Therefore three standard deviations to either side of the mean leads to a range of almost 70 slots per day. This seems to adequately reflect the fluctuation in demand we observed. Finally, it is worth noting that the introduction of multiple OP classes does not affect the results given in this paper. One can view the overall problem as two sub-problems. First, how much capacity does one need to reserve for IP in order to meet the required limits on OT? Second, given that one has set aside a certain amount of overall capacity for IP demand, how does one proceed to schedule the various OP classes into the remaining capacity? The optimal answer to the first question is entirely independent of the second. There are other implementation challenges (such as how no shows would affect the results) but none, in our mind, negate the fact that the introduction of the proposed reservation policy significantly increases throughput and reduces OP waiting times without increasing costs. 52 9. Conclusion The introduction of a low priority IP class does not represent a huge procedural change on the part of a CT department. It requires some careful thought on the part of the radiologists to insure that the appropriate IP are classified as LIP and it requires some additional phone calling on the part of the staff. There are no additional financial costs involved. The results of the simulation show clearly that introducing a one day flexibility to only 10% of IP demand provides a significant reduction in the growth rate of OP waiting times - even if only 10% of OP are willing to be on call. Varying the parameters of the simulation, as well as introducing variability in the duration of each scan, did not affect the ability of the proposed policy to improve throughput and thereby reduce OP waiting times. The proposal presented here applies readily to the CT operations that provided the impetus for this research. However, it could potentially be applied to any situation where there is a fluctuating demand and two or more priority levels (such as MRI-scheduling or operating room scheduling). The key is to determine whether there is any flexibility present in the high priority class and how to best exploit that flexibility. A potential application outside of health care might be the management and shipment of inventory. Inventory often involves multiple priority classes. The only question therefore is whether there is any flexibility in the scheduling of the higher priority class that is not currently being used efficiently. In the case of inventory management, Cattani and Souza compare a number of rationing policies in a scenario with two demand classes [13]. However, all of the policies only attempt to manipulate the lower demand class. Lawson and Porteus have demonstrated the advantage of allowing for the possible expediting of a shipment [32]. However, it might also be advantageous to 53 have a priority class that can potentially be delayed in order to insure that shipments leave with near full capacity. This would be analogous to the LIP category. The research in this chapter could be viewed as clearing the ground for the more complex problem with multiple OP priority classes. Imposing an OT limit, as pro-posed above, allows for the separation of the total capacity between IP and emergency on the one hand and OP on the other. However, though a directed search was suffi-cient to determine the capacity required for IP demand, it does not answer the issue of when to schedule OP - particularly if there are numerous priority classes. Chapter 3 addresses the issue of scheduling OP into the remaining capacity as well as deter-mining what action to take if the remaining capacity is not sufficient to maintain reasonable waiting times for the various OP priority classes. Chapter 5 will then expand the model in Chapter 3 to include IP demand and then compare the results with what has been presented here. There is no doubt that limited resources are going to continue to challenge the provision of health care. It would seem reasonable therefore to insure that we are using the resources that we have as effectively as possible which is precisely what the proposal outlined in this chapter attempts to do.1 lA version of this Chapter has been accepted for publication in Journal of the Operations Research Society. Patrick J . and Puterman M . Improving Resource Utilization through Flexible Inpatient Scheduling 54 C H A P T E R 3 D y n a m i c M u l t i - P r i o r i t y Pa t i en t Schedu l ing w i t h U n c e r t a i n D e m a n d 1. Introduction Chapter 2 simplified the scheduling process by assuming only one OP priority class. With only one priority class, there is essentially no scheduling issue for OP as one will simply allocate the first available slot within the capacity allocated to OP demand on a first come first served basis. However, if there are numerous priority classes then clearly there is reason for booking lower priority OP later than the first available slot in order to leave room for later arriving higher priority demand. It is this additional challenge that we seek to address in this chapter. We assume that total capacity has already been divided between IP and emergency demand on the one hand and OP demand on the other. We then seek to find the optimal scheduling policy for the capacity allocated to OP demand when there are multiple priority classes. Unfortunately, the optimization techniques used in chapter 2 are no longer useful in the setting where there are more than two priority classes. Thus, we resort to using (approximate) dynamic programming. 2. The Mode l 2.1. The State Space. We begin, therefore, by formulating the scheduling pro-cess as a discounted MDP. On any given day, the resource manager will have access to the schedule, as it currently stands from today to the end of the booking horizon, 55 as well as to the incoming demand waiting to be booked from each OP priority class. Thus the state space, S, takes the form: (x,y) = (xux2, ...,xN;y1,y2, ...,yi) where xn = the number of OP already booked on day n (xi = tomorrow's bookings), xn E { 0 , 1 , C } with C equal to the daily OP capacity, yi = the number of OP of priority i waiting to be booked, N = the maximum number of days one will book in advance, / = the number of OP priority levels. It is worth noting that C is the result of an earlier decision that divides the total capacity between IP and emergency demand on the one hand and OP on the other. 2.2. The A c t i o n Set. The resource manager's task is to decide on which day to schedule the incoming demand. In addition, there needs to be some mechanism for keeping the system viable even if there is not enough available capacity for waiting demand. There are at least three potential scenarios. In the first, the resource manager has the ability to reject demand if necessary. In the second, he can relieve the stress on the system by performing some scans through overtime (or through out-sourcing). In the third, the booking of demand can be postponed to a future date so that any unbooked scans appear in tomorrow's demand. Since this last option only postpones the problem, we concentrate on'the first two. Thus, a vector of possible 56 actions can be written as, (a, z) — {ajn, z{\, where din = the number of priority % OP to book on day n, Zi — the number of priority i OP to reject or serve through overtime. It is obviously undesirable to turn demand away or to perform extensive overtime so there needs to be a significant cost associated with these options. To be valid, any action must satisfy the following three constraints which insure that the capacity constraint is not violated, that all waiting OPs are booked and that actions are forced to be positive and integer. i (3.1) xn + ^ain<C Vn,n = l , . . . ,W i = l N (3.2) S£2,ain = y i - z t \/i,i = l,...,I • n = l (3.3) a,z > 0, integer Vi,i = l,...,I & Vn,n = 1 , N . Therefore, we can denote the action set for any given state by J N As,y = {{a,z)\xn + E ain < C1, E a™ = Vi~ zi> (5> ^) ^ °> integer}. i = l n = l 2.3. The Transition Probabilities. Decisions are made at the end of each day. The model is complicated by the fact that the horizon is not static but rolling with day 2 becoming day 1 and so on after each decision epoch. We assume that no OP can be booked more than N days in advance so that, at the beginning of each decision epoch, the Nth day has no bookings in it. Once a decision is made, the only stochastic element in the transition to the new state consists of the next day's incoming arrivals. 57 Thus the transition can be written as: {x1,x2, •••,xN;y1,y2, ...,yi) -> (x2 + ^ a i 2 , ...,xN + ^aiN,0;dx,dr) i = l t = l with probability = Il{=1p(dj) where p(di) is the probability that di OP of priority i arrive on a given day. Here we are assuming that the demand for one priority level is independent of the demand for another. This assumption is not strictly necessary but does make the mathematics easier. Nor does there seem any reason to doubt that it would be true since OP demand arises' from independent sources (the specialist doctors in the region serviced by the hospital). We are also assuming that demand from one day to the next is independent of each other. Again, though this does not seem unreasonable, it would be good to verify this in any application to real data. 2.4. The Cost Structure. The only remaining piece of information required for the optimality equation is the cost associated with a given state-action pair. The cost comes from two sources. First, a cost is incurred if an OP is booked later than the maximum recommended waiting time for the priority class in question. Second, there is a cost associated with rejecting demand or using overtime to serve excess demand. Thus, assuming a linear cost structure, we can write the costs as: i c(a, z) = ^ c(i, n)a i > n + ^ h(i)zi i,n i=l where, for example, c(i,n) = k(i)[n — T(i)]+, and k(i) is the daily penalty for an OP of priority i who waits longer than the maximum recommended time, T(i), h(i) is the penalty for rejecting or serving through overtime 58 an OP of priority i. The cost function c(i,n) reflects the fact that the cost associated with a late booking is only incurred if a patient from priority class i is booked past T(i) and thereafter a fixed penalty cost, k(i) is paid for each day late. It is reasonable to assume that both k(i) and h{i) are non-increasing in i. In fact, for the scenario where demand can be rejected, it seems reasonable to assume that h(i) is strictly decreasing in i and that for the scenario where overtime is used h(i) is constant since overtime costs are independent of the priority class. 2.5. The Value Function. The value function in the M D P is therefore the total discounted cost over the infinite horizon and satisfies the following optimality where 7 is the daily discount factor and D is the set of all possible incoming demand streams. Of course, it is here that we run into dynamic programming's greatest nemesis -'the curse of dimensionality' - since the state space is much too large to allow a direct numerical solution. In particular, the dimension of the state space is CNIM, where M is the maximum number of patients from a single priority class who can arrive on a given day. This is, of course, extremely large for any reasonable values of C, ./V, / and M and therefore does not allow the above DP to be solved by standard methods. equation: (3-4) v{x,y) = mm 59 2.6. A n Introduction to Approximate Dynamic Programming. There now exists a whole field of potential methods for dealing with precisely this problem, all of which are grouped under the title of approximate dynamic programming. These potential methods begin by restricting the value function to a certain class of functions and then seeking to find the "optimal" value function within this class. The question is how do you determine what class of functions to choose and how best to find the "optimal" approximate value function within the chosen class? The first question is still wide open but there are a number of available answers to the second. One possibility is to update the approximation via simulation. As an example of this tactic, consider approximate policy iteration using temporal difference methods. The process begins by assuming a certain form to the value function in the MDP that is dependent on a vector of parameters, f, and then fine-tunes the value of r via a simulated run, (s 0 ) S i , s2,s„), of the MDP generated by a fixed policy. To see how this works in detail, let us assume that the approximate value function can be written as v(s,r) where s is a member of the state space. Further, let <7(sfc, sfc+i) be the reward (or cost) for going from state Sk to state Sk+i and let A be a number between 0 and 1. The update to the parameter vector, r, following the transition to state Sk+i is written as: fe (3.5) r ^ + T d ^ A ^ V ^ r ) m=0 where dk is called the temporal difference (TD) and is equal to g(sk, Sk+i)+v(sk+i,r) — v(sk,r), 7 is the discount factor and where the gradient is taken with respect to r. Specifically, dk gives you the difference between your current estimate of the value function at state Sk and the one-step realization of the value of being in state Sk based 60 on the simulation run. A positive temporal difference therefore suggests that you have underestimated the value of being in state Sk and a negative temporal difference that you overestimated it. Intuitively, it makes sense that the value of r» should increase if and only if you have overestimated the value function (dk < 0) and the value function is decreasing in (Vi f (sfc, r) < 0) or else you have underestimated the value function (dk > 0) and the value function is increasing in (Vit>(Sfc,r) > 0). Assuming A = 1, this is precisely what equation (3.5) does except that the update is dependent not only on the transition Sk to Sk+i but on all transitions that have already occurred in the simulation run. The value of A allows one to discount the effect of a state the further away it is from the current transition. There are two sources of error. First, the approximation may not be able to capture the true value function adequately and secondly, the update of the parameter vector is based on a simulation run and is therefore open to sampling error. Once the approximate policy evaluation is complete and the approximate value function is available, a new policy is generated which is greedy with respect to v(s, r). Sometimes this can be done exactly while at other times we can only obtain an approximation to a greedy policy which opens this method up to a third source of error. Thus, we have a an algorithm that alternates between policy evaluation steps and policy improvements steps. A second possibility, and the one employed in this thesis, is to update the ap-proximation through mathematical programming. This approach was first developed by Schweitzer and Seidmann [49] with more recent work done by both Adelman and De Farias and Van Roy. The general idea is to transform the above MDP into the equivalent linear program (LP) and then assume some form to the value function 61 that makes the LP tractable. As mentioned earlier, choosing the appropriate form for the approximation is still an open question in approximate dynamic programming and requires a certain amount of ingenuity and insight into the nature of the prob-lem. One popular method is to pick "features" that best describe the problem as the basis for the approximation. The choice of "features" however remains a matter of judgement. 2.7. Approximat ing the Value Function. Dynamic Programming theory states that the above M D P can be transformed into the equivalent linear program of the following form: (3.6) max ^ a(x,y)v(x,y) x,y&S subject to (3.7) c(a,z) + 7 ^ I p{d)v I x2 + ^ a i 2 , ...,xN + ^ a i N , 0 ; d u . . . ,d 7 <?€£> V V i = l i = 1 ' > v(x, y) V(a, z) E ASig and (x, y) G S where a is a vector of positive numbers. The solution to the above LP will equal the solution to the optimality equation given in (3.4) for any strictly positive a [41]. Without loss of generality, we will assume that a is a probability distribution (over the initial condition of the state space). The conversion to a linear program does not, however, avoid the curse of dimensionality as the above LP has a variable for every state and a constraint for every state-action pair in the MDP. A possible solution is to approximate the value function, v, with a linear combination of basis functions 62 (see [2] and [15]). As a first attempt, we will use the following affine approximation: N (3.8) v{x, y) = W0 + Y^ Vnxn + J2 WiVi n = l i=l Vn can be interpreted as the marginal cost of booking a scan on day n and Wj can be interpreted as the marginal cost of having one more OP of priority class i waiting to be booked. We will impose the further restriction that Vn,n = 1,...,N and Wi,i = 1 , a r e non-negative while Wo is unconstrained. A working paper by Adelman [3] gives some reason for believing that for a M D P that consists of multiple sub-problems that are joined together by some linking constraints (as in our model), the choice of a linear approximation for the value function is reasonable. However, there is certainly no guarantee that this is the case and thus one resorts to determining the appropriateness of fit by analyzing the eventual outcome. Once we have chosen a form for the approximate value function, we can reformu-late the LP as the following: ( jv / > n = l i = l / subject to N n = l i=l d&D N-1 p{d) I W0 + Vn{xn+l + Y ai,n+i) + E W i d i \ n = l i = l i=l < c(d, z) V(d, z) £ AX:V and (x,y) e S V,W>0. 63 Rearranging terms and using the assumption that a is a probability distribution over the initial condition of the state space yields ( N I \ (3.10) max \W0 + T Ea[Xn}Vn + T E^W, \ subject to N / 1 \ 1 ( (1 - 7) W 0 + ^ V n [ x n - jxn+1 - 7 E a*> n + 1 ) + E W i ( V i ~ ^E<*lYil „ = 1 V i = l ' i = l V < c(a, i ) V(a, z) G As,g and (f, y) € 5 V,W>0 with = 0 and a , ^ + 1 = 0, for all i £ {1,...,/} and where Xn and are random variables representing the number of OPs already booked on day n and the number from priority class i waiting to be booked respectively. By E^p^n] we mean 2~2x ya(x' v)xn- However, it is reasonable to assume that a(x,y) = a(x)a(y) and that a(y) can be chosen to equal the demand distribution by priority class. Though we now have a linear program with a reasonable number of variables, the number of constraints remains intractable. This suggests solving the dual through column generation. Solving the dual has the advantage of a reasonable number of constraints but at the expense of creating an intractable number of variables - one for each state-action pair. Column generation solves this problem by starting with a small set S' of feasible state-action pairs to the dual and then (using the dual prices as estimates for W0, Vn and Wi) finding one or more violated constraints in the primal. It then adds the state-action pair(s) associated with these violated constraints into the set S' before re-solving the dual. The process iterates until either no primal 64 constraint is violated or one is "close enough" to optimality to quit. The dual of the above LP can be written as: (3.11) min ^ X(x, y, a, z) I c(i, n)ain + h(i)zj ^ (£,y)es \ i,n i = l subject to (3.12) ( I - 7 ) J2 X(x,y,a,z) = l (3.13) ^ X(x,y,a,z) xn - 7 x n + i - 7 y ^ n + i j > Ea[Xn] V r a = l ,...,iV (s,i?)es \ i = l (3.14) ^ X(x,y,a,z^(yi-'yEy\Yi\)>Ea\yi\ Vi = !,...,! (2,j7)6S (3.15) X > 0, where X ( x , y, a, z) is the dual variable associated with the state-action pair (x, y, a, z). In general, it may be difficult both to find an initial feasible set S' and to find a violated primal constraint. Fortunately, in this case, an initial feasible state-action pair for the dual consists of a state with no available slots and where all incoming demand is rejected or served through overtime. Finding a most violated primal constraint involves solving the following (tractable) integer program: 65 z(V, W) = min <,s,y)es I N / I N i,n i = l n=l \ i=l / N 1 / \ n = l i = l ^ ' subject to equations (3.1) to (3.3) as well as the predictable positivity and integrality restrictions on the state vectors x and y. Due to equation (3.2), we can eliminate the y variables and decompose the above minimization by day: N Z(V, W) = Y,bn + lYl WiE-\yi\ ~ (1 - 7 ) ^ 0 + J2 - Wi) Zi n = l i = l i = l where each bn has the form bn = min < ^ l c(h n) + 7 K - 1 - Wi] ai>n + [7K -1 - K i ] xn > V. 1=1 ) subject to xn + i = i x„ and a.,„ = ( a l n , a 7 „ ) > 0, integer with Vn-i = 0 and the optimal given by { 0 if Wi < h{i) M otherwise. (Recall that M is the maximum number of arrivals for each priority class on any given day.) The form of each bn has a nice intuitive interpretation. For each action, ain there are two potential costs and one benefit - the cost, c(i,n), associated with a (possibly) 66 late scan, a cost, 7Vr„_i, associated with a loss of available capacity tomorrow and a benefit, Wt, associated with removing some OP from the current demand. There is also a net loss or gain, jVn-i — Vn, in each day's value. 3. The Form of the Opt imal Approximate Value Function. Once we have solved the dual, the prices associated with each constraint give us the optimal value function approximation. What is perhaps surprising is that we can, under mild conditions, give the exact form of the optimal value function approx-imation in both the scenario with rejected demand and the scenario with overtime without having to solve the approximate LP. Of course, the approximate value func-tion outlined in the theorems below was not apparent initially and only suggested itself after extensive analysis of the optimal solutions to the approximate LP over a variety of parameter combinations. We present both theorems but defer the proofs to chapter 4. The first theorem gives the optimal value function approximation, over all approximations of the form given in equation (3.8), for the scenario where overtime is permitted. T H E O R E M 3.1. Assume that the cost of overtime, h(i), is the same for all priority classes and T(i) is strictly decreasing in i. If (3.16) k(i)[n - T(i)} + + -y n- TWh(l) > j T^- T^h(l) for all n > T[i) and for all i, and (3.17) £ 1 - A, + X ; 7 [ - ^ ) l + £ ; Q [ X n ] > T ( 1 ) C + - ^ -z—/ 1 — 7 L — ' 1 — 7 t = l ' 71=1 ' where \ — i?a[Yi] is the arrival rate for demand from priority class i, C is equal to capacity and 7 is the discount rate, then the optimal approximate value function 67 amongst all linear approximations for the discounted MDP will have the following form: • vn = 7 [ n - T ( l ) ] + ^ 1 ) fQr a U n e { i , . . . , • vN = 0 • Wi = 7 r « - r ( 1 > / i ( l ) for alii. • w0 = h(l)(-T(l)C-^ + 7 E L (The assumption that -E a[li] = \ is not strictly necessary but allows for some insight-ful interpretation below.) The above form of the optimal approximate value function has some intuitive appeal. From a cost standpoint, there is no difference between the days up to and including T( l ) , thus one would expect to value scanning slots on these days equally (Vn = Vn-\ for all n < T(l)). Thereafter, the value of a slot tomorrow is equal to 7 times the value of a slot today (Vn — ^Vn-\ for all n > T(l)) since a spot tomorrow will become a spot today by the next decision epoch. Both these expectations hold true in the above formulation. Equation (3.16) lends itself to numerous interpretations. If one sets i = 1 then the interpretation is that the cost of booking a patient on day n > T(l) and then performing an OT scan n — T(l ) days into the future is greater than the cost of performing an OT scan now. In other words, you do not benefit from postponing the need for overtime by booking patients late. For i > 1, the interpretation is essentially the same except that the cost of performing an OT scan now is discounted reflecting the fact that the slots freed up by booking a lower priority patient late are less valuable and therefore there is less incentive to do so. Alternatively, equation (3.16) can be interpreted as stating that the cost of booking a priority i patient on day n > T(i) plus the value of a scanning slot on day n is greater than the value of 68 a scanning slot on day T[i). In other words, the cost to the system is greater if you book late. Note that the more you value the future, the more likely that equation (3.16) will be satisfied. For example, with 7 = 0.9, it would only be violated if the cost of an OT scan is more than ten times the cost of a late booking. If 7 = 0.99 then the cost of an OT scan needs to be approximately 100 times that of a late booking before equation (3.16) is violated. There is little reason for a resource manager of a diagnostic facility to discount future costs (especially considering the time periods are days) and thus in the current application, the above condition will undoubtedly be satisfied for any reasonable values of k(i) and h(i). This is a significant result as k(i) may be extremely difficult to quantify exactly. Thus to know that the above form of the value function is the optimal approximation over a wide variety of potential cost parameter values lends much more credence to the results. Rearranging equation (3.16) yields the following condition on the ratio between the penalty for a late booking, k(i), and the penalty for OT, h(i). k(i) 7T W-ni ) _ y - r t t h(lj > k(i)[n-T(i)]+ ' Note that the right hand side is always positive and decreasing in n. Thus if this condition is violated for day m then it is violated for all n < m. If equation (3.16) is violated then the relative values of k(i) for each priority class i become important. Varying the relative values leads to any number of interesting policies that are willing to book patients from each priority class up to a certain number of days late before performing OT. However, once the late penalties get low enough then the emerging policy only uses overtime as a last resort. The closer the discount factor is to one, the quicker one reaches this "last resort" policy. For 7 equal to 0.99, there is essentially 69 only the two potential optimal solutions - the one given in the above theorem and one that sets all Vn and all Wi equal to zero (and thus uses OT as a last resort). Finally, in traditional DP theory, the solution to the LP is known to be indepen-dent of a provided a is strictly positive for all states [41]. However, in approximate DP, it is well known (see [1] and [15]) that this is not the case but the nature of the dependence of the optimal solution on a is not very well understood. Equation (3.17) provides the necessary bound on a in order for the optimal solution to have the desired form. The right-hand side can be viewed as the total available capacity in the infinite horizon setting. Since, capacity before day T(l) is equally valuable, dis-counting need only start on day T(l) + 1. Capacity after day T( l ) forms a geometric sequence with the first term equal to 7C and the ratio equal to the discount factor, 7. Thus, total capacity consists of the capacity available in the next T( l ) days, T(1)C, plus the capacity available thereafter, Demand too forms a geometric series (with ratio 7) and thus the first term on the left-hand side can be viewed as the total expected demand over an infinite horizon. Finally, if one views a as a probability distribution on the number of initially booked slots per day, then the second term on the left-hand side consists of a discounted function of the total capacity already in use. Thus equation (3.17) states that total expected demand plus expected initial bookings should be greater than total capacity. In other words, there must be reason to believe that one will have to use OT at some point. If a is chosen so that this con-dition is violated, the dual solution will yield an approximate value function identical to zero. This will of course lead to a myopic booking policy that places every patient into the slot that minimizes the immediate cost. 70 A similar analysis, for the scenario where demand can be rejected, yields the following theorem. T H E O R E M 3.2. Assume that the cost of rejecting demand, h(i), satisfies (3.18) h(i) > jT^-T^h(I) for all i < I and that T(i) is strictly decreasing in i. If (3.19) k(i)[n - T(i)]+ + 7"-T^/l(/) > ^~T^h(I) for all n > T(i) and for all i and (3.20) V 7 7 ~ r ( 1 \ + T^-T^+Ea[Xn] > T(1)C + then the optimal approximate value function amongst all linear approximations for the discounted MDP will have the following form: • Vn = 7"Vr(i)-r(/)/l(j) for a U n e _ > N _ i} • VN = 0 • Wi = jT^-T^h(I) for all i € { 1 , . . . , / } . W0 = *fw-nDh{I) ( - T(1)C - ^ + 7 E[=i ^ ^ A , ) where n\jT(l) = max(n, T(l)) . The intuition here is entirely analogous to the overtime scenario and thus will not be re-iterated. The difference between the two optimal approximate value functions stems directly from our assumptions on the cost structure for the two scenarios -namely that h(i) is strictly decreasing in i when demand is rejected but constant when overtime is used. 71 3.1. Determining the Scheduling Policy. The traditional LP method for directly solving an M D P provides the optimal policy by letting the probability of using action a in state s be equal to the value of the dual variable, X(s,a), divided by the sum of the dual variables over all possible actions in state s. The viability of this method depends on the fact that a direct solution to the L P will have at least one positive variable, X(s,a), for all states s. Since we solved the approximate LP through column generation, we only visited a very small percentage of all'possible states and thus we cannot derive a policy through the above method. However, we can perhaps gain some insight into the optimal policy by examining the optimal dual variables. If we assume that the optimal approximate value function has the form outlined in Theorems 3.1 and 3.2 then one result that emerges from the proof is that there are strict conditions on what state-action pairs can possibly have a positive dual value. Namely, for the scenario involving overtime, the dual variables can only be positive for state-action pairs satisfying: • xn + ain = C for all n < T(l) • Zi = 0 for a lH > 1 • aln = 0 for all n > T(l) • ain = 0 for a lH > 1, n ^ T(i). This suggests that the optimal policy will only ever use overtime for OP from the highest priority class (OP1). It also suggests that it will never book OP1 patients late and that it will book all other priority class patients on the last day that does not incur a cost. Similarly, for the scenario involving rejected demand, the dual variables can only be positive for state-action pairs satisfying: • xn + a\n = C for all n < T( l ) 72 • Zi = 0 for al i < I • a l n = 0 for all n > T( l ) • a,in = 0 for a l i i > 1, n ^ T(i). Again, this suggests that 0P1 patients should never be booked late and that the lower priority classes should be booked into the last day that does not incur a late penalty. It also suggests that only the lowest priority class should ever be rejected. However, since we did not visit every possible state, this falls short of providing a full policy. For instance, what should a resource manager do when faced with a situation where there is not enough OP1 demand to fill all available slots before day T(l)? Or what should the resource manager do if there is not enough space available on day T(i) to meet all waiting demand from priority class i? Thus, we need an alternative method for deriving a booking policy from the optimal approximate value function. Fortunately, this can be done straightforwardly. Given the approximate value function, one can find the optimal action, (a, z), for any given state, (x,y), as needed, by solving the following tractable integer programming problem (VQ = 0): , I N I (3.21) min I 53 53 n K , n + 53 h(i)zi (s,2)eAS i j, L . = 1 n = 1 . = 1 deD N W° + J2 Vn{Xn+l + O i , n + l ) + 53 W i d i 71=1 1 = 1 1=1 f N 1 1 \ — min \ 53 5Z n ) + 7 K - i ) HN + 53 W)* + constant \ subject to equations (3.1) to (3.3). Thus, the logical means of testing the usefulness of the approximate value function is to allow equation (3.21) to determine the booking 73 policy in a simulation of the scheduling process. The results are given in the next section. 4. Simulation Results The coding of the column generation required to solve the approximate LP was done in A M P L with C P L E X as the solver. Time to solution was less than five minutes and involved between 300 and 500 columns for any problem with a booking horizon of 30 days and the average number of arrivals less than 120. (Solving larger instances is quite feasible but we did not explore any bigger than this.) The simulation of the scheduling process was also done in A M P L / C P L E X as it involves solving the integer program given in equation (3.21) with constraints (3.1) to (3.3). We ran the simulation for 20 000 days with a warm-up period of 5000 days (that is statistics are not collected until day 5001). 4.1. A Small Hospital Setting with Rejected Demand. We initially present the scenario where the resource manager may choose to incur a cost in order to reject some demand. The results are based on a small hospital with a capacity for 10 OP scans per day and with 3 OP priority classes. The booking horizon is set at 30 days and demand is assumed to be Poisson with means 5, 3 and 2 for each priority class respectively. In reality, we need to truncate the Poisson distributions in order to keep the state space finite. However, one can set the maximum daily arrivals for each priority class large enough so that the probability contained in the truncated tail of the Poisson distribution is vanishingly small. Setting demand equal to capacity seemed the most reasonable choice given our objective. If demand is less than capacity then optimal scheduling is not as essential as it might be (though obviously it would 74 still be useful to schedule as optimally as possible due to variation in demand). If demand is set greater than capacity then rejection or overtime costs will simply be higher. In theory, since one does have some leeway in booking, a scenario where capacity and demand are equal might seem to be manageable, however variability in demand generally causes this not to be the case. The daily cost for a late scan is set at 3, 2 and 1 for each priority class and the cost of rejection at 10 more than the cost of booking on day 30. In other words, it is more costly to reject a higher priority OP than a lower one and it is always more costly to reject than to book (ignoring the cost associated with a loss of capacity). These "costs" are essentially costs to patient health rather than financial costs. The maximum recommended waiting time by priority class is 7, 14 and 21 days respectively. The discount rate is .99 as one does not want to sacrifice the future for the present. Using equation (3.21) together with the action constraints (3.1) to (3.3), we can determine "optimal" booking actions for a simulated random demand. Perhaps sur-prisingly, the optimal solution results in a simple heuristic policy. First, fill any unused capacity available for tomorrow (since this capacity will be lost if not filled today). Second, if possible, book any remaining priority 1 OP some time in the first week (otherwise on the first available day) but book lower OP classes into the latest available day that does not incur a late penalty (i.e. for % > 1, book priority i OP on day T(i)). Finally, periodically reject a certain percentage of demand from the lowest priority class. Note that this policy confirms our initial conjectures based on the optimal dual variables. Under such a scenario, the above booking policy manages to keep waiting times within the recommended lengths but only at the expense of rejecting around 13% of all 75 priority 3 OP (see Table 3.1). This works out on average to roughly one rejection every 4 days (though of course rejections do not occur uniformly but rather come in spurts). Unfortunately, it does not seem possible to provide the conditions under which these rejections occur without solving the integer program. Thus, implementation of this policy depends on the availability of software capable of solving the integer program. Figure 3.1 shows the waiting times by priority class for the above policy. F I G U R E 3 . 1 . Waiting Time With Rejection by Priority Class 40000 Q. o ° 30000 E ^ O P 1 B O P 2 D O P 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2 2 23 24 25 2 6 2 7 28 2 9 30 Days If we run the same policy but rejecting only if absolutely necessary, then the results are dramatically worse with over 50% of priority 1 OP being late as well as significant portions of the lower priority classes (see Table 3.1). It is worth noting that, in almost all cases, this is the policy that emerges if the conditions given in Theorem 3.2 are not satisfied. It is also worth noting that the current practice of simply postponing the booking of any demand that cannot be met will in fact perform worse than the "reject as last resort" policy. The only reason costs do not tend to infinity when demand is postponed is that, in reality, demand is negatively correlated with expected waiting 76 time. Thus, in fact, there is implicit rejection of demand occurring under current practice, but the decision as to when to reject demand is being made not by the resource manager but by the specialist doctors who recommend the OP scans in the first place. Our current model does not capture the dependence of demand on expected waiting time but could be adapted at a later date to do so. A possible alternative policy is to impose a strict booking limit on top of the above policy (again rejecting patients only if absolutely necessary). To that end, we ran the above booking policy but enforced the condition that an OP of lower priority would only be booked on a given day if the number already booked on that day did not exceed a pre-specified value. Clearly that number would decrease the lower the priority class. As long as the capacity and the number of priority classes is not too large, the optimal booking limits to impose can be determined through simulation since there are only a relatively small number of options. The resulting optimal booking limits for the scenario outlined above is to place no restriction on the priority 2 class OP but to restrict priority 3 class OP to only one a day. (Of course, there is no reason to place a booking limit on tomorrow's bookings as those scanning slots will be lost if not filled today.) While coming close to matching the results of the initial policy, the booking limit policy manages to maintain reasonable waiting times only by rejecting 21% of all priority 3 OP and booking half of those OP3 that it accepts late (see Table 3.1). The fairly intuitive message is that the optimal solution is to closely restrict the lowest priority class in order to allow room for later arriving higher priority demand. Moreover, the above suggests that restricting the lowest priority class in a dynamic 77 T A B L E 3.1. A Comparison of Three Scheduling Policies Policy % Late % Rejected Daily Cost OP1 OP2 OP3 OP1 OP2 OP3 Total Optimal DP Approx. 0.10 0 0 0 0 12.85 2.58 4.89 Reject as Last Resort 53.17 35.77 24.85 0.08 0.43 0 0.17 119.00 Booking Limit 0 0.02 49.52 0 0 20.57 4.13 15.00 T A B L E 3.2. Optimal Approximation Policy with Increasing Rejection Costs Rejection Cost % Late % Rejected Average Daily Cost OP1 OP2 OP3 OP1 OP2 OP3 Total 19 0.01 0 0 0 0 12.85 2.58 4.89 109 0.56 0.27 69.10 0 0 12.25 2.46 39.20 1009 49.06 88.84 95.40 0.02 0.35 0.28 0.17 170.35 fashion rather than placing a static booking limit can be more efficient in the long run. As one would expect, increasing the cost associated with a rejection has the effect of hampering the ability of the booking policy to maintain reasonable waiting times. Table 3.2 presents the impact of increasing the cost of rejection to 100 and 1000 above the cost of booking a priority / patient on day N. Note that condition (4.14) in Theorem 3.2 is violated in the bottom two instances and thus a different policy emerges than the one mentioned earlier. In fact, in the second instance, condition (4.14) is violated for i = 3 but not for i < 3, thus essentially leading to a policy that is only willing to book the lowest priority class late. In the 78 third instance, condition (4.14) is violated for all i and thus we get the "reject as last resort" policy. There are two obvious difficulties with implementing such a model in practice. First, how does one determine the "cost" of a late scan? Clearly, the direct cost is to patient health but that is next to impossible to accurately quantify. The second difficulty is that rejecting patients outright may not be a viable option. 4.2. A Small Hospital Setting wi th Overtime Available. The second sce-nario where z represents the number of OP served through overtime addresses both of these difficulties simultaneously. In this scenario, the cost of rejection can be set as the cost of an overtime scan. In essence, this is a means of deliberately overbook-ing. It would be the task of the policy makers to suggest a second date, T'(i), for each priority class, that would correspond to the point at which the late costs equal the overtime cost. (Incidentally, T'(I) would also give you the length of the book-ing horizon.) The daily "cost" of a late scan could then be determined by setting k(i) at such a level that by the time you are booking T'(i) days in advance (but not before), the late costs outweigh the overtime costs. Such an explicit formulation of the late penalty is not strictly necessary as one could still leave these costs arbitrary. The emerging optimal policy will remain the same provided the late penalty is large enough to satisfy condition (3.16) in Theorem 3.1. Recall that the cost structure in this case is significantly different as the overtime costs are independent of the priority class. Once again we get the surprising result that the optimal solution results in a simple heuristic booking policy. First, fill any unused capacity available for tomorrow. Second, if possible, book any remaining priority 1 OP some time in the first week. / / 79 T A B L E 3.3. Impact of the Overtime Policy Overtime % Late % served through O T Average Cost O P 1 OP2 O P 3 O P 1 OP2 O P 3 Total Dai ly Cost 30 0 0 0 1.56 0 0 0.78 2.33 90 0 0 0 1.44 0 0 0.72 6.46 150 0 0 0 1.51 0 0 0.76 11.31 no space is available, serve any remaining priority 1 OP through overtime. Continue to book lower priority OP on the last available day that does not incur a late penalty (i.e. for i > 1, book priority i OP on day T(i)). Initially, we assume a cost of thirty dollars for an overtime scan (the cost associated with the overtime salary of two CT technicians for a 15 minute scan) and that an additional wait beyond T(i) of 5, 10 and 15 days for each priority class respectively equates to the cost of overtime. Thus the daily cost for late scans for each priority class is 6, 3 and 2 respectively. Note that unlike the the rejection scenario costs are now related to an objective dollar figure. Patient health is still taken into account by determining how many days passed the recommended limit equates to overtime cost. The resulting effect on the performance of the linear approximation is given in Table 3.3 along with the performance when the cost of overtime is increased to 90 and 150. Note that all other parameters are identical to the scenario outlined initially. Table 3.3 suggests that the above policy results in one and a half percent of priority one OP being served through overtime which, over 15 000 days, is roughly 1000 patients or one every 15 days. Thus, if overtime is available, one can maintain reasonable waiting times by removing a small proportion of the highest priority class. Note that the same policy emerged for a wide range of potential costs associated 80 with overtime. Thus, it is clear that performing a very small proportion of the high priority demand through overtime in order to remove some of the strain on a system can dramatically improve waiting times. Figure 3.2 shows the waiting times by priority class when overtime is allowed. F I G U R E 3.2. Waiting Time With Overtime by Priority Class O 2500O "o § 20000 E10P1 • O P 2 n O P 3 r i ll. . I I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3 0 Days The next section seeks to show that these results extend to a larger hospital as well as to a variety of potential demand streams. 4.3. A Large Hospi tal Setting. A hospital such as the Vancouver General Hospital has a capacity of more than 30 OP scans per day. Data available from V G H only provided us with the number of OP scans by priority class per day. It did not give us the length of each exam requested. Thus, though most OP scans are only 15 minutes, the reality is that using 30 scans per day is an underestimate of the actual OP demand for 15 minute scanning slots. This will become more of an issue in Chapter 5 when we extend the model to include IP demand as the length of IP scans varies from 15 minutes to 90 minutes. Nonetheless, increasing the daily capacity to represent a larger hospital with 30 scans per day did not greatly affect 81 T A B L E 3 .4 . Capacity of 30 Scans per Day % Late % Removed Dai ly Cost O P 1 O P 2 O P 3 OP1 OP2 O P 3 Total Rejection 0 0 0 0 0 2.43 1.46 6.92 Overtime 0 0 0 0.33 0 0 0.2 4.51 the results as shown in Table 3.4. ("Removed" simply refers to OP who were either rejected or served through overtime depending on the scenario.) The one advantage is that the increased capacity meant that the required percentage of OP served through overtime was significantly smaller. We tested the initial "reject" policy with rejection costs equal to 10 more than the cost of booking on day N and the overtime policy with OT costs set at 90. Demand was still assumed to be Poisson but with mean arrival rates of 15, 10 and 5 for each priority class respectively. These results would suggest that the policy using overtime is less sensitive to Changes in capacity than one based on outright rejection. This robustness of the overtime policy is further underlined if one increases the percentage of OP demand coming from the lower priority classes. (The data we have from the Vancouver General Hospital suggests that the larger demand does actually come from the lower priority classes.) Figure 3.3 compares the average cost for various arrival streams in the case of outright rejection and overtime. Clearly, the rejection policy fares worse the larger the percentage of the OP popu-lation coming from the lowest priority class. The overtime policy, on the other hand, fares reasonably well regardless of the relative frequency of each priority class. 82 F I G U R E 3.3. Average Cost for a Variety of Demand Streams • M=15, A2=10, A3=5 • A1=10, A2=10, A3=10 • A1=5, A2=15, A3=10 • A1=5, A2=10, A3=15 Reject P o l i c y 5. Conclusion The above analysis suggests that without some reasonable means of removing some portion of demand (be it through overtime or through outright rejection), a system where demand is equal to (or greater than) capacity wil l run into serious waiting time challenges. The questions facing a resource manager are how much de-mand must be removed (either through overtime or rejection) as well as what type of demand (which priority class) and when to remove it. Through the use of approx-imate dynamic programming, we have been able to answer these questions for any reasonably sized hospital - a feat that would have been impossible through traditional dynamic programming. Of course, the "cost" is that we had to approximate the orig-inal M D P and thus our solution may in fact be sub-optimal. However, our results suggest that even our approximate results are a substantial improvement over cur-rent practice. Moreover, the value functions derived through our approximation yield easily implementable policies that maintain reasonable waiting times while removing 83 only a small percentage of demand both in the case of overtime and of outright re-jection. We further showed that if overtime is available then it is the highest priority class whose demand is occasionally removed while if one has to reject demand then it is the lowest priority class that is culled. Finally, from a policy point of view, the use of overtime has shown itself to be more robust than outright rejection (as a means of maintaining reasonable waiting times for minimal cost) over a variety of capacity constraints and demand streams. To implement the policies presented here the only necessary data is the arrival distribution of patients by priority class as well as the available capacity, the length of the booking horizon and the maximum recommended waiting times for each class. The resource manager must also agree on the appropriate cost structure (overtime vs. rejection, late booking penalty). One would also need to ascertain that the assumption of independence between demand from various priority classes and between demand on successive days is verified. If it turns out that there is a "day-of-the-week" effect then this may alter the results. There is nothing in the results that depends on the Poisson assumption so alternative arrival distributions should lead to the same results. Current practice seems to largely depend on postponing demand (by booking further and further in advance or else postponing booking altogether). However, this only compounds the problem. The research in this paper strongly suggests that it is possible to prevent the need for expanding wait lists by judiciously performing very minimal amounts of overtime in order to prevent congestion. Since we used approximate dynamic programming, it is certainly possible that one might be able to do better if one knew the true value function in the MDP. The next 84 Chapter will provide, along with the proof for Theorems 3.1 and 3.2, a discussion of the potential gap between the what is achieved through the above approximation and what might have been achieved had the original MDP been tractable.1 1A version of this Chapter will be submitted for publication in OR. Patrick J . Puterman M . Queyrannne M . Dynamic Multi-Priority Patient Scheduling with Uncertain Demand 85 C H A P T E R 4 The Optimal Approximation and Bounding the Optimality Gap 1. Introduction Presented in this chapter is a proof of the form of the optimal approximation to the value function (amongst the set of linear approximations): V(x, y) = W0 + V"x" + E W i V i n = l i = l We analyze both the scenario where OT is an option and the scenario where demand can be rejected. The cost of an OT scan is assumed to be independent of the priority class while the cost of rejected demand is assumed to be decreasing in i. We assume both OT/rejection costs and late booking costs are linear. In both cases, the max-imum recommended waiting time, T(i), for each priority class increases with i as a high priority patient is a patient who must be served sooner. After presenting the proofs, we provide a discussion of the "cost" associated with having approximated the value function and present a more complicated approximation based on a convex formulation. For completeness, we restate the theorem before giving the proof. 2. The Form of the Optimal Policy with Overtime T H E O R E M 4.1. Assume that the cost of overtime, h(i), is the same for all priority classes and T(i) is strictly decreasing in i. If (4.1) k(i)[n - T(i)}+ + 7n-T^h(l) > 7 T W- T ( 1 >/i(l) 86 for all n > T(i) and for all i, and (4.2) i 7r(i)-r(i) N E iz—Xi + E ^ l B " T ( 1 ) 1 + £ 7 « w > T W C + 1 -'-1 7 71=1 i=l 7 where A; is i/ie arrival rate for demand from priority class i, C is equal to capacity and 7 is the discount rate, then the optimal approximate value function amongst all linear approximations for the discounted MDP will have the following form: • Vn = ^n~ T^ +h(l) for allnG {l,...,N - 1} • VN = 0 • Wi = 7T W - r ( 1 ) / i ( l ) for alii. . WQ = M D ( - T(l)C - £ + 7 E l i ^ A . ) , Proof: The outline of the proof is as follows. We first assume the above form to the value function and show that it gives a feasible solution to the primal LP. We then construct a dual solution that together with the above primal solution satisfies complementary slackness. We do this by determining what state-action pairs result in the primal constraint being tight and then constructing a dual solution that is only positive for this set of state-action pairs and for which all dual constraints are tight (since our primal solution is positive except for VN)- This construction is sufficient to prove the optimality of the above primal solution [7]. We begin therefore by proving the feasibility of the hypothesized primal solution. Clearly, it gives non-negative values for V and W. Recall that the constraint for the primal LP can be written as: 87 N ( 1 \ (1 - l)W0 < J3 ( E n ) + ^ n - 1 ~ W^ ai>n + ^Vn~l ~ ^ X n j „ = i V i = i / + 7 53 WiE^il + 53 (h(i) - Wi) Zi i = l i = l Note that y does not appear in the equation as we have made use of the fact that Vi = En=i ain + zi f ° r a u * £ {1) Substituting the hypothesized solution into the primal constraint and assuming that . E a [ Y i ] = A ; (again not necessary but helps with the interpretation) yields: / T ( l ) (4.3) (1-7) Wb < - 53 7 T ( i ) - T ( 1 ) ^ ( l ) a i i - h(l)Xl - 53(1 - -y)h(l)xn i = l n=2 + f ^ (fc«[n - T ( T ) ] + + 7 [ " - r W - 1 l + « / l ( l ) - T ^ - ^ I M I ) ) ^ , , n=2 t= l ^ ' I I + 53 7 r w- r ( i )+ i / l ( i ) A . + 53(/l(i) _ 7 n o - m ) / l ( 1 ) ) ^ i = l i = l for all (a, z) € A^:g and (x, y) € 5. This follows from the fact that V-i = 0 and 'yVn-i — Vn — 0 for all n > T( l ) . To prove primal feasibility, we simply need to show that the above definition for W0 satisfies equation (4.3) when the righthand side (RHS) is at its most negative. Fortunately, we can find a state-action pair that minimizes the RHS on a day to day basis. For each day the choice is between filling the day with previous bookings (xn) and/or with new arrivals (aj„) or simply leaving the day empty. For n = 1, the coefficient in equation (4.3) for x\ is at least as negative as the coefficient for an with equality only if i = 1. Thus, any state-action pair minimizing the RHS will have x\ + an = C. In other words, we are indifferent between states where day 1 is fully booked with some combination of previous bookings and current priority 1 arrivals. For n = 2, ...,T(1), we know that k(i)[n — T(i)]+ = 0 for all i. Thus, by inspecting the coefficient for xn, any state-action pair minimizing the RHS, will have xn = C if (1 — 7) > 7 T W - T ( 1 ) — 7 which is clearly true for all i with equality for i = 1. Again, in the case of i = 1, we are indifferent between any state where day n is fully booked with some combination of previous bookings and current priority 1 arrivals. Thus any state-action pair that minimizes the RHS will have xn + ain = C for all n < T( l ) . For n > T( l ) , the coefficient for ain in equation (4.3) equals zero at n — T(i) for each i > 2. If n < T(i), the coefficient is clearly positive for each priority class since 7 < 1. On the other hand, if n > T(i) then equation (4.1) insures that the coefficient is also positive. Thus, any state-action pair minimizing the RHS of equation (4.3) will have ain = 0 for all n ^ T(i),i > 1. Moreover, it will have aln = 0 for all n > T( l ) . The term in equation (4.3) involving the OT actions, Zj, implies that any state-action pair minimizing the RHS will have z* — 0 for a l H > 1 and that, again, we are indifferent in the case of i = 1 (though z\ can only be as large as the number of waiting priority 1 patients). Using the above conditions on the set of state-action pairs minimizing the RHS of equation (4.3), one can show that W0 has the proposed form by computing equation (4.3) with the appropriate values for a, x and z. Moreover, we have demonstrated that 89 the proposed primal solution will have tight constraints only for those state-action pairs satisfying the following conditions: • xn + a l n = C for all n < T( l ) • Zi = 0 for a lH > 1 • ain = 0 for all n > T( l ) • ain = 0 for a lH > 1; n ^ T(i). Thus, complementary slackness implies that the optimal dual solution must be zero for state-action pairs that do not satisfy the above conditions. The next step is to construct a feasible dual solution, X(x,y,a,z), with the above properties so that we have a primal-dual pair satisfying complementary slackness. Since the primal variables given above are all non-zero (except for Vjv), this implies that the dual constraints must all be tight (except for the one associated with day N). If we can find such a dual solution, we will have proved the optimality of the constructed primal-dual pair. In fact, we will impose the further restriction that a dual variable is positive only if, for all i and n, xn and ain equal zero or C. Let (s,a) = (x, y, a, z) represent an arbitrary, feasible state-action pair and let B = {(s,a)|X(s,a) > 0}. Recall that the dual constraints have the form: (4.4) (s,a)€B (4.5) (s,a)€B ) >Ea[Xn) Vn = l , . . . , i V (4.6) (s,a)€B (4.7) X > 0 V(s,a) e S x A. 90 Concentrating on equation (4.5), we know that Ea[Xfli] should be zero since at the beginning of each decision epoch day iV stands empty. Thus, we need not put weight on state-action pairs with non-zero. Thus, for n = N — 1, equation (4.5) yields £ X(s,a)(xN_1) = Ea[XN_1}^ £ X(s,a) = E a [ X c N - l ] . (s,a)€B (s ,a )6B ZJV-1>0 Further, for n = N — 2, equation (4.5) yields 53 X(s,a)(xN-2 - 7 Z N - 1 ) = - E a [ X A T _ 2 ] (s,a)€B => 53 ^(s,a)(x N _ 2 ) - 7 5Z ^(s,a)(x^_i) = Ea[XN-2] (s,a)eB (s,a)eB 53 X(s,a) = ^ I ^ l + 7 53 X(s,a) (s ,a )6B (s ,a )6B * N - 2 > ° xjv_i>0 = ^ ^ a [ a r j v - 2 ] + 7 ^ - l ] ) . Proceeding similarly, for arbitrary n, we get (4.8) 53 X(s,a) = + 7 £ X(s'a) = h E ( s , a ) £ B (s ,a ) eB m = n i n > 0 z n + i > 0 This would be for the case for all n > T(l) except that bookings can occur for ' lower priority classes on each T(i). Thus, for n — T(i) — 1, there is the added complication that bookings may be made on day n + 1. This leads to 53 ^ ( s , a ) ( x T W _ i - 7 x T ( i ) - 7ai,r(i)) = Ea[XT(i)-i] (s,a)eB =^ C7 53 X ( s , a ) - 7 C 53 * ( s , a ) - 7 C 5Z X ( s ' a ) = Ea[Xm-i). ( s , a ) € B ( s , a ) e B (s ,a ) eB * T ( i ) - l > 0 x T ( i ) > ° a i , T ( i ) > 0 91 However, since Zi = 0 for all i > 1 and ain = 0 for all n ^ T(i), equation (4.6) yields C X(s,*)= X(s,a)yi = ^-X l \r- D /_ _ \ r> 7 ( s , a ) € B (s,a)€B o i , T ( t ) > 0 ( s , a ) e B a i , T ( i ) > ° 1 \ A i C Thus, (4.9) J2 X ( s ' a ) = £ (^«[^r ( i ) - i ] + Y Z - ^ + 7 £ *(s,a) (s,a)eB V 7 / (s,a)€S ^ T C O - l 5 " 0 . * T ( i ) > ° 1 / N \ = - ( ^ [ X ^ ] + £ 7 m - T ( i ) + 1 ^ [ o ; m ] + 73—Ai ^ m=T(i) ^ ' and, in general, for n > T( l ) , (4.10) £ X(s,a) = i ( £ 7 m - " ^ [ ^ m ] + 7 ^ £ 7 ! T W - n ! + / T W > n A i (s,a)efl ^m=n ^ i=l where Ix(i)>n equals one if T(i) > n and zero otherwise. Finally, for n < T(l),aln may be non-zero. So, equation (4.5) yields: £ X(s,a)(xn - 7 x n + i - 7ai,n+i) = Ea[Xn] (s,a)€S C £ X ( s , a ) - E a [ X n ] + 7 c ( £ X(s ,a)+ £ X(s,a)Y ( s , a ) € B ^ ( s , a ) € B ( s , a ) € B ' i r l > 0 r r n + 1 > 0 a i , n + l > ° However, not all of priority 1 patients are necessarily booked on the same day. This would make the system unsolvable but for the fact that we know that a ; n + 1 +a i i n + i = C • 92 for all n € {0, ...,T(1) - 1} and for all (s,a) e B. Hence, equation (4.4) yields ( s , a ) S B ( s , a ) € B a l , n + l > ° x n + l > ° Therefore, (4.11) £ X ( s , a ) ( s , a ) 6 B x n > 0 Thus equations (4.10) and (4.11) give the amount of dual weight that must be placed on each day in order to satisfy complementary slackness as well as dual feasi-bility. Al l weights are positive and none are greater than the total available weight I 1-7' To determine the dual weight to be placed on sate-action pairs with positive z\, we make use of the fact that = ^ + _ y _ forn<T(1) C 1—7 1 - 7 (s,a)£B 93 from equation 4.6. Therefore, r(i) A / A E *(s,a)*i = - 53 ( E -*(s»a)alitl J >,a)eB ^ n=l ^ (s,a)6B ' ' 71=1 X ' (s,a)gB / Ai CT(1) r r 7 + c ( E 1 - 7 1 - 7 v n = 1 L T(l)-1 r Ea[Xn] 7 C 1 - 7 . 53 ..n-rfn-^a^n] | ^ .,r(Q-r(i) 1 X7i=T(l) ^ t=2 \1 1 _ 7 1 _ 7 1 _ 7 ^ ^ l - 7 / T(i)—T(l) r< N - E V^Ai - ^ - ^ + E 7 | - T < 1 ) l + ^ [ ^ ] -• =1 ' ' 71=1 Thus, (4.12) £ X{s,a)Zl = £ ^ ^ A , - T(1)C - ^ - + jh-y[n-T{1)]+Ea[Xn} (s,a)£B t=l 7 7 n=l which is greater than zero by equation (4.2). It is worth noting that simply for dual feasibility, we would only need the above to be greater than or equal to zero. However, if equation (4.12) were to be identically zero then we would have degeneracy and the proposed primal solution would no longer be unique. In fact, the optimal objective function would be zero suggesting that an approximate value function identical to zero would be optimal. The above argument suggests a weighting scheme for a dual feasible solution that, together with the proposed primal solution, satisfies complementary slackness. It remains to show that it is possible to construct positive dual variables satisfying the 94 above weighting scheme. However, since there are a near infinite number of state-action pairs (much greater than the length of the booking horizon plus the number of priority classes) and since one can choose to fill (or not fill) each day separately, finding a set of state-action pairs that will satisfy the above weighting scheme must, in fact, be possible - however difficult it may be in practice. A possible algorithm for determining such a dual solution would be the following: • Begin with a state-action pair with days 1 to N—1 full with previous bookings and with z\ equal to the maximum number of arrivals for priority class 1. • Assign weight to this state-action pair equal to the required weight for states with X J V - I positive. • Create second state-action pair identical to the first except with day N — 1 empty. • Give this new state-action pair weight equal to the required weight for states with XN-2 positive minus the weight already assigned to the first state-action pair. (If the assigned weight is negative simply make day x/v-2 equal to zero in first state-action pair and assign weight to current state-action pair equal to the required weight for states with x^-2 positive.) • Proceed similarly removing one day from the set of previous bookings each time. • Whenever the required weight for states with positive z\ is reached, split the current state into two with the only difference between the two being that one will have Z\ equal to the maximum arrivals for priority class 1 and the other will have z\ = 0. Assign to the first the additional weight needed to 95 meet the required weight for states with positive z\ and the remainder to the second (At what point this will happen cannot be known a priori). • As soon as day Si,r(i) is empty in the new state-action paper add in the action • Whenever the required weight for states with positive a ^ i ) is met, repeat the process outlined above for z\. • Repeat all the way down to a state that has previous bookings only on day one. • Add one final state-action pair that has no previous bookings but has a 1 ) 7 l = C for all n < T( l ) . Assign weight to this state-action pair equal to 1/(1 — 7) minus the total weight already assigned. This algorithm is not terribly illuminating but does provide assurance that a dual solution of the above form can be found which is enough to conclude the proof. 3. The Form of the Opt imal Policy wi th Demand Rejection Turning now to the scenario where some demand can be rejected and where it is assumed that it is more costly to reject higher priority patients, we restate the analogous theorem to the one given in the scenario involving OT. THEOREM 4.2. Assume that the cost of rejecting demand, h(i), satisfies a, •,itT(i) equal to C and proceed as before. (4.13) h(i) > 7TW-r(/)/l(j) for alii < I and that T(i) is strictly decreasing in i. If (4.14) k(i)[n - T(i)] + + r- T{I)h(I) > 7 T ( i ) - T ( / ) M / ) 96 for all n > T(i) and for all i and (4.15) j ^ f ^ K + j^ 7[n~TW]+Ea[Xn] > T ( 1 ) C + I ^ -i=l ^ n=l then the optimal approximate value function amongst all linear approximations for the discounted MDP will have the following form: • Vn = 7 " VT(i)-r(0/ l(j) f0r all n € { 1 , N - 1 } • VN = 0 • Wi = 7 TW- TWfc(I) for all i E {1,.... /} . Wo = 7 T ( 1 ) - T ( / ) M / ) ( - T(1)C - £ + 7 E l x ^ ^ A . ) where n\/T(l) = max(n,T(l)). Proof: Again we will begin by proving primal feasibility. If we assume the above form for the optimal approximate value function, the primal constraint yields: (4.16) ( l - 7 ) W o < - 7 r ( 1 ) - T ( / ) M / ) £ ! - X > T ( i ) - T ( / ) ^ K i i=i T ( 1 ) T / v + J2 (kW71 - TW1+ + ini)-T[I)+lKI) - Jni)-T{1)h(l)ja, _ ( l _ 7 ) 7 T ( l ) - T ( / ) ^ / ) a . r + £ - + 7"- r ( / )^(/) ~ 7 r ( i ) - T ( / ) M ' ) ) n=T(l)+l ^ ' + E ( 7 T W " T ( / ) + 1 ^ ) A i + (fc(z) - 7 T ( i ) - T ( 7 ) M / ) k ) t=l ^ ' As with the OT scenario, to prove primal feasibility we simply need to show that the above definition for WQ satisfies equation (4.16) when the RHS is at its most negative. Again, we can find the state-action pair that minimizes the RHS on a day to day basis. 97 For n = 1, the coefficient in the above primal constraint for X\ is at least as negative as the coefficient for an with equality only if i = 1. Thus, the state-action pair minimizing the RHS will have X\ + au = C. In other words, we are indifferent between states that fill day n with any combination of previous bookings and current priority 1 arrivals. For n = 2, . . . , r ( l ) , we know that k(i)[n - T(i)]+ = 0 for all i. Moreover, the coefficient for ain, ^ 7 T ( 1 ) - T ( / ) + 1 — ^ T(l)-T(1)^ is positive for a lH > 1 and equals the coefficient of xn when i — 1. Thus, we are indifferent between states that fill day n with any combination of previous bookings and current priority 1 arrivals. Therefore, any state-action pair that minimizes the RHS will have xn + a\n = C for all n < T( l ) . For n > T ( l ) , the coefficient for ain equals zero if n = T(i). If n < T(i), the coefficient is clearly positive. On the other hand, if n > T(i) it is also positive due to equation (4.14). Thus any state-action pair minimizing the RHS of equation (4.16) will have ain = 0 for all z > 1 and n ^ T(i). Moreover, a\n = 0 for all n > T(l ) . The coefficient for z; is h(i)—•~fT^~T^h(I) which is strictly positive for alH < / by equation (4.13) and equal to zero for % = I. Note that if this condition is not satisfied then the coefficient for z* might be non-positive for other priority classes leading to a different optimal policy (one that might reject demand from more than one class). However, given equation (4.13) is satisfied, any state-action pair minimizing the RHS of equation (4.16) will have z; = 0 for all i < / and that we will be indifferent to the value of Zj (although it is limited by the number of arrivals). Using the above conditions on the set of state-action pairs minimizing the RHS of equation (4.16), one can demonstrate that WQ has the form given initially simply by computing equation (4.16) with the appropriate values for a, x and z. Moreover, 98 we have demonstrated that the proposed primal solution will have tight constraints only for those state action pairs satisfying: • xn + a\n = C for all n < T( l ) • Zi = 0 for a l i < / • ain = 0 for all n > T( l ) • ain = 0 for a lH > 1, n ^ T(i). Again, complementary slackness implies that the optimal dual must be zero for state-action pairs not satisfying the above conditions. Moreover, since the primal variables given above are all non-zero (except for V/v), this implies that the dual constraints must all be tight. If we can construct such a dual solution, we will have proved the optimality of the constructed primal-dual pair. We first determine the amount of dual weight placed on states with positive zj by equating the primal and dual objective functions: N I £ X(s,a)h(I)Zl = Wo + ] T VnEa[Xn} + W i £ a M N I maxl n=l = 7 7 ,T(i)-T(l) 1 - 7 99 which is positive by equation (4.15). If the weighted sum of E a [ X n ] is not large enough (i.e. equation (4.15) is not satisfied), the dual problem may be infeasible or degenerate. Turning to equation (4.5), we again know that Ea[Xjy] should be set to zero since at the beginning of each decision epoch day N stands empty. Thus, we need not put any weight onto state-action pairs with x^ non-zero. For n = N — 1, the dual constraint (4.5) yields £ X(s,a)(xN_1) = Ea[XN_1]^ £ X (s ,a) = ^ ^ - l ] (s,a)eB (s,a)efl For n — N — 2, the dual constraint (4.5) yields £ X(s,a)(a;w_2 - 7^iv-i) = Ea[XN-2] (s ,a)£S £ X ( s , a ) ( x w _ 2 ) - 7 £ A"(s,a)(xjv_i) = Ea[XN_2] (s,a)eB (s,a)6B £ X ( s , a ) = ^ ^ + 7 £ *(s,a) . ( s , a ) 6 B ( s , a ) S B xN_2>0 xN_1>0 = ^Ea[xN-2] + 1Ea[N-l]y Proceeding similarly, for arbitrary n, we get N (4.17) £ X(s,a) = ZjZA + 7 £ X (s ,a) = I £ 7 r o - ^ [ ^ ] . ( s , a ) 6 B ( s , a ) S B m=n x n > 0 x n + 1 > 0 This would be for the case for all n > T(l) except that bookings can occur for lower priority classes on each T(i). Thus, for n = T(i) — 1, there is the added 100 complication that bookings may be made on day n + 1. This leads to E X(s ,a)(x T ( i )_ 1 - 7Zr(i) - 7^,2^)) = E Q [ X T ( i ) _ i ] (s,a)eB =>C E ^ ( s , a ) - 7 ^ £ X ( s , a ) - 7 C X(s,a) = Ea[Xni)-i] ( s , a ) S B ( s , a ) S B ( s , a ) e B r T ( i ) - l > 0 ' x T ( i ) > 0 ° i , T ( t ) > 0 However, equation (4.6) gives us that C E X(s,a) + E X(s ,a)zi= £ X(s'a)^ = Y ^ A i (s.a)eB (s,a)€B (s,a)SB ^ " i , T ( i ) > 0 2 i > 0 a Thus, for i = I, we have E *(s'a) ( s , a ) £ B v ' ' ( s , a ) £ B ° i , T ( i ) > 0 z » > 0 ( s , a ) S B xT(i)-l>< V i 5 t l [ I T ( l H ] + ^ - A , - 7 £ X ( s , a ) z ^ + 7 E X(s,a) \ ^ ( s , a ) S B / ( s , a ) S B * i > 0 I T ( i ) > 0 = h ( £ 7 m - T ( i ) + 1 ^ [ X m ] + ^ - A , - 7 E • ^m=T(i)-l ^ (s,a)es / 2 j > 0 In general, for n > T( l ) , we have (4.18) E X(s'a) = £ ( E 7 m - n ^ [ ^ m ] + TZ-J2 l [ T [ i ) - n ] + l T [ i ) > n \ i (s,a)es >• m=n ^ t = l x n > 0 -nl+/r(/)>n E 7[r(0-( s , a ) e B z / > 0 since = 0 for all i ^ I. Finally, for n < T(l), the situation is again complicated by the fact that now a l n may be non-zero. However, we know that for all n < T( l ) , 101 the day has to be full with either previous bookings or current bookings. Thus, for n < T( l ) , we have £ X(s,a)(a; n - jxn+i - 7^1,71+1) - Ea[Xn] (s,a)€B C £ X(S,a) = Ea[Xn]+'yc( £ X(s,a) + £ X ( s , a ) \ ( s , a ) € B ^ ( s , a ) £ B ( s , a ) £ B ' x„>0 xn+1>0 a l , n + l > ° But since xn+\ + ai,n+i = C for all (s,a) G 5, equation (4.4) give us £ X(s,a) + £ X(s,a) = ^ 7 ( s , a ) € B ( s , a ) € B ' ° l , n + l I n + l = C Therefore, (4.19) Y. 7 C 1 - 7 i n > 0 Thus equations (4.18) and (4.19) give us the amount of dual weight that must be placed on each day in order to satisfy complementary slackness as well as feasibility. The above argument suggests a weighting scheme for a dual feasible solution that, together with the proposed primal solution, satisfies complementary slackness. Again it remains to show that one can easily construct a feasible dual solution satisfying the above weighting scheme but the line of reasoning is no different and a similar algorithm for determining the dual solution can be applied. This concludes the proof. 4. How Good is the Approximation? Perhaps the greatest challenge facing approximate dynamic programming is to determine the size of the gap between the cost associated with a policy derived from the approximate DP and the cost that would be incurred under the true optimal 102 policy. Unfortunately, current bounds are far from tight [15]. One alternative is to compare the results with that of current practice over a simulated data set [2]. However, in our case, current practice does not follow any discernible rule and thus defies simulation. Another option is to compare the outcome of the proposed booking policy with that of current practice over a known historical data set. This too is proving difficult in our current situation as hospitals have very little accurate data on OP waiting time. Though we have data giving the arrival rates for OP by priority class by day, there is no record of the state of the system at the beginning of data collection thus making comparison difficult. The simulation results given in Chapter 3 avoid this difficulty by providing a long enough "warm-up" period so that the effect of the initial conditions are minimized. The results substantiate the claim that our proposed policy outperforms current practice but it would be nice if we could quantify the gap between what we can achieve through approximation and what might have been achieved had we been able to solve the MDP directly. 4.1. Perfect Foresight. We can get an upper limit on how well we might have done by assuming perfect knowledge of the incoming demand. In such a case, the optimal policy can be solved as a straightforward assignment problem of the following form. Let yu be the number of OPs of priority i that arrive on day t of the simulation. Further, let aitn be the action that determines how many of priority i patients that arrived on day t to book on day n. Clearly, to be valid n must be greater than t but less than or equal to t + N. The assignment problem then becomes: mm 103 subject to £ aun < C Vn i,t £ aitn + Zi = £ y i t Vi t,n t aun > 0, integer ditn = 0 Vn < t and Vn > N + i . Unfortunately, for a long simulation run or a large-sized hospital, this assignment problem becomes extremely memory intensive. For shorter simulation runs (1000 days) and a small-sized hospital, perfect foresight with an initially empty queue and the same parameters as the initial simulation run given in the results section of Chapter 3 seems to avoid all costs. Such perfect foresight is however impossibly optimistic and thus only provides a very loose lower bound on actual costs. Moreover, in a larger hospital with more variation in demand, the results are unlikely to be so good. 4.2. The Opt imal Objective Value in the Approximate L P . One imme-diate lower bound on the total discounted cost is the optimal objective value for the approximate LP. Since we have restricted the value function to have a certain form, it is clear that the optimal primal objective value to the approximate L P will be a lower bound on the optimal objective in the original LP. By strong duality, we further get that the optimal dual objective in the approximation will also be a lower bound on the dual objective in the original LP. This dual version of the objective function can be interpreted as the long run total discounted cost and thus our optimal value for the objective in the approximate LP gives us a lower bound on the true discounted 104 total cost. In theory, we can therefore get a handle on the "cost" associated with having approximated the value function by comparing this lower bound with the to-tal discounted cost incurred during the simulation (line of reasoning follows that of [3]). While this bound is better than "perfect foresight", it suffers from being highly dependent on our choice of a, the distribution on the initial state of the system, and on the demand stream early on in the simulation run. Thus, the total discounted cost incurred during the simulation varies dramatically with a and even varies sig-nificantly between simulation runs with the same a. If we set a so that the initial booking horizon is full then we get the tightest bound with total discounted cost in the simulation being within 18% of the lower bound (±3.08%). However, if a is chosen to be slightly more realistic so that more capacity is available as one moves further out in the booking horizon then the optimality gap increases to 34 % (±4.83%). The intuition is that the L P formulation does not fully capture the time dynamics so that it best mirrors the "true costs" when the costs are incurred sooner rather than later. The above confidence intervals obviously give an upper bound on the optimality gap. If we were able to better capture the true value function in the original MDP one would see both the value of the objective function (the lower bound) increase and the simulated total discounted cost decrease. It is possible that even if one were able to solve the LP exactly, the gap would still be non-zero due to the fact mentioned earlier that the LP does not fully capture the time dynamics. 4.3. A Convex Approximat ion. The challenge of deriving practical bounds within approximate dynamic programming is an on-going one that we hope to pursue more in the future but there is one final piece of evidence to suggest that our approx-imation is, in fact, a reasonable facsimile of the true value function. It arises from 105 pursuing what was originally thought to be a defect in the model - namely, that a lin-ear approximation does not take into account that on any given day, the marginal cost of booking a scanning slot should increase as the number of available slots decreases. Under a linear approximation, going from having two available slots to having one "costs" the same as going from having ten available slots to having nine. One would presume that this is not actually the case. Thus, a more reasonable conjecture of the value function might be non-decreasing and convex in the number already booked on each day (xn). For simplicity we maintained a linear approximation in the demand variable. In developing this new approximation, we took advantage of the fact that any non-decreasing, convex function / : {0,1, ...,C} —> 3ft with /(0) = 0, can be written as: c - i v=0 with all TV > 0 and where 4>v(x) — max{0,x — v},v G {0,1,.. . ,C — 1}. Thus our convex approximation can be written as N C - 1 v(x, y) = W0 + £ £ Tm<j>v{xn) + £ WiVi. n = l v=0 i = l Precisely as before, we can then reformulate the LP in terms of this approximate value function: ( N C - 1 / . N Wo + £ £ Ea[<pv(Xn)]Tm + £ Ea[Y$Wi n = l i;=0 i = l / 106 subject to N C - l (1 - 7) W 0 + E E T v n \ ^(xn) ~ 7^(^n+l + E ai,n+l) I n=l ?j=0 \ i=l / (4.21) +YjWiL-1Ed\dl]\ i=l ^ • ' < E C(^ n)°™ + E ^ G (^ ' ^ G ^ i=l where a is a probability distribution over the initial conditions. Again, we are still left with a very large number of constraints suggesting that we solve the dual by column generation. The dual of the above LP can be written as (4.22) min ^ X(x, y,a,z) I ^ n)Q»" + E h(i)zj j ( S , ! / ) 6 S \ i,n i=l / subject to ( 1 - 7 ) E X(x,y,a,z) = 1 E -^ (x, y. a, f) I ^ ( ^ n ) - 7<r^ I ^n+l + E a i > n + l ) ) - ^ [ ^ l 1 " ) ] x,y)€S \ \ i=l / / (Z, ( S , z ) s / l S i j r Vn = 1 , J V and Vu = 0 , C - 1 E X ( f , y , a , z ) f j/i -7£?d[di]J > EQ[ipw{yi)] Vi = 1, X > 0. 107 Again we need to start off with a feasible set, 5", of state-action pairs to the dual and then find a violated constraint for the primal by solving: (4.23) z(r,W)= min |c(a, z) - V Wt (Vi - -yEa[di]) - (1 - j)WQ ( 2 , ? ) S S *=1 N C-1 - E E * 71=1 7J=0 v I ^n+1 + / ai,n+l i = l subject to equations 3.1 to 3.3. Due to the equality constraint involving y; (and again ignoring the arbitrary limit on arrival rates), we can still eliminate the y variables to leave: (4.24) Z{T, W) = min {(c(i, n) - Wi)ain + Y(h(i) - W(i))Zi iV C-1 r I I \ + £ £ 7 r 7J,7 l - i0 n = l u=0 >- \ t = l / + 7 £ w i E Q [ F i ] - ( l - 7 ) W o j i = i <* subject to (4.25) (4.26) cn + £ a i n < C Vn,n = 1 , N i = i a, z > 0, integer As with the linear case, we can decompose the minimization by day to get: N (4.27) £ bn + J2(h(i) - Wi)z; + 7 £ WiE\Yi\ - (1 - 7) Wo n = l i = l i = l 108 where each bn has the form: (4.28) (4.29) subject to (4.30) bn = min <^ V 7 c ( i , n ) - Wi)ain a.,n,Xn I * ' v 1=1 C-\ r + E lTv,n-l(t>v{Xn + E Qin) ~~ Tvn<l>v(Xn) v-0 i = l a;n + E a i n ^ C ' Vn,n = 1 , N l x,a> 0, integer i = i where T„ in_i = 0 for all u and n = 1. We now have a non-linear objective with linear constraints. However, if we fix xn = x then each bn can be transformed into the equivalent IP given below: , i c - i (4.31) jnin \ E(c(^ n ) ~ ^i)<kn + E v 1=1 u=0 subject to (4.32) (4.33) (4.34) (4.35) i = l x + Ea*« —^ Vn,n = 1 , A T tf„>0 Vu,u = 0 , . . . , C - l > X + E _ w Vu,u = 0 , . . . , C - l i = l a > 0, integer . Finding the value of x G {0, ...,C} that provides the smallest objective (4.31) is, of course, equivalent to solving (4.23). Once the optimal parameters, W0,TVN and 109 Wi have been determined the optimal policy, for a given (x, y) vector, reduces to a convex transportation problem: I N min >^ h(i)zi + >^ ( 3 , S ) e A ( f ^ ^ C - 1 £ c(i,n)ain + 7 £ r , ; n ^ i = l . TJ=0 \ i = l / + constant subject to •'(4.36) Y.ain<C-xn Vn,n = l,...,N i=l N (4.37) ^2ain = yi-Zi = 1 , I 71=1 (4.38) a, z > 0, integer . This is the "local" optimization problem that, once r and W are known, can be solved for any given state (x,y) and which yields the optimal booking policy based on the approximation. It can be linearized in exactly the same manner as equation (4.31). The surprising result is that the added flexibility in this model makes no difference as the optimal value function chosen by the model turns out to be the exact same linear model given earlier - at least for the simulation runs we have attempted to date. This would seem to support the conclusion that the linear model is an adequate representation of the true value function of the MDP and that the "cost" associated with having approximated the value function is not in fact too significant. Further simulation runs would help to strengthen this finding but ideally we would like to show this analytically in a manner similar to the proofs given above. no 5. Conclusion The implication of the results in this chapter is that one can in fact derive the optimal approximate value without having to perform the arduous task of solving the approximate LP. Moreover, we have shown that for any reasonable ratio between the cost associated with overtime or rejection and the cost of late booking, the optimal value function (and therefore the optimal policy) will have the form outlined in the theorems presented here. Thus, the optimal policies presented in Chapter 3 will in fact remain optimal for a wide range of values for the cost parameters - provided the future is not heavily discounted. Our ability to bound the "cost" associated with having approximated the value function is admittedly the weakest part of the analysis. However, both the bounds derived through the optimal dual objective value and the fact that the convex approximation returned the same linear optimal solution, suggest that our approximation is a reasonable representation of the true value function. To be able to say more than this is the object of future research.1 X A version of this Chapter may be submitted for publication. Patrick J. Puterman M . Queyrannne M . I l l C H A P T E R 5 Comparing Models 1. Introduction An astute reader might at this point wonder why one needs the model from Chapter 2 as clearly one could extend the MDP model given in Chapter 3 to include inpatient demand and thus derive a complete scheduling policy. While this is true, and certainly we will present the results of extending the M D P model in this chapter, there is a more significant difference between the model in Chapter 2 and that given in Chapter 3. In Chapter 2, the model begins with a fixed overtime limit and then seeks to assess the impact of that OT limit on the waiting times of OP. In Chapter 3, we begin with recommended maximum waiting times and assess how much overtime is necessary in order to minimize the trade-off between late scans and OT (or rejection). We showed that the optimal scheduling policy can maintain reasonable waiting times with minimal OT (or rejection) and is robust to changes in the cost parameters. Thus, essentially, the two models start from opposite assumptions - the first assumes a limit on OT, the second a (non-strict) limit on maximum waiting time. The first therefore is assessing the impact of a given policy, the second is suggesting the necessary policy to meet given waiting time targets. Moreover, the analytical method is different in the two chapters with the model in Chapter 3 is significantly more general. 112 2. Extending the M D P to include Inpatients Extending the M D P to include IP demand simply involves adding an extra pri-ority class with a prohibitively high cost associated with a late booking and with a maximum recommended waiting time of one day. In other words, a priority class that is served the day the demand is placed. There is a slight change in the interpretation of the model as xi in the original MDP represented tomorrow's slots whereas now it represents today's slots. Thus, days are shifted over one and an additional restric-tion must be placed to insure that no OP can be booked into x\. We present here the results for the scenario involving OT. The theorems presented in Chapter 3 and proved in Chapter 4 suggest that the optimal policy will involve booking all lower priority patients (in this case all OP priority classes) on the last available day that does not incur a cost and using OT to do any IP demand that cannot be met during regular hours. In fact, this is precisely what emerges when the full model is run in the simulation (see Table 5.1). Of note, is the fact that the cost associated with this policy is much higher than was the case when we did not include IP. This is due to the fact that before our highest priority class could be booked anywhere within the first week without incurring a penalty whereas now, our highest priority class can only be booked on day 1. Thus we no longer have the same flexibility to smooth out the variations in demand. This would suggest that any flexibility that might be added to the scheduling of IP might very well have a significant impact on costs - as was seen in Chapter 2. Including a LIP category into the MDP model simply involves adding another priority class where the maximum recommended waiting time is 2 days with a prohibitively high cost associated with a late booking. The effect of taking some of the demand 113 T A B L E 5.1. The Impact of LIP on a Small Sized Hospital I P M i x % Late /% Served through O T Dai ly Cost H I P L I P O P 1 OP2 O P 3 Total 100% HIP 0/10.69% - 0/0 0/0 0/0 0/7.13% 192.37 90% HIP 0/9.52% 0/0 0/0 0/0 0/0 0/5.71% 154.15 from IP and placing it into this LIP category is to significantly increase throughput and therefore reduce the amount of OT required (see Table 5.1). The results presented in Table 5.1 represent the same model as the initial results in Chapter 3 with OP demand following three independent Poisson distributions with means 5, 3 and 2 respectively. We assume an IP demand that is Poisson with mean 20. In the model that includes a LIP category, we assume 10% of IP demand can be classified as LIP. OT costs are set at 90 with a discount rate of 0.99 and late penalty costs of 1000, 500, 18, 9, 6 for each priority class respectively. (Note that all we really needed was to make the late penalty cost for HIP and LIP greater than the OT cost to insure that no IP was made to waited longer than the recommended time.) We set capacity equal to 30. In terms of the number of OT scans performed, assuming only 10% of IP can be classified as low priority, yields a drop from an average of 2.1 OT scans per day to 1.7 OT scans per day. Note also, that the advantage of this model is that, unlike the model in Chapter 2, it does not require a pool of on-call OP who can be rescheduled as space becomes available. This is a significant advantage in that the booking policy becomes much simpler. If we seek to mirror a larger hospital such as V G H then the advantage of adding a LIP category becomes more pronounced (see Table 5.2). Again, recall that the V G H 114 T A B L E 5.2. A Larger Hospital IP M i x % Late /% Served through O T Dai ly Cost H I P L I P O P 1 OP2 O P 3 Total 100% HIP 0/4.75% - 0/0 0/0' 0/0 0/3.56% 384.42 90% HIP 0/3.3% 0/0 0/0 0/0 0/0 0/2.23% 240.62 data available to us simply gives the number of requests per priority class per day but does not give us the actual number of scanning slots requested by priority class per day. This latter number may be significantly higher as some requests require more than one 15 minute scanning slot. The average number of requests for IP scans per day at V G H is 58.3 while OP demand from the three priority classes was 5.3, 10.9 and 13.8 respectively. While most OP scans are 15 minutes in length, IP scans are often much longer. Thus, it makes sense to increase the number of scans requested by IP to an average of 90 per day while letting OP average demand be 5, 10 and 15 per day respectively. Table 5.2 presents the results. Again, in terms of the number of OT scans performed, the LIP category yields a drop from an average of 4.3 OT scans per day to 2.7 OT scans per day. Capacity usage has also gone up from 96% to 98%. Finally, for reasons already mentioned, it is difficult to compare the models from Chapter 2 and Chapter 3. However, in Chapter 2 we did investigate the amount of OT required in order to meet demand for the case with 90% HIP and the case with 100% HIP. In the case of 90% HIP, the OT limit needed to be set at 6 OT scans per day (on average) while in the case of 100% HIP, 8 OT scans per day were needed. Thus, it is worth seeing whether these predictions are in fact born out in the full MDP model when the same parameter values are used as in the initial simulation 115 T A B L E 5.3. Mirroring Chapter 2 Simulation IP M i x % Late /% Served through O T Dai ly Cost H I P L I P O P 1 OP2 O P 3 Total 100% HIP 0/6.48% - 0/0 0/0 0/0 0/4.57% 698.26 90% HIP 0/5.72% 0/0 0/0 0/0 0/0 0/3.63% 555.68 from Chapter 2. To that end we assumed a capacity of 165 with Poisson demand rate of 120 for IP and 50 for OP. OP demand was broken into the three priority classes with arrival rates 15, 15 and 20. The results are given in Table 5.3. Dividing the average daily cost by 90 we see in fact that the prediction from Chapter 2 does in fact reflect the results given with the full M D P model in terms of the amount of OT required in order to meet demand. From a policy standpoint, the full MDP model would seem to suggest a very simple booking policy with an easily quantifiable cost. A further challenge to the resource manager is to decide whether or not the potential reduction in OT cost resulting from an increase in regular hour capacity is worth the financial input required. In fact, our model can easily help answer this question by quantifying the difference in OT cost between a model with capacity C and a model with capacity C + k, k > 0. For instance, taking the example from Table 5.3 and increasing regular hour capacity from 165 to 170 yields the results given in Figure 5.1 (taking only the case with 10% LIP). Thus our model allows the resource manager to determine exactly how much reg-ular hour capacity is optimal and how much OT costs to expect once that investment in regular hour capacity has been made - subject to the proviso that our solution is based on an approximation. It would seem reasonable to suppose that the optimal 116 F I G U R E 5.1. Average Number of Daily OT Scans as a Function of Capacity 9 - r o A , , , , 1 165 166 167 168 169 170 C a p a c i t y ( solution will not be one involving zero OT as that would lead to significant unused capacity on days with low demand. Of course, how much OT is optimal depends very much on the actual cost of an OT scan and the cost associated with adding additional regular hour capacity. 117 C H A P T E R 6 Further Enhancements and Policy Recommendations 1. Further Enhancements There are certainly numerous potential enhancements to our optimization model that we hope to purse in the future. We discuss briefly some of the more interest-ing ones. These do not represent attempts to "complicate" the model but rather seek to address significant challenges experienced by resource managers charged with scheduling multi-priority patients. 1.1. O P N o Shows. A potentially significant source of unused capacity are OP who do not arrive in time for their appointment or simply do not show up at all. It is well-known within the airline industry that the optimal booking policy in the presence of no shows invariably involves overbooking. At present, our model does not explicitly penalize unused capacity. Of course, implicitly, by creating a late penalty, unused capacity is penalized simply because it increases waiting times. However, if we wanted to include a "no show" rate into our model then we would need to include in the reward function a penalty associated with unused capacity which would clearly be affected by the "no show" rate. It would be of interest to determine if such an addition to the reward function does in fact affect the optimal policy. 1.2. Random Service Times. In our current M D P model, each request for a scan is assumed to take exactly 15 minutes. Thus OT is incurred as soon as more patients are booked into a given day than there is capacity. In reality, scanning time 118 is stochastic and thus the amount of OT incurred is random. It is our belief that the inclusion of random service times would have little impact on the results provided that the expected scanning time is approximately equal to the allotted time. However, it would be worthwhile to verify this. 1.3. Mul t ip le E x a m Lengths. As mentioned in Chapter 2, scheduled exam lengths are, in reality, not all 15 minutes in length. Instead, they can be 15, 30, 45, 60 or even 90 minutes (all multiples of a 15 minute scanning slot) in duration. To deal with this added complication, the MDP model would need to be expanded so that each priority class is broken down by exam length. Thus, the state space would be (x,y) = (xi,...,xN,yni..,y1j,.:.,yIi,..,YIJ) where y^ represents the number of priority i OP waiting to be booked for a scan requiring j slots and J is the number of potential exam lengths. The action would consist of where to place incoming demand from each priority level and each exam length and would take the form: (d, z) (Oijnj where a;jn represents the number of priority i OP requiring a scan of j slots to book on day n and Zij is the number of priority i OP requiring a scan of j slots to reject or serve through overtime. The constraints on the action set would similarly need to 119 be modified to the following: i J xn + E E J ' * a^n - ^ Vn,n = l,...,N N Ea^» = Vii ~ Zii V*>* = 1 a n d V-?>-7 = J n = l a, z>0, integer = 1 , I & \/n,n = 1,N. The transition probability would then become i J i J (xux2, •..,xN;y1,y2, ...,yi) (^2 + E E J *a '^2' -' X n + E E J : * Q ^ » ° i rfi> •••» ^ ) i = l j = l i = l j = l where dj now represents the incoming demand for priority i OP broken down into the exam length categories. Finally, the cost to the system is given by: / J c(a,z) = E c(hn)a i : j,n + E E - 7 * h ^ Z i i,j,n i=l j=l where c(i,n) has precisely the same form as before. Of course, in order to implement such a model, one would need to know the arrivals rates not only for each priority class but for each priority class and exam length category. Nevertheless, given that such data is available, the above can be solved in precisely the same manner through approximate dynamic programming. The alternative is simply to view a 45 minute scan as three separate 15 minutes scan. However, this leads to batch arrivals and does not take into account that a 45 minute scan cannot be broken into one 15 minute scan today and two tomorrow. Our suspicion is that the simple heuristic booking policy would remain substantially unchanged but it would be useful to verify this. 120 1.4. Piece-wise Linear Costs. The reality for most hospitals is that staff salaries for OT are initially time and a half but jump to double time if the amount of OT reaches a certain limit, Z. Introducing such piecewise OT costs would require adding a second rejection/OT variable z' such that z\ equals to zero unless Zj equals Z. Thus the cost structure would become where h'(i) represents the higher cost associated with double time. 1.5. Patient choice. Another reality facing hospitals is that patients often refuse the first date offered to them and thus may need to be offered a second choice. Adding this to the M D P model would greatly increase its complexity as the decision process would now require at least two decisions for each patient waiting to be booked. More-over, the transition probabilities would have an additional stochastic element as a patient would refuse the initial date offered with some probability. More realistically, it might be worth incorporating patient choice into the simulation and seeing what potential effect it might have on the average daily cost. 1.6. Demand Dependent on Expected Waiting Time. Perhaps more in-teresting would be to incorporate the reality that demand for a hospital resource is most likely highly (negatively) correlated with expected waiting time. Thus, as waiting times decrease, demand increases. This could be incorporated into the MDP model simply by introducing balking to the model by making tomorrow's demand (y) inversely proportional to the number of patients already in the system (X)n=i x «)-i 121 Recall that in the original model the approximate LP could be written as: (6.1) max (W0 + V Ea[Xn]Vn + T] E ^ w A v& { n^i i=l J subject to (1 - 7) Wo + £ Vn (xn - jxn+1 - 7 £ ai.n+i^ + £ Wi fj/i - 7^a[^i] n = l ^ i = l ' i = l ^ < c(a, 2) V(a, 5) e i4 S ) i ? and (£, y) E S V,W>0 with XAT+I = 0 and a j^v+i = 0, for all i G {1,...,/} and where Xn and Yi are random variables representing the number of OPs already booked on day n and the number from priority class i waiting to be booked respectively. The only difference emerging when demand is made inversely proportional to the number of patients already in the system is that the expectation over a of Yi will now be conditional upon Yln=i x«-What effect this might have on the optimal policy is hard to conjecture. 1.7. Average Reward Cri ter ia . We are very interested in developing an anal-ogous model for the average reward MDP. The advantage would be that we avoid the ambiguities introduced by the arbitrary "cost" vector, a, in the discounted version. It will be of interest to see if we can in fact give as strong results in the average reward case as we have been able to in the discounted one. The complication is to determine whether or not the resulting average reward MDP model is unichain or not. 1.8. Mul t ip l e Hospitals. There is one last important practical complication that is worthy of consideration. Within Canada, and most likely elsewhere, the 122 situation of one hospital acting independently is becoming less and less common. Instead, regions are divided into health authorities, each of which may contain a number of hospitals with one centralized booking system. Thus, the challenge facing a resource manager is complicated by the fact that his resources may be spread out throughout the region at various hospitals. Thus, the state of the system at any given decision epoch includes the current booking schedule at each hospital as well as the current demand broken down not only by priority level but also by region. We are interested in the region of the OP simply because we will need to take into account a cost associated with traveling to various hospitals. (We need to be able avoid the absurd situation of sending an OP across the region in order to get a scan done one day earlier.) Thus the state space has the form: (x,y) = (xi,...,xN,yu...,yi) where xn = (xn\,X„M) is a vector consisting of the number of OP already booked on day n for each hospital m G M = { 1 , M } , Vi = (yn, •••lUu is a vector consisting of the number of OP of priority i from each geographical region j G J = { 1 , J } waiting to be booked, N = the maximum number of days one will book in advance, N = {1,...,N}. I = the number of OP priority levels, /={!,...,/}. 123 The actions are similarly more complicated as the resource manager needs to determine how many OP of each priority level and region to send to each hospital and to each day. Thus, a vector of potential actions can be written as: where <J(i,j,n,m) = the number of priority i OP from region j to book on day n at hospital m, Zij — the number of OP of priority i from region j to reject. Of course, to be valid, any action must still satisfy the following two constraints, insuring that the capacity constraint is not violated and that all waiting OPs are booked, as well as constraints insuring that the actions are positive and integer-valued. i J (6.2) xnm + J2Yl <Cm V(n,m)e{N,M) i = i j = i N M (6-3) £ £ a(i,j,n,m) = Vij ~ Zij V(l, j) E {I, J) 71=1 771=1 (6.4) a,z> 0, integer. The costs associated with such a scheme remain the same as before with an addi-tional term that takes into account the cost of travel. i J c(a> z) = £ c(i,j, n, m)o(jj>n,m) + £ £ h(i)zij i,j,n,m i = l j=l 124 where x = (x[,...,xN),a = {a(ij,n,m)} and z = {zi3}, c(i,j,n,m) = k(i)[n - T(i)]+ + D(j,m), k(i) is the daily penalty for a OP of priority i who waits longer than the maximum recommended time, T(i), h(i) is the penalty for rejecting an OP of priority i, D(j, m) is the cost of sending a OP from region j to hospital m. Given the above formulation, we can give the transitions as: ( i j i J \ x2 + E E a ( i j , 2 , ) , , - ^ J v + y~]y^a>(i,j,N,-),0,d\ t = l j=l i=l j = l / with probability p(d) = r j j = i ^Ylj=iPY{dij) ^ and where p(di3) is the probability that dij OP of priority i and from region j arrive on a given day. Here we are assuming that the demand for priority/region pair is independent of all others. Finally, the optimality equation is written as: (6.6) min < c(a, z) {a,z)&AStV y + 7 E Pv$ * v ( ^ + E E °(«J'-2.-)' '''' X"N + E E ° ( < ' °> d j f &£» L V <=1 i = l <=1 3=1 J J J where 7 is the discount factor. From here, we can formulate the model much as we did before by deriving the related LP and approximating the value function by either a linear or convex ap-proximation. Though it is clear that the state space is significantly larger, it seems 125 reasonable to hope that similar results can be obtained in this more general setting. Future work will seek to establish this. 1.9. Alternative Applications. Finally, we are interested in pursuing a num-ber of possible alternative applications of the model. The most obvious is to surgery scheduling. The complication here is that most surgical scheduling works on a block design that assigns blocks of time to each surgeon who then books his/her patients into those blocks. Thus our model might be most useful to the surgeons themselves as they seek to minimize excessive waiting time for their patients based on a fixed capacity available to them. Moreover, surgeons do have access to OT as they can request more time if needed. A second potential application would be to the scheduling of cancer radiation treatment. The added complication here is that when one books a patient for treat-ment, one is booking them for a number of treatment sessions rather than just one. Moreover, some treatments may require daily treatment for a period of days while others may require weekly treatment for a period of weeks. The length of treatment will vary by condition. Thus the patient classes will need to cover not only priority but also type and length of treatment. Given this information on the patients wait-ing to be booked, the update on the booking horizon, x, though more complicated is nonetheless still entirely deterministic. Finally, it would be interesting to see what purpose our model might serve in non-health care applications such as airline revenue management and call center manage-ment. Airline revenue management is not trading off waiting time and OT costs so, while the method may still be applicable, the objective would have to be modified significantly. Call centers on the other hand are dealing with the trade-off between 126 waiting time and capacity costs. Thus there is certainly the potential for useful cross-over. 2. Policy Insights The ultimate goal of this research is, of course, to aid hospital resource managers to more efficiently schedule patients. Thus, it is fitting that we conclude this thesis with an overview of the policy insights to be gleaned from this work. First and foremost, the salient message of this research is that a small amount of OT and intelligent scheduling can maintain reasonable waiting times. There will clearly be an optimal regular hour capacity that will be sufficient to keep OT costs at a reasonable level but not so large as to lead to excessive amounts of wasted resource time. Our model can help in determining the optimal choice for this trade-off. The intuition is that, in a system where demand and capacity are evenly matched, spikes in demand will cause the booking horizon to reach an undesirable state (i.e. one in which patients are booked later than recommended). If no means is available for relieving the pressure on the system then it is difficult for the resource manager to reduce waiting times back down to acceptable levels. Thus, when the next spike in demand arrives, it simply compounds the problem. However, if a small amount of OT is used judiciously, when a spike in demand occurs waiting times can be maintained within the recommended time frame. The second policy insight is that the more flexibility present in the scheduling of your highest priority class, the greater your ability to manage waiting times for minimal cost. This was evident when we went from a model having only OP (where the highest priority class could be booked anywhere within the first week without 127 incurring a cost) to the full model involving IP (who had to be booked on the day the request was placed). Even adding a one day flexibility to only 10% of the IP class can have a significant impact on throughput and therefore on waiting times for all classes of patients. It is worth reminding the reader that this one day flexibility is already present in the priority categorization for C T scans at the site we studied but is currently not being used. Thirdly, the simulation results in Chapter 3 clearly show that a strict reservation (booking limit) policy can be sub-optimal. Instead, one can do better by dynamically scheduling patients as described in Chapters 3 and 5. This confirms the work of Gerchak, Gupta and Henig who also showed that strict reservation policies can be sub-optimal in the case of two priority classes [22]. Here we demonstrate this result for multiple priority classes. Fourthly, the research presented in this paper outlines simple booking policies that manage to restrict waiting times to the recommended levels. Due to the fact that we have employed approximations in order to solve the otherwise intractable MDP, we cannot categorically state that these booking policies are in fact optimal. However, we have provided bounds that suggest that these policies are, at least, close to optimal and certainly they would seem to be an improvement over current practice. Moreover, the simulation results suggest that there is very little unused capacity available for improving throughput. Thus, the potential for reducing the amount of OT required is limited. Finally, as health authorities move to using a centralized booking scheme for all hospitals in their region, it will become more and more necessary to have an automated scheduling process. This will require a more formal booking policy than 128 is currently used in practice. The simplicity of the booking policies that emerge from our research would lend themselves readily to an automated system. Winston Churchill stated that "men often stumble on the truth but usually pick themselves up and carry on as though nothing had happened". Our hope is that those resource managers who "stumble" across this research will not dismiss it as the work of academics in their ivory tower but will find it useful in aiding their attempts to more efficiently manage hospital resources. 129 Bibliography [1] D. Adelman. A price-directed approach to stochastic inventory/routing. Operations Research, 52:499-514, 2004. [2] D. Adelman. Dynamic bid-prices in revenue management. Accepted for publication in Opera-tions Research, 2005. [3] D. Adelman. Weakly coupled stochastic dynamic programs. Personal Communication, 2006. [4] G. Allon and A. Federgruen. Competition in service industries with segmented markets. Sub-mitted to Management Science, available at www.kellogg.northwestern.edu, 2004. [5] D. Bertsekas and J. Tsitsiklis. NeuroDynamic Programming. Athena Scientific, Belmont, Mas-sachusetts, 1996. [6] D. Bertsimas and I. Popescu. Revenue management in a dynamic network environment. Trans-portation Science, 37:257-277, 2003. [7] D. Bertsimas and J. Tsitsiklis. Linear Optimization. Athena Scientific, Belmont, Massachesetts, 1997. [8] R. Blendon. Inequities in health care: A five country survey. Health Affairs, 21:182-191, 2002. [9] K. Bond et al. Intervention to reduce overcrowding in emergency departments. Available at www.cadth.ca, 2006. [10] X. Bosch. Spain cuts waiting times for surgery. British Medical Journal, 318:419, 1999. [11] X. Bosch. Surgeons working evenings to cut Spanish waiting lists. British Medical Journal, 320:320, 2000. [12] S. Brumelle and D Walczak. Dynamic airline revenue management with multiple semi-markov demand. Operations Research, 51:137-148, 2003. [13] K. Cattani and G. Souza. Inventory rationing and shipment flexibility alternatives for direct market firms. Production and Operations Management, 11:441-457, 2002. 130 [14] B. Chen and S. Henderson. Two issues in setting call center staffing levels. Annals of Operations Research, 108:175-192, 2001. [15] D. De Farias and B. Van Roy. The linear programming approach to approximate-* dynamic programming. Operations Research, 51:850-865, 2003. [16] D. De Farias and B. Van Roy. A cost-shaping linear program for average-cost approximate dy-namic programming with performance guarantees. Mathematics of Operations Research, 29:462-478, 2004. [17] D. De Farias and B. Van Roy. On constraint sampling in the linear programming approach to approximate dynamic programming. Mathematics of Operations Research, 29:462-478, 2004. [18] S. Duckett. Living in the parallel universe in australia: Public medicare and private hospitals. Canadian Medical Association Journal, 173:745-747, 2005. [19] A. Ehman. Saskatchewan's 22-month wait for an mri is 'almost critical' says radiologists' asso-ciation. Canadian Medical Association Journal, 170:776, 2004. [20] N. Esmail. Hospital waiting lists in Canada. Available at www.fraserinstitute.ca, 2005. [21] M . Fitzpatrick. Wait times no.l health care barrier. 2006. The StarPhoenix, Saskatoon. [22] Y . Gerchak, D. Gupta, and M . Henig. Reservation planning for elective surgery under uncertain demand for emergency surgery. Management Science, 42:321-334, 1996. [23] L. Green, S. Savin, and B. Wang. Managing patient demand in a diagnostic medical facility, 2005. Under review with Operations Research. [24] L. Gunning-Schepers. The health benefits of prevention: A simulation approach. Health Policy, 12:1-25, 1989. [25] D. Gupta and L. Wang. Revenue management for a primary-care clinic in presence of patient choice. Under review with Operations Research, 2005. [26] M . Hanning. Maximum waiting-time guarantee - an attempt to reduce waiting lists in Sweden. Health Policy, 36:17-35, 1996. [27] J . Hurst and L. Siciliani. Tackling excessive waiting times for elective surgery: A comparison of policies in twelve oecd countries. OECD Health Working Papers, 6, 2003. 131 [28] S. Kim and I. Horowitz. Scheduling hospital services: the efficacy of elective-surgery quotas. Omega, 30:335-346, 2002. [29] Z. Kmietowicz. Waiting times in british casualty departments remain too long. British Medical Journal, 318:351, 1999. [30] G. Koole and A Mandelbaum'. Queueing models of call centers: A n introduction. Annals of Operations Research, 113:41-59, 2002. [31] A. Laupacis and W. Evans. Diagnostic imaging in Canada. Healthcare Papers, 6, 2006. [32] D. Lawson and E . Porteus. Multistage inventory management with expediting. Operations Re-search, 8:878-893, 2000. [33] S. Lewis et al. Ending waiting-list mismanagement: Principles and practice. Canadian Medical Association Journal, 162:1297-1300, 2000. [34] L. Liu and X. Liu. Dynamic and static job allocaiton for multi-server systems. HE Transactions, 30:845-854, 1998. [35] A. MacCormick and B. Parry. Waiting time thresholds: Are they appropriate? ANZ. Journal of Surgery, 73:926-928, 2003. [36] D. Moulton. New software helping surgeons cut waits, e-mail communication, 2006. [37] T. Noseworthy. Further reflections on diagnostic imaging in Canada. Healthcare Papers, 6, 2006. [38] D. Payne. Campaign to reduce waiting lists in ireland has little impact. British Medical Journal, 322:694, 2001. [39] B. Postl. The final report of the federal advisor on wait times. 2006. [40] J . Preater. A bibliography of queues in health care and medicine. Keele Mathematics Research Report, 01:1, 2001. [41] M . Puterman. Markov Decision Processes. John Wiley and Sons, New York, New York, 1994. [42] V. Rhodes. Diagnosis delay sparks probe. The Leader Post (Regina), 2006. [43] J . Ridge, S. Jones, M . Nielsen, and A. Shahari. Capacity planning for intensive care units. European Journal of Operational Research, 105:346-355, 1998. [44] T. Rohleder and K. Klassen. Rolling horizon appointment scheduling: A simulation study. Health Care Management Science, 5:201-209, 2002. 132 [45] R. Romanow. Building on values: The future of health care in Canada. 2002. [46] C. Sanmartin et al. Waiting for medical services in Canada: Lots of heat, but little light. Canadian Medical Association Journal, 162:1305-1310, 2000. [47] C. Sanmartin et al. Access to health care services in Canada, 2003. Statistics Canada, Catalogue 82-575-XIE, 2004. [48] J . Schaafsma. Are there better ways to determine wait times? Canadian Medical Association Journal, 174:1551-1552, 2006. [49] P. Schweitzer and A. Seidman. Generalized polynomial approximations in markovian decision processes. J. Math. Anal. App., 110:568-582, 1985. [50] T. Sheldon. Dutch waiting lists increase despite 36m campaign. British Medical Journal, 321:530, 2000. [51] L . Siciliani and J. Hurst. Explaining waiting-time variations for elective surgery across oecd countries. OECD Economic Studies, 38, 2004. [52] P. Slaughter et al. A national strategy for waiting-time research? Canadian Medical Association Journal, 172:1283-1284, 2005. [53] L. Stein. Making the best use of radiological resources in Canada. HealthcarePapers, 6, 2006. [54] A. Street and S. Duckett. Are waiting-lists inevitable? Health Policy, 36:1-15, 1996. [55] D. Strum, L. Vargas, and J. May. Surgical subspecialty block utilization and capacity planning: A minimal cost analysis model. Anesthesiology, 90:1176-1185, 1999. [56] D. Strum, L. Vargas, and J. May. Modeling the uncertainty in surgical procedure times: Com-parison of log-normal and normal models. Anesthesiology, 92:1160-1167, 2000. [57] R. Sutton and A. Barto. Reinforcement Learning. The MIT Press, Cambridge, Massachusetts, 1998. [58] H. Taylor and S. Karlin. An Introduction to Stochastic Modeling. Academic Press Inc., Orlando, Florida, 1985. [59] S. Thomas. Two week rule for cancer referrals? British Medical Journal, 323:864, 2001. 133 [60] G. Van Ryzin and G. Vulcano. Simulation-based optimization of virtual nesting controls for net-work revenue management. Working paper available at the Columbia Business School Website, 2004. 134
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Dynamic patient scheduling for a diagnostic resource
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Dynamic patient scheduling for a diagnostic resource Patrick, Jonathan 2006
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Dynamic patient scheduling for a diagnostic resource |
Creator |
Patrick, Jonathan |
Publisher | University of British Columbia |
Date Issued | 2006 |
Description | We take an in-depth look at the scheduling of patients for a diagnostic resource. Our aim is to schedule patients in order to maintain reasonable waiting times for minimal cost. We assume a fixed capacity with stochastic demand coming from multiple priority classes. We further assume that it is the lower priority patients that must be booked first, therefore requiring the resource manager to implement a booking policy to assure room for later arriving higher priority patients. If too much capacity is reserved for higher priority patients then there will inevitably be unused capacity resulting in longer waiting times than might otherwise be the case. If not enough capacity is reserved then higher priority patients will have to be served through overtime or forced to wait longer than recommended. We begin, in Chapter 1, with an international overview of efforts to reduce waiting times. Chapter 2 proposes a scheduling policy assuming only two priority classes and a fixed limit on expected overtime. The higher priority class are inpatients who must be served the day the demand for a scan is placed. The lower priority class consists of outpatients who may be booked weeks in advance. We present a model that gives the optimal reservation policy and examine the benefit of introducing some flexibility into the higher priority (inpatient) class. Chapter 3 then restricts the modeling to outpatients where demand is divided into multiple priority classes. We present a Markov Decision Process that we solve through approximate dynamic programming in order to derive an approximately optimal booking policy that maintains reasonable waiting times for minimal cost. Chapter 4 presents some strong theoretical results as to the nature of the optimal policy from chapter 3 as well as providing bounds on the "deviation from optimality" associated with our approximation. Chapter 5 then adds inpatients to the model in chapter 3 and compares the results of the full model to those given in chapter 2. Finally, we conclude with possible enhancements to the model and policy insights for the resource manager. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0093055 |
URI | http://hdl.handle.net/2429/18620 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2006-200667.pdf [ 6.81MB ]
- Metadata
- JSON: 831-1.0093055.json
- JSON-LD: 831-1.0093055-ld.json
- RDF/XML (Pretty): 831-1.0093055-rdf.xml
- RDF/JSON: 831-1.0093055-rdf.json
- Turtle: 831-1.0093055-turtle.txt
- N-Triples: 831-1.0093055-rdf-ntriples.txt
- Original Record: 831-1.0093055-source.json
- Full Text
- 831-1.0093055-fulltext.txt
- Citation
- 831-1.0093055.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0093055/manifest