Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Applications of stochastic optimization models in patient screening and blood inventory management Sabouri, Alireza Bagh Abbas 2014

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2014_november_sabouribaghabbas_alireza.pdf [ 795.65kB ]
JSON: 24-1.0102473.json
JSON-LD: 24-1.0102473-ld.json
RDF/XML (Pretty): 24-1.0102473-rdf.xml
RDF/JSON: 24-1.0102473-rdf.json
Turtle: 24-1.0102473-turtle.txt
N-Triples: 24-1.0102473-rdf-ntriples.txt
Original Record: 24-1.0102473-source.json
Full Text

Full Text

Applications of StochasticOptimization Models in PatientScreening and Blood InventoryManagementbyAlireza Sabouri Bagh AbbasB.Sc., Sharif University of Technology, 2007M.Sc., North Carolina State University, 2009A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Business Administration)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)September 2014c© Alireza Sabouri Bagh Abbas 2014AbstractThis thesis comprises three chapters with applications of the stochasticoptimization models in healthcare as a central theme. The first chapterconsiders a patient screening problem. Patients on the kidney transplantwaiting list are at higher risk for developing cardiovascular disease (CVD),which makes them ineligible for transplant. Therefore, transplant centersscreen waiting patients to identify patients with severe CVD. We proposea model for finding screening strategies, with the objective of minimizingsum of the expected screening cost and the expected penalty cost associatedwith transplanting an organ to an ineligible patient. Our results suggestthat current screening guidelines, which are only based on patients’ risk fordeveloping CVD, are significantly dominated by policies that also considerfactors related to patients’ waiting time.In the second chapter, we extend our results from the first chapter tothe case of inspecting a vital component which is needed at a random futuretime when an emergency occurs. If the component is not operational at thattime, the system incurs a large penalty, which we want to avoid through in-spections and replacements. We propose a model and solution algorithm forfinding an inspection policy that minimizes the infinite horizon discountedexpected penalty, replacement, and inspection costs. We also discuss otherstructural properties of the solution, as well as insights based on numericalresults.In the third chapter, we consider inventory decisions regarding issu-ing blood in a hospital. This research is motivated by recent findings inmedicine that the age of transfused blood can affect health outcomes, witholder blood contributing to more complications. Current practice at hospi-tal blood banks is to issue blood in order from oldest to youngest inventory,so as to minimize shortage. However, the conflicting objective of reducingthe age of blood transfused requires an issuing policy that also depends onthe inventory of units of different ages. We propose a model that balancesthe trade-off between the average age of blood transfused and the shortagerate. Our numerical results suggest we can significantly reduce the age oftransfused blood with a relatively small increase in the shortage rate.iiPrefaceModified versions of Chapter 2 and 3 have been submitted for publica-tion, but they have not been accepted for publication yet. These two papersare co-authored with Dr. Tim Huh and Dr. Steven Shechter. They were in-volved in the early stages of problem formulation, provided feedback duringthe course of both research projects, and contributed to manuscript edits.I was responsible for writing the majority of these papers, developing andimplementing all the models, and preparing all the numerical results.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Screening Strategies for Patients on the Kidney TransplantWaiting List . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Inspecting a Vital Component Needed upon Emergency . . . 21.3 Issuing Policies for Hospital Blood Inventory . . . . . . . . . 32 Screening Strategies for Patients on the Kidney TransplantWaiting List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 72.2.1 Clinical literature . . . . . . . . . . . . . . . . . . . . 72.2.2 OR/MS literature . . . . . . . . . . . . . . . . . . . . 82.2.3 Contributions to the literature . . . . . . . . . . . . . 102.3 Problem Formulation and Assumptions . . . . . . . . . . . . 112.3.1 The expected cost of a screening policy . . . . . . . . 122.4 Structural Results . . . . . . . . . . . . . . . . . . . . . . . . 132.5 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . 152.5.1 Simulation of the kidney transplant waiting list . . . 162.5.2 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 17iv2.5.3 Model-based screening policy . . . . . . . . . . . . . . 202.5.4 Results and discussion . . . . . . . . . . . . . . . . . 222.5.5 Comparison of policies in the face of cost uncertainty: 242.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Inspecting a Vital Component Needed upon Emergency . 273.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 283.3 Problem Formulation and Assumptions . . . . . . . . . . . . 313.3.1 The discounted expected total cost of an inspectionpolicy . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.4 Structural Results . . . . . . . . . . . . . . . . . . . . . . . . 353.5 Numerical Examples . . . . . . . . . . . . . . . . . . . . . . . 383.5.1 Effect of changes in the number of available inspectionopportunities . . . . . . . . . . . . . . . . . . . . . . . 383.5.2 Effect of changes in the failure time distribution . . . 403.5.3 Effect of changes in the cost parameters . . . . . . . . 443.5.4 Comparison with constant interval inspection policies 443.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 Issuing Policies for Hospital Blood Inventory . . . . . . . . 494.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 514.2.1 Contribution to related literature . . . . . . . . . . . 524.3 Model and Formulation . . . . . . . . . . . . . . . . . . . . . 534.4 Solution Approach . . . . . . . . . . . . . . . . . . . . . . . . 564.4.1 Calibrating approximate value function coefficients . 564.4.2 ADP-based issuance policy . . . . . . . . . . . . . . . 624.5 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . 634.5.1 Simulation of the hospital blood bank . . . . . . . . . 634.5.2 Results and insights . . . . . . . . . . . . . . . . . . . 644.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705 Conclusion, Extensions and Further Application . . . . . . 72Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75AppendicesA Chapter 2: Supporting Results . . . . . . . . . . . . . . . . . 83vB Chapter 2: Proofs of Main Results . . . . . . . . . . . . . . . 87C Chapter 3: Proofs of Main Results . . . . . . . . . . . . . . . 90D Chapter 3: Supporting Results . . . . . . . . . . . . . . . . . 92E Chapter 3: Solution Algorithm . . . . . . . . . . . . . . . . . 95viList of Tables2.1 Recommendations for cardiac surveillance of waitlisted patients. 82.2 Parameter values and data sources for main model compo-nents. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3 Comparison of different screening policies. . . . . . . . . . . 23viiList of Figures2.1 Pareto efficient policies from different policy classes. The“best” coordinate for each policy reflects the values found inTable 2.3, which are based on the baseline model parametersgiven in Table 2.2 . . . . . . . . . . . . . . . . . . . . . . . . 253.1 The optimal inspection policy and the optimal discountedexpected total cost (DETC) for different values of n (F rep-resents the replacement interval tn+1 − tn). . . . . . . . . . . 393.2 Examples of the optimal inspection policy with counter-intuitiveproperties. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3 Three outcome measures when p = prob(S < T ) varies be-tween 0 and 1 ( corresponds to the base-case scenario). . . . 423.4 Optimal discounted expected total cost (DETC) for differentn as ci and cp change. . . . . . . . . . . . . . . . . . . . . . . 453.5 Comparison of constant interval inspection policies and opti-mal inspection policies. . . . . . . . . . . . . . . . . . . . . . . 464.1 Comparison of ADP-based policies and age-based thresholdpolicies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.2 Comparison of ADP-based policies (solid lines) and age-basedthreshold policies (dashed lines) for different supply-demandratios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.3 Performance of quantity-based threshold policies for values ofκ = 50, 100, . . . , 500. . . . . . . . . . . . . . . . . . . . . . . . 70viiiAcknowledgementsMy sincere thanks go to my supervisors, Dr. Tim Huh and Dr. StevenShechter at the Sauder School of Business for their invaluable help andsupport during my PhD studies. They helped me through every step ofthis research and without their guidance and contribution, this dissertationcertainly would not have been the same.I am thankful to the two other members of my committee, Dr. MauriceQueyranne and Dr. Nick Bansback for their insightful comments and sug-gestions. I also had the opportunity to learn from Dr. Queyranne over thecourse of four PhD courses and was greatly inspired by his knowledge andteaching style.I would also like to thank my wife Behnaz and my parents for theirsupport and encouragement throughout these years which made all thispossible.ixTo Behnaz and SophiaxChapter 1IntroductionHealth care has become a major application for mathematical modelsand the analytical tools developed in the field of Operations Research (OR)over the past decade. Health care is an area where the impact of providingbetter solutions is most tangible. Even minor improvements at the opera-tional level have significant potential savings due to the high costs of thehealth care system. Then, these savings can compensate for the rise in thecosts, standards and the need for better health care delivery. Moreover,by better managing limited health care resources, more patients can haveaccess to high quality care in a timely manner. For these reasons, the maintheme of this dissertation is to develop analytical frameworks for three im-portant problems faced by health care policy-makers and practitioners. Inthe remainder of this chapter we briefly describe and motivate each problem,discuss the objectives of our work, and outline main results of our models.1.1 Screening Strategies for Patients on theKidney Transplant Waiting ListChapter 2 considers the management of patients who wait for severalyears on the kidney transplant waiting list. Approximately 90,000 patientswith end-stage renal disease await a kidney transplant in the U.S., with amedian waiting time of between 2 and 5 years depending on blood type(OPTN [51]). During this time, waiting patients are at significant risk ofdeveloping cardiovascular disease (CVD), which is often described as a silentdisease (McCullough [38]). Therefore, transplant centers screen waiting pa-tients at various intervals to identify such patients and decrease the chancesof operative mortality or poor post-transplant outcomes (Humar et al. [26]).Although the importance of regular cardiovascular screening of these pa-tients is well recognized, there is no consensus on which patients should bescreened and at what intervals (Gaston et al. [23]). Some centers screenall patients annually, some biannually, and some screen different patients atdifferent frequencies according to risk level (Danovitch et al. [17]).11.2. Inspecting a Vital Component Needed upon EmergencySince screening patients at the time of kidney arrival is infeasible (due tothe limited time available), transplant centers screen patients periodically.Collaborating with a kidney transplant surgeon and transplant coordinatorsat the British Columbia Transplant Society, we develop a model to decidehow often patients with different risk profiles and positions on the waitinglist should be screened in order to minimize the expected screening costand the cost of offering a kidney to a patient with unknown CVD. Using asimulation model, we also show that current screening guidelines, which arebased only on patients’ risk for developing CVD, are significantly dominatedby policies that also consider factors related to patients’ waiting time. Wealso establish that the screening intervals should be decreasing over time.This is an intuitive property of the optimal screening policy; nonetheless, itis not considered by the current screening guidelines.To our knowledge, this is the first study that uses OR techniques to ad-dress these types of screening problems. The problem of patient readinessin the context of transplant waiting list management has its own uniquecomplexities that make it distinct from other disease screening problems inthe OR literature. The potential benefits for the patients include decreas-ing the number of cardiac events after renal transplant due to unidentifiedCVD, better use of scarce donated organs, and more efficient use of systemresources for performing patient screenings.1.2 Inspecting a Vital Component Needed uponEmergencyIn Chapter 3, we extend some of our results from Chapter 2 to the case ofinspecting a vital component which is needed at a random future time whenan emergency occurs. If the component is not operational at that time, thesystem incurs a large penalty, which we want to avoid through inspectionsand replacements. While we describe this problem as finding inspectionpolicies for a general component needed at the time of emergency, a healthcare related application for this problem is the inspection of defibrillatorunits placed in public buildings. These unit might fail and their failure arehidden and revealed only by inspection or attempted usage. However, ifthe component is not operational at the time of the emergency, the systemincurs a large cost. Therefore, regular inspection and replacement of theseunits are important.We propose a model and solution algorithm for finding an inspectionpolicy that minimizes the infinite horizon discounted expected penalty, re-21.3. Issuing Policies for Hospital Blood Inventoryplacement, and inspection costs for these units. We also prove several struc-tural properties of the optimal solution, and use them to develop an efficientsolution algorithm. Finally, we discuss important managerial insights basedon our numerical experiments. In particular, we show a property of theoptimal inspection policies that contrasts with the existing literature andintuition.1.3 Issuing Policies for Hospital Blood InventoryThe third health care problem that we study in this thesis deals withissuing policies of blood units in the hospital blood bank. Our research ismotivated by the recent clinical evidence that suggests using older blood fortransfusion results in higher risk for complications (Koch et al. [33], Wanget al. [76], Zallen et al. [79]). Whereas all the traditional studies of issuingpolicies and the current practice only consider minimizing shortages andoutdates as part of their objective (Pierskalla and Roach [58]), our modelalso considers the age of blood transfused as one of the performance metricsthat we want to optimize. The conflicting objective of reducing the ageof blood transfused requires a more complicated issuance policy that alsodepends on the inventory of units of different ages.Since consideration of the age of transfused blood in designing issuingpolicies is fairly recent, there are only a few studies in the OR literature thatexplore the trade-offs between the average age of blood transfused and theshortages/wastage. For instance, Atkinson et al. [7] proposed a simple classof issuing policies based on a single age threshold. They used simulation toshow how changing the threshold affects the average age of blood transfusedand the shortage proportion. Abouee-Mehrizi et al. [1] provided a stylizedqueueing model to find the distribution of the age of transfused blood underthe above threshold policy. However, none of these papers characterizethe optimal issuing policy or provide a framework for finding good issuingpolicies that consider the inventory of different ages on each day.We formulate this problem as an infinite horizon dynamic program. Sincethe dynamic programming formulation of this problem suffers from the curseof dimensionality due to the large state and action spaces, we solve theproblem using approximate dynamic programming (ADP) methods. Ournumerical results, based on data from a large hospital in British Columbia,suggest we can significantly reduce the age of transfused blood with a rela-tively small increase in the shortage rate.Our results provide evidence for policy makers that they can improve31.3. Issuing Policies for Hospital Blood Inventorythe health outcomes from blood transfusions by decreasing the average ageof blood transfused without sacrificing the availability of the blood supply.Furthermore, we showed that our state-dependent ADP-based issuing policyoutperforms the static policies previously proposed in the literature. We alsointroduce a simple class of issuing policies inspired by our results, that notonly performs well, but is also easy to implement and follow in practice.4Chapter 2Screening Strategies forPatients on the KidneyTransplant Waiting List2.1 IntroductionEnd-stage renal disease (ESRD) is the complete or near complete failureof the kidney’s function and marks the final stage of chronic kidney disease(CKD). According to the US Renal Data System annual report, approxi-mately 400,000 patients in the United States had ESRD in 2009 (USRDS[74]). There are two treatment options for ESRD, dialysis and kidney trans-plantation, with the latter being the treatment of choice due to its lower costsand better outcomes (Port et al. [60] and Schnuelle et al. [66]). However,a shortage of living and deceased kidney donations leads to long transplantwaiting lists while patients undergo dialysis. Approximately 90,000 patientsin the United States await a kidney transplant, with a median wait timebetween 2 and 5 years depending on blood type (OPTN [51]).All ESRD patients must pass a comprehensive evaluation process beforethey can be accepted to the waiting list. This includes tests for infection,cancer, and heart disease, among others. While accepted patients may beinitially free of these comorbidities, during the long wait for a transplant,they may develop serious health conditions. Some of these would make thepatients ineligible for transplant, since performing a major surgery on themcan put them at an increased risk of mortality or serious post-transplantcomplications (Humar et al. [26]). Transplant centers try to avoid these out-comes by periodically re-evaluating waiting patients and temporarily puttingpatients they identify with such serious conditions on“inactive” (or “hold”)status (Danovitch et al. [18]).Among the different health conditions that waiting patients might de-velop, transplant centers are particularly concerned about cardiovasculardisease (CVD), as patients typically are not aware they have developed it52.1. Introductionuntil they undergo a screening test (Parfrey and Foley [52]). Studies haveshown that patients with CKD and patients on dialysis are at significantlyincreased risk of developing CVD (McCullough [38], Parfrey and Foley [52]).Also, several studies have noted that many complications after kidney trans-plant are associated with CVD (Humar et al. [26], Ojo et al. [50]). For in-stance, Ojo et al. [50] reports that in a population-based survival analysisof United States patients with ESRD transplanted between 1988 and 1997(a total population of 86,502 adult renal transplant recipients), almost halfof the deaths with a functioning graft in the first 30 days after transplantwere due to cardiovascular complications (the total number of deaths withfunctioning graft in this period was 7,040 deaths). This leads to a firmconsensus among transplant centers regarding the importance of follow-upcardiac evaluations (Gaston et al. [23]). However, while there are recom-mended guidelines for CVD screening policies for patients on the waitinglist, they do not appear evidence-based. Furthermore, transplant centersvary considerably in how frequently they screen patients, as they use a com-bination of expert judgment, resource considerations, and general guidelinesto come up with their own policies for screening patients (Danovitch et al.[18]).There are three main issues that make screening decisions challenging.First, when a deceased donor kidney becomes available, it must be trans-planted in a short period of time due to the fact that the prolonged timeoutside the body (cold ischemia time) reduces its functionality in the recip-ient (Salahudeen et al. [63]). Therefore, transplant centers do not have timeto start screening patients at the time a kidney is offered for donation. Thesecond issue is that one cannot know in advance with certainty to whichpatient the next available kidney will be offered. A kidney cannot be offeredto patients whose body may develop an immune response to the donatedkidney or whose blood type is not compatible with that of the donor, bothof which are determined only upon an organ becoming available for dona-tion. The last issue that complicates the screening process is that screeningresources are limited and costly. Obviously, by screening all the patients inshort intervals, transplant centers can maintain updated information abouteach patient. However, one must weigh the benefits of the extra screeningsagainst the costs and patient inconveniences of obtaining them. These issuesraise the important questions of which patients should be screened and howthe screening intervals should change as patients continue waiting. Our pri-mary contribution in this chapter is to recommend an analytical approachto answer these questions.The rest of this chapter is organized as follows. First we review rele-62.2. Literature Reviewvant literature in Section 2.2 and further describe our contributions to theliterature. In Section 2.3, we state our assumptions and present our formu-lation of the problem. We derive several structural properties of the optimalsolution in Section 2.4, and we exploit these properties to develop a solu-tion algorithm that finds the optimal solution. In Section 2.5, we apply ourmodel in the context of screening patients on the kidney transplant waitinglist. Finally, we discuss concluding remarks and future work in Section Literature ReviewIn this section, we review the relevant literature in two parts (clinicalliterature and operations management literature), and we elaborate on ourcontribution in light of the existing literature.2.2.1 Clinical literatureThe issue of maintaining and monitoring the kidney transplant waitinglist has been a challenge for the transplant community due to the persis-tent rise in the number of patients on the waiting list. Danovitch et al.[18] discussed this issue and summarized the results of a survey from 192transplant centers. The focus of this survey was on screening for CVD andindicated that there is considerable variability among centers regarding thefrequency and modality of the tests. They concluded that existing screeningpractice is not based on specific evidence and provided general recommenda-tions for transplant programs. Gaston et al. [23] summarized the issues andrecommendations regarding the kidney transplant waiting list addressed ata national meeting of the transplant community in 2002. It is mentionedin their report that “there is a widespread agreement among transplantprograms that repeated cardiovascular surveillance is required for many pa-tients awaiting a cadaver kidney transplant, with more intense monitoringfor high-risk patients. There is no firm consensus, however, as to who shouldbe tested, at what interval and with what modality.” For cardiac testing,the National Kidney Foundation [48] provided a set of recommendationsthat reflect the current screening policy in the U.S. (summarized in Table2.1). In British Columbia, Canada (the geographic region we model in ournumerical experiments of Section 2.5), on the other hand, the current policyis even simpler: screen “low-risk” patients every two years and “high-risk”patients annually, where high-risk is defined as a patient who is diabetic,age 50 or older, or who has a history of CVD treatment. Gill et al. [24],reporting on a study of British Columbia screening policy, concluded that72.2. Literature ReviewTable 2.1: Recommendations for cardiac surveillance of waitlisted patients.Category Screening intervalLow-risk every 3 yearsNon-diabetic high risk biannualdiabetic and/or with history of CVD treatment annualfurther studies to obtain optimal cardiac screening policies is necessary giventhe high cost of performing such tests and the uncertainty in the use of thecurrent policies highlighted in their study.2.2.2 OR/MS literatureOur work also relates to three bodies of work in the OR/MS literature:organ transplantation, disease screening, and machine maintenance.a) Transplant policies: The OR/MS techniques have proven helpfulin developing policies for many healthcare problems, including problemsrelated to organ transplantation. The research focus of the OM communityregarding the latter has been primarily in designing better allocation policiesfrom a societal perspective (e.g., Bertsimas et al. [14], Su and Zenios [71,72], Zenios [80], Zenios et al. [81]) or in improving accept/reject decisions oforgan offers from a patient perspective (e.g., Alagoz et al. [3, 4, 5], Sandikciet al. [64]). For instance, Zenios et al. [81] proposed a fluid model to findkidney allocation policies that optimize both clinical efficiency and equity,Su and Zenios [71] introduced a model for organ allocation that accountsfor the patients’ choice in accepting the organ, and Alagoz et al. [5] (in thecontext of liver transplant waiting list) provided a model to help patientsand their physicians decide whether to accept an organ offer of given quality.b) Disease screening policies: Several OR/MS papers have also exam-ined optimal screening policies for different diseases. For example, modelsof breast cancer screening have been studied in Ayer et al. [9], Kirch andKlein [32], Maillart et al. [35], Shwartz [70]. Maillart et al. [35], for exam-ple, used a partially observable Markov chain formulation to examine thevalue of dynamic screening policies in which the length of screening intervalcan be a function of patient age. Ayer et al. [9] provided a partially observ-able Markov decision process (POMDP) model to determine patient-specificmammography screening times.c) Machine maintenace policies: Our work is also related to the liter-ature on machine maintenance polices and inspection policies in particular,82.2. Literature Reviewas there are natural analogies between deciding when to inspect deterio-rating equipment over time and when to screen patients for disease. Forinstance, Zhang et al. [82], building upon this literature, developed a modelfor finding post-operative surveillance schedules for patients who have un-dergone vascular surgery. We review several relevant machine reliabilitypapers here and refer the reader to the following articles for an exhaustivesurvey of this literature (Chelbi and Ait-Kadi [15], Jardine and Buzacott[27], McCall [37], Nakagawa [47], Pierskalla and Voelker [59], Sherif andSmith [69], Valdez-Flores and Feldman [75], Wang [77]).Barlow et al. [11] examined the trade-off between inspection costs and apenalty cost, where the latter is proportional to the duration of time thatthe system runs while a failure is undetected. They developed structuralproperties of the optimal solution, as well as a method to find the optimalinspection times for a broad class of failure densities. Their framework isrelevant to the case of a manufacturing system in continuous operations,where failure results in the production of defective items, or in the health-care context where early detection of disease can result in a more effectivetreatment. Many extensions of the Barlow et al. [11] have been consideredin the literature. For instance, Luss and Kander [34] extended their modelto the case where the inspection time is not negligible, and Parmigiani [55]considered the case where inspections are prone to error. Also, Munford andShahani [39] provided a method for finding a nearly optimal inspection pol-icy for the model studied by Barlow et al. [11], which is easier to computeand performs well. Sengupta [68] studied the case where failure becomesevident after some random time due to the evident loss of product qualityor, in the patient context, due to the eventual development of symptoms.Whereas the above papers consider a continuous running cost for theduration of time a failure goes undetected, other reliability papers considercosts that occur at discrete times during a failed or deteriorated state. Forexample, Maillart and Pollock [36] considered a two-phase system in whicha component moves from “new” to “worn” after a random amount of time,and from “worn” to “failed” after another random amount of time. Costsaccrue for each inspection, preventive maintenance action (taken when aninspection finds a component in the worn state), and reactive maintenanceaction (taken upon component failure), and the objective is to minimize thetotal expected cost over a finite time horizon. Parmigiani [54] proposed amodel for finding optimal inspection policies for a stand-by component (e.g.,power generator), which will be needed at a random future time (e.g., timeof an emergency). In this case, there is no penalty for a delayed detection offailure, as long as it is detected before the standy-by component is needed92.2. Literature Review(at which time it can be replaced). However, if the stand-by component isin a failed state at the time it is needed, the consequences are severe. Theobjective in this setting is to minimize the expected number of inspections,subject to a maximum probability of finding the component is failed at thetime it is needed.2.2.3 Contributions to the literatureOur work contributes to the clinical literature by proposing the firstanalytical framework for evaluating the performance of different screeningguidelines. By integrating our analytical results at a patient-level perspec-tive (Section 2.4) with a detailed simulation of the entire transplant waitlist(Section 2.5), we show that our model-based results can significantly out-perform existing policies and other simple classes of policies. We believe thisprovides a foundation for developing more effective, evidence-based guide-lines.To our knowledge, our model is the first work in the OR/MS literaturethat addresses transplant waiting list management questions before an organbecomes available rather than after (i.e., allocation and acceptance/rejectiondecisions discussed above). Our problem considers how to best screen thewaiting list for the possibility of a kidney offer, which leads to different ob-jectives and methodologies for addressing them. Our screening problem isalso different from previous disease screening studies in the literature be-cause the goal in those is early detection and treatment of the disease whileconsidering the cost of performing the tests. In contrast, we consider theobjective of a transplant center, which is to identify adverse health condi-tions before a patient is called upon for a transplant, while also consideringcostly screening resources. Therefore, in this study, we seek to minimize thetotal cost from screenings as well as the cost associated with complicationsdue to transplants to patients with unknown CVD.Our analytical model and results have important similarities and differ-ences to some of the reliability papers reviewed above. In particular, ourtwo main results (Theorem 1, decreasing inspection intervals, and Theorem2, an algorithm for obtaining the optimal policy) were derived by adapt-ing similar results found in Theorems 5 and 6 of Barlow et al. [11]. Notethat other extensions of the Barlow paper also used similar techniques toprove the optimality of decreasing inspection intervals and to provide a cor-responding solution algorithm (e.g., see Theorems 2 and 3 of Sengupta [68]and Theorems 1 and 2 of Parmigiani [55]).Our contributions to the reliability literature are in 1) providing a differ-102.3. Problem Formulation and Assumptionsent extension to the original inspection problem of Barlow et al. [11], whichis motivated by a health care application, and 2) filling a gap in the resultsthat motivated previous solution algorithms in the literature. Regardingthe first part, our problem requires the consideration of three interactingprobability distributions: the time until the patient develops CVD, the timeuntil the patient will be offered a kidney and undergo transplantation, andthe time until the patient will die. The time until CVD development is anal-ogous to the time until component failure (Barlow et al. [11]), and the timeuntil calling upon the patient for a transplantation is analogous to the timeuntil a stand-by component is needed (Parmigiani [54]). To our knowledge,there has been no analogous consideration of our patient death distribution.This might occur in a reliability context, for example, if there were somerandom time until the component (and any identical replacements) becameobsolete.Regarding our second contribution to the reliability literature, we notethat previous results (e.g., Theorem 6 of Barlow et al. [11]) are incompletein that they do not prove “if and only if” statements. For example, in ourTheorem 2 part A of Section 2.4, we have the statement “there exists somem such that xj > xj−1 > 0 for all j ≥ m if and only if t1 > t∗1.” Theanalogous statement in the solution algorithm of Theorem 6 of Barlow et al.[11] has the “if” part of this but does not establish the “only if” part. Thesame holds for our Theorem 2, part B. While it is not difficult to establishthe forward directions (nor would it be for the analogous result of Barlowet al. [11]), it has significant practical importance for creating the binarysearch solution algorithms. One will not know in general whether or not theinitial choice of t1 is greater or less than t∗1, but rather will conclude thisbased on which of the two contradictions arises from the sequence of xj thatthe choice of t1 produces.2.3 Problem Formulation and AssumptionsWe first develop a model for the problem of screening an arbitrary patienton the waiting list. In Section 2.5, we discuss how this model, along witha discrete event simulation (DES) model, can be used to help a transplantcenter decide on screening schedules for all waiting patients. Provided thepatient survives long enough on the waiting list and is still regarded aseligible for transplant, a kidney will eventually be offered to this patient.Let T be the random variable representing this remaining waiting time. Inthe meantime, a patient might develop CVD without knowing it, and we112.3. Problem Formulation and Assumptionslet S represent the random variable for the time until this would happen,provided the patient survives that long. Furthermore, the patient might alsodie of any reason (CVD-related or not) randomly at time U . For the sake oftractability, we assume T, S and U are independent random variables andhave density functions g(t), f(s) and h(u), respectively. Later, we relax thisassumption in our simulation model by considering dependence between theCVD development time and the death time.If the decision maker (the transplant center) offers a kidney to the patientafter developing CVD (S < T < U) but before screening identifies it, apenalty cost cp is incurred due to the increased risk of complications duringand after the transplant. In other words, cp is the expected treatment costfor complications that result from offering a kidney to a patient with CVD.We let cs represent the cost incurred each time the transplant center screensa patient. We further discuss quantifying cost parameters in Section 2.5.5.We assume cs is significantly less than cp. Our goal is to find a screeningpolicy that minimizes the expected total cost, where a screening policy isdefined by an increasing sequence of screening times T ={tj}+∞j=1, where tjrefers to the scheduled time for the jth screening given that the patient isstill on the waiting list without any CVD detected.We assume that the support of T, S and U is [0,+∞) and f(s), g(t),and h(u) are positive for all positive s, t, and u. We assume h(u) has theincreasing failure rate (IFR) property, which is a natural property of aging.Moreover, f(s) and g(t) are continuous (and differentiable) Polya Frequencyfunctions of order 2 (PF2) density functions. Note that PF2 (or log-concave)density functions include a wide range of probability densities, including theExponential, Normal and Logistic distributions, as well as a large subsetof the Gamma and Weibull family. These distributions also have the IFRproperty, which makes them suitable for modeling the CVD time of agingpatients. Similar logic applies to the kidney offer time density since patientswith longer waiting times are more likely to receive a kidney offer. Finally,we assume that screenings are error-free and take negligible time to perform.We relax these assumptions in our simulation model of Section The expected cost of a screening policyThe expected total cost (C) of a screening policy is the sum of two costs:the expected penalty cost (P) and the expected screening cost (S). First,consider an arbitrary screening schedule, indicated by T . To derive P, wejust need to consider the probability of incurring the penalty cost betweenconsecutive screening times. The penalty cost cp is incurred in the interval122.4. Structural Results(tj−1, tj) if a kidney offer is made in this interval (say at time t), the patienthas developed CVD in the interval (tj−1, t) before the kidney arrival, andthe patient is still alive at time t:P(T ) = cp+∞∑j=1P(tj−1 < S < T < tj , U > T )= cp+∞∑j=1∫ tjtj−1g(t)(F (t)− F (tj−1))H¯(t)dt, (2.1)where t0 = 0. In deriving (2.1), we implicitly assume limj→∞tj = ∞, whichmeans that screenings are scheduled as long as the patient is on the waitinglist.Now consider the expected screening cost, S. We perform the jth screen-ing if the patient has not developed CVD by the time of (j − 1)th screeningand the kidney arrival and death have not occurred by the time of jth screen-ing:S(T ) = cs+∞∑j=1P(T > tj , S > tj−1, U > tj)= cs+∞∑j=1F¯ (tj−1)G¯(tj)H¯(tj). (2.2)By combining (2.1) and (2.2) we obtain the expected total cost of ascreening policy T as C(T ) = P(T ) +S(T ). In the next section, we use thisform of C(T ) to establish structured optimal policies and an algorithm forobtaining the optimal policy.2.4 Structural ResultsIn this section and Appendices A and B, we provide several propertiesof the optimal screening policy and use these properties to develop an al-gorithm for obtaining the optimal screening policy. Again, the perspectiveis that of the optimal screening policy for an arbitrary patient on the wait-ing list; we embed this single-patient optimal algorithm into a heuristic forscreening the entire waiting list in Section 2.5. To this aim, we consider thefirst order optimality condition. The expected total cost C(T ) is differen-tiable with respect to each tj since F (s), G(t) and H(u) are differentiable132.4. Structural Resultsfunctions (differentiability follows from the continuity of f(s), g(t) and h(u),respectively). Appendix A provides supporting Lemmas for the two theo-rems stated in this section, and Appendix B provides the proofs of thesetheorems.First, we need to impose the following technical assumption on the pa-rameters of our model. While this assumption is needed for our analysis,it holds for many instances of the problem that we solve in Section 2.5. Infact, Lemma 4 in Appendix A shows that for the case where g and h areWeibull densities, this assumption reduces to a condition only on the shapeparameters of such densities. In Section 2.5, we also discuss a method toobtain nearly optimal screening policies for the cases where this assumptiondoes not hold.Assumption 1 The function Λ(t) := cp − cs(1 + h(t)G¯(t)g(t)H¯(t))satisfies the fol-lowing two properties:(a) Λ(t) is increasing in t.(b) There exists some ψˆ such that Λ(t)H¯(t)g(t) is strictly decreasing in tfor all t > ψˆ.Lemma 3 in Appendix A establishes that the optimal screening policymust satisfy the first order necessary condition and cannot be a bound-ary solution (i.e., 0 < t1 < t2 < t3 < . . .). This Lemma also provides atool for characterizing the optimal screening policy. To be more specific,using the necessary condition we are able to reduce the dimension of thedecision variable space from +∞ to 1. The necessary condition (A.3) inAppendix A produces a relationship among the three subsequent values oft∗j ’s, i.e., {t∗j−1, t∗j , t∗j+1}. Since t0 = 0, we can use (A.3) to find recursively allthe screening times by just determining the optimal first screening time t∗1.Therefore, for screening policies that satisfy the necessary condition (A.3),the screening times are implicitly functions of t∗1.For ease of representation, we define the length of the jth screeninginterval as xj := tj − tj−1. Next we show that the length of the optimalscreening interval x∗j is always decreasing in j. In other words, we screenthe patient more frequently as time passes. This property is consistent withthe increasing failure rate property of the disease, as well as the fact thatpatients are more likely to receive a kidney offer as they move up the waitinglist.Theorem 1 In the optimal screening policy T ∗ ={t∗j}∞j=1, the lengths ofthe screening intervals{x∗j}∞j=1 are decreasing in j.142.5. Numerical ExperimentsThe decreasing-interval property proved in Theorem 1 is the most importantproperty of the optimal screening policy, and yet it is ignored by all of theconstant-interval screening guidelines used in practice (see Section 2.2.1).In our numerical experiments of Section 2.5, we show that constant-intervalpolicies are significantly outperformed by our decreasing-interval screeningpolicies.Our next step is to obtain the optimal screening policy. As we discussed,the optimal screening times can be obtained recursively using (A.3) afterobtaining the optimal first screening time t∗1. The following result motivatesour solution algorithm by providing us with a way of identifying a wrongchoice for the first screening time t1.Theorem 2 Let{xj}∞j=1 be the sequence of the lengths of the screeningintervals generated recursively from (A.3) after choosing a first screeningtime, t1 > 0. Let t∗1 be an optimal value of the first screening time t1. Then,the following holds:(A) There exists some m such that xj > xj−1 > 0 for all j ≥ m if andonly if t1 > t∗1.(B) There exists some m such that xj < 0 for all j ≥ m if and only ift1 < t∗1.Theorem 2 establishes that if a non-optimal first screening time t1 is cho-sen and being used to generate a sequence of screening time recursively using(A.3), it would result in some “contradiction” (we say “contradiction” sincexj > xj−1 > 0 is inconsistent with Theorem 1, and xj < 0 is inconsistentwith the constraint t1 ≤ t2 ≤ . . .). It also states that if the contradiction isof the kind “xj < 0 for some j”, then the current choice of t1 is less than theoptimal value t∗1, and if the contradiction is of the kind “xj > xj−1 for somej”, then the current choice of t1 is greater than the optimal first screeningtime t∗1. These conclusions also imply that the optimal screening policy isunique. To obtain the unique optimal first screening time t∗1, a binary searchalgorithm can be used since based on the guidelines of Theorem 2, we candecide whether t1 > t∗1 or t1 < t∗1.2.5 Numerical ExperimentsThis section describes how the results from previous sections can beapplied to the problem of screening patients on the kidney transplant waitinglist. First, we describe a data-driven discrete event simulation (DES) model152.5. Numerical Experimentswe developed of a kidney transplant waiting list. This serves two purposes:1) we can use the DES to evaluate any proposed screening policy, and 2)we use the DES to estimate the remaining waiting time density g for ouranalytical model, which are then used in our model-based screening policy(described in Section 2.5.3).2.5.1 Simulation of the kidney transplant waiting listOur DES is based on the kidney transplant waiting list of British Columbia,Canada. The main components of the model are as follows:1. Patient generation: The patient generation module creates ESRDpatients according to a Poisson process with rate 304 patients per year andassigns them various characteristics such as blood type, age, and gender.These characteristic are assigned randomly based on a probability distribu-tion obtained from historical data (see Section 2.5.2 for data sources).2. Health progression while waiting: The simulation program as-signs each patient a time at which the patient may develop CVD, as wellas a time of death. We use accelerated failure time models (Anderson et al.[6], Odell et al. [49]) for modelling the time of developing CVD and the timeof death. These models have common risk factors such as age, gender andbeing diabetic as covariates. Since these models are calibrated based ondata from the general population, we use a Cox proportional hazard modelto update them for ESRD patients (for instance, Foley et al. [21] and Sar-nak and Levey [65] report that CVD mortality in dialysis patients is 10-30times higher than in the general population). We remark that here the timeof CVD development means the time at which the severity of the diseasereaches the point that the transplant center would no longer consider thepatient eligible for a transplant. In the absence of a clear definition for thisevent, we assume that the definition used in Anderson et al. [6] matches thepractice of transplant centers.3. Kidney generation: Similar to the patient generation module, weuse British Columbia historical data to generate the time between kidney do-nations (average 6.1 days, exponentially distributed) and the donor’s bloodtype.4. Screening policy: The screening policy indicates at what times dif-ferent patients should undergo cardiovascular screening so as to update theirhealth status and eligibility for transplant. We consider imperfect screen-ings through their estimated sensitivity and specificity, as well as screeninglead time, which denotes the time until the results of the screening becomesavailable. In practice, screening is a two-stage process. In the first stage, a162.5. Numerical Experimentsnon-invasive test (e.g., echo-cardiogram or electrocardiogram) is performed.Patients are asked to take an invasive test (coronary angiography) only if theresult of the first stage tests is positive. If the overall result of the screeningprocess is positive, then the patient is placed on hold status at the timethe screening result becomes available. Also, the first stage tests are usuallyimperfect (i.e., have sensitivity and specificity of smaller than 1), where falsepositive test results increase the screening costs due to unnecessary follow-up tests, and false negative results lead to CVD cases that go undetected.Furthermore, the final outcome of the screening process becomes availableafter a non-negligible lead time (which we consider as exponentially dis-tributed with a mean of one month). Note that since for each patient thesimulation program has already assigned the true CVD development time,the result of each screening test can be easily determined given the sensi-tivity and specificity of the tests. The simulation program assigns a costto each screening performed, where the cost of the second-stage test is onlyapplied if the result of the first-stage test is positive.5. Allocation policy: After a kidney becomes available, the allocationpolicy indicates to which patient it should be offered. We use the allocationpolicy currently in place in British Columbia, which is primarily drivenby the waiting time and compatibility criteria, i.e., the kidney goes to thecompatible patient (cross-match negative, blood type compatible patient)who has been waiting the longest. If the kidney is offered to a patient whohas developed CVD that is not identified by any of previous screenings, weassign a penalty cost cp to this transplant (see Section 2.3 for the descriptionof cp).6. Outcomes/output: The main outcome of interest in our case isthe total cost. Other detailed metrics such as annual number of screeningsperformed or the annual number of CVD cases detected are also collectedby the simulation model.2.5.2 DataWe use publicly available data from different sources. The simulationmodel is based on the waiting list dynamics (patient and kidney arrivalrates, as well as allocation policy) that occur in British Columbia. However,the characteristics of the patients and kidneys are generated based on bothBritish Columbia and United States data, where the latter is used if we couldnot find the data for British Columbia. Patients’ CVD time distributionsare generated using accelerated failure time models introduced in Andersonet al. [6]. For a patient’s death time, we first generate a random time from a172.5. Numerical Experimentsdeath time distribution for a general ESRD patient (who has not developedCVD yet). If the generated time is after the patient’s CVD time, we updatethe death time by generating it from a death time distribution for a ESRDpatient who also has CVD, based on the model of Anderson et al. [6]. Table2.2 summarizes the main model components, parameter values, and datasources.182.5.NumericalExperimentsTable 2.2: Parameter values and data sources for main model components.Parameter Value SourcePatientArrival rate 304 ESRD patients per year †Age distribution (M)30-40 (0.176)1 40-50 (0.241) 50-60 (0.401)†60-70 (0.144) 70-80 (0.037)Age distribution (F)30-40 (0.177) 40-50 (0.301) 50-60 (0.345)†60-70 (0.168) 70-80 (0.009)Gender Probability of female: 0.45 ‡Blood type O (0.485) A (0.329) B (0.148) AB(0.038) ‡PRA score 0-10 (0.7520) 10-80 (0.1720) 80-100 (0.0760) ‡Diabetic Probability of diabetes: 0.6 ‡CVD time Accelerated failure time models Anderson et al. [6]Death time Accelerated failure time models Anderson et al. [6]KidneyTransplant rate 60 kidney transplants per year †Blood type O (0.474) A (0.372) B (0.123) AB(0.031) ‡ScreeningSensitivity Electrocardiogram: 0.68, Coronary Angiography: 1.00 Patterson et al. [56]Specificity Electrocardiogram: 0.77, Coronary Angiography: 1.00 Patterson et al. [56]Mean lead time 1 month ∗CostScreening cost ECG: $330, Coronary Angiography: $1800 Patterson et al. [56]Penalty cost $40,000 Patterson et al. [56]1 Numbers in parentheses represent probabilities.† Canadian Organ Replacement Register Report, 2010, and British Columbia Transplant Society (BCTS) data, 2006.‡ Organ Procurement and Transplantation Network (OPTN) data, 2011.∗ Discussion with transplant coordinators at BCTS.192.5. Numerical ExperimentsWhile limited public data make it difficult to perform extensive valida-tion of our model, we were able to compare observed median waiting timewith the ones reported by the British Columbia Transplant Society [12].The median waiting time experienced in British Columbia was 63.1 monthsfor patients transplanted in 2010 and 62.2 for patients transplanted in 2011,which are close to the median waiting time of 63.0 months observed fromthe simulation program.2.5.3 Model-based screening policyHere we discuss how we apply our analytical model of Sections 2.3 and2.4 to develop a model-based screening policy. Note that our analyticalmodel determines the optimal screening times for a single patient who faces aremaining waiting time (until kidney offer) density g and has CVD and deathtime densities f and h, respectively. In practice, a transplant center needsto develop a screening policy for all patients on the waiting list. However,it would be analytically intractable to derive a globally optimal solution fordeciding all patients’ screening times; the state space and decision spacewould quickly face the “curse of dimensionality.” Instead, we propose aheuristic that first assigns each new patient a screening schedule, derivedfrom our analytical model and solution algorithm of Section 2.4. We thendynamically update patients’ screening schedules as the waiting list evolvesand they move to higher ranks.The CVD and death time densities (f and h, respectively) are functionsof patient characteristics such as age, gender, and diabetes status, and areindependent of the waiting list dynamics and other patients’ characteris-tics. In contrast, the remaining waiting time density g for each patient isa function of the waiting list dynamics and depends on the characteristicsof patients who have higher priority over the considered patient. This iswhere we use the DES model for the purpose of estimating the density g fora patient, as we can run several replications of the model to obtain waitingtime samples, and then fit a distribution to the data. However, it wouldbe computationally expensive to do this for every patient at different timesduring the simulation run. Instead, we create a moderate number of cate-gories based on a few factors related to the waiting time distribution, and fitthese distributions offline. These factors are a patient’s rank on the waitinglist, blood type, and panel reactive antibodies (PRA) score.Rank is an important determinant of remaining waiting time, since kid-neys are offered in first-in-first-out order (provided the kidney is compatiblewith the intended recipient). A patient’s blood type is also a major factor202.5. Numerical Experimentsaffecting a patient’s waiting time. For instance, a patient of rank 50 withblood type AB will experience a much shorter waiting time compared to apatient ranked 50 with blood type O, since blood type AB is the universalrecipient and blood type O is the universal donor. The third factor, thepatient’s PRA score, estimates the percentage of the donor population thatthe patient would develop an immune response to, and thus be unable toreceive the donor’s kidney. Patients with lower PRA scores will wait less fora kidney offer. We consider all combinations of 30 rank (up to rank 300 ingroups of 10), 4 blood type (A, B, AB, O), and 3 PRA score (0-10, 10-80,80-100) categories, for a total of 360 waiting time distributions we fit usingthe DES model.We also group patients into 20 categories based on the primary factorsthat affect the CVD and death time distributions f and h: 5 age (30-80 ingroups of 10), 2 gender, and 2 diabetes status categories. We then use ouranalytical model of Sections 2.3 and 2.4 to obtain the optimal screening pol-icy for 7,200 (360× 20) different combinations of a patient’s characteristics.Since we dynamically update the optimal screening policy every month, foreach combination, we just store the first screening interval, t∗1 in a look-uptable. If the look-up value of t∗1 is within the next month, we screen thepatient. In the remainder of this chapter, we call this look-up table the“model-based” screening policy.Having this look-up table effectively allows us to implement a dynamicscreening policy. As an example, suppose that based on the current rank ofa patient, the optimal policy suggests that the patient should be screenedafter one year. However, after six months, the transplant center mightobserve that the rank of the patient decreased faster than expected dueto a higher donation rate in that six month period. They can then use theoptimal screening policy for the updated rank, which might suggest to screenthe patient much sooner than the six months that remain in the previousscreening schedule for that patient.We remark that for 14% of the 7,200 combinations, the particular setof parameters does not satisfy Assumption 1 described in Section 2.4, andtherefore our solution algorithm cannot be used to find the optimal patient-specific screening policy. For these cases, we find a nearly optimal policyusing a method inspired by Munford and Shahani [39]. In this method,given a probability p, we find the next screening interval in such a waythat the probability of offering a kidney to a patient with unknown CVDin that interval is equal to p. After obtaining the screening intervals, thetotal expected cost of such a policy (as defined in Section 2.3) can be easilycomputed. To find the best value for p, we try different values for p and212.5. Numerical Experimentschoose the one that minimizes the total expected cost. The correspondingscreening policy provides an approximation to the optimal policy. Whencompared against the optimal policy for the cases where Assumption 1 holds,we observed that the total expected cost is only 7% less for the optimal policyon average.Note that our analytical model in Section 2.3 only considers one param-eter, cs, for the screening cost, whereas in reality (and as our simulationmodel considers) there are two stages of tests, with the second stage beingsignificantly more expensive than the first stage (see Table 2.2 for cost esti-mates). To deal with this difference between our analytical and simulationmodels, we use an implied value of cs, which we define as the sum of thecost of performing the first non-invasive test (c1) and the expected cost ofperforming the second test (ac2), where a is the proportion of times that thesecond test is performed. Using the simulation program, we observe that forthe current screening policy, the second test is performed 36% of the time.We use this value as our estimate of a.2.5.4 Results and discussionThis section aims to provide insights and guidelines to policy-makers fordesigning more effective and efficient screening policies. Towards this aim,we perform several numerical experiments and discuss the importance ofdifferent variables in the design of improved screening policies.We first demonstrate the value of our model-based screening policy bycomparing its performance against the current guidelines of screening high-risk patients annually and low-risk patients every two years. We also com-pare our approach against the best among two other classes of screeningpolicies: “risk-based” and “rank-based” policies. A risk-based policy is ageneralization of the current guidelines, which assigns one fixed screeninginterval to high-risk patients, and another fixed screening interval to low-risk patients. We consider fixed intervals ranging from 3 months to 3 years,in increments of 3 months. For the rank-based policies, we consider a sin-gle rank threshold (50, 100, 150, 200, or 250) and assign different screeningintervals to the patients on different sides of this threshold. It is worthpointing out that instead of using the model-based policy, one might con-sider a simulation optimization approach. However, instead of searchingover an enormous decision space for good policies via common simulationoptimization approaches (e.g., genetic algorithms, tabu search, etc.), we useour analytical model to find a good screening policy.The results of our experiment are summarized in Table 2.3. We per-222.5. Numerical Experimentsformed 100 simulation replications of each policy, and each replication sim-ulates 1,000 kidney transplants after the warm-up period (which ends whenthe waiting list size matches the current waiting list size in British Columbia).The table provides the averages and the 95% confidence intervals for the fol-lowing three metrics: total annual cost, percentage of bad transplants (i.e.,transplants offered to patients with unknown CVD), and average annualnumber of screenings (both non-invasive and invasive). Note our policiesfocus on trying to minimize the total expected cost metric, but the othertwo metrics provide other outputs of interest for the transplant center.Table 2.3: Comparison of different screening policies.Screening policy Total annual Percentage of Average annualcost(million $) bad transplants number of screeningsCurrent 0.797 (±0.007) 20.9 (±0.2) 409.9 (±3.2)Best risk-based 0.714 (±0.007) 12.6 (±0.2) 592.8 (±4.8)Best rank-based 0.612 (±0.005) 7.2 (±0.2) 639.5 (±5.2)Model-based 0.511 (±0.005) 8.5 (±0.2) 429.1 (±4.0)First, we observe that the current screening policy results in 20.9% badtransplants and requires 409.9 screenings performed each year. We foundthat the best (lowest total cost) risk-based policy should screen high-riskpatients every six months and low-risk patients every year, which is halfof the intervals suggested by the current policy. Consequently, the annualnumber of screenings performed increases by 44.6%, but the total annualcost decreases by 10.5% due to the 8.3% decrease in the percentage of badtransplants. The best rank-based policy suggests screening the first 100 pa-tients every 3 months, and the rest every 3 years. Compared with the bestrisk-based policy, this policy performs 7.9% more screenings each year, butreduces the total annual cost and the percentage of bad transplants furtherby 14.2% and 42.8%, respectively. This suggests the importance of consid-ering factors highly correlated to remaining waiting time (e.g., rank on thewait list) in the design of patient screening guidelines. Our model-basedpolicy, which explicitly considers the remaining waiting time distribution,achieves a 17% reduction in total cost relative to the best rank-based policy.It does this by by requiring significantly lower annual number of screeningswith only a slightly higher percentage of bad transplants. Comparing themodel-based policy back to the current policy, we obtain a 35.9% reduc-tion in the total annual cost, by reducing the percentage of bad transplants232.5. Numerical Experimentsby 59.6% while using only 5% more screenings per year. The model-basedscreening policy achieves this efficiency by scheduling the screenings at pe-riods where the patient is more likely to receive an offer or have developedCVD.2.5.5 Comparison of policies in the face of cost uncertainty:Recall that we defined the penalty cost as the treatment cost of com-plications resulting from a transplant to a patient with unknown CVD. Inpractice, however, different complications might arise as a result of perform-ing a transplant on a patient with severe CVD, and the treatment cost forthese complications can significantly vary. Furthermore, the penalty costcan consider the opportunity cost of offering a kidney to a healthy patientinstead of a patient with severe CVD. All these issues make quantifying costparameters a difficult task in practice. Instead of focusing on the cost, Fig-ure 2.1 provides an alternative way for managers to understand the benefitof using our model-based policy over existing guidelines. Figure 2.1 depictstrade-off curves for the two primary (non-cost-based) metrics in our study:the percentage of bad transplants and the annual number of screenings.Each point of the figure corresponds to one screening policy. For the risk-based policies, each point is obtained by choosing different fixed screeningintervals for the two risk groups. Similarly, for the rank-based policies, eachpoint is obtained by choosing a rank threshold as well as two fixed screeningintervals for the two rank groups. We remark that the dominated policies ineach class are not shown in Figure 2.1. The different model-based policiesare obtained by changing the ratio of costs cpcs .Figure 2.1 shows that for any risk-based policy, one can find a dominatingrank-based policy (i.e., a policy with a smaller percentage of bad transplantsand smaller annual number of screenings performed). Furthermore, onecan find a model-based policy that outperforms both risk and rank-basedpolicies. Therefore, by using our model-based policies, one can always gainefficiencies in terms of both metrics. Our observation suggests that theinsight discussed earlier about the importance of considering the waitingtime in designing the screening guidelines does not change if different costfigures are used. Furthermore, the Pareto efficient curves shown in Figure 2.1provides a powerful tool to policy-makers for developing the right screeningguidelines, as they can choose a policy which balances their desired trade-off between the percentage of bad transplants and the amount of screeningsnecessary.242.6. ConclusionsFigure 2.1: Pareto efficient policies from different policy classes. The “best”coordinate for each policy reflects the values found in Table 2.3, which arebased on the baseline model parameters given in Table 2.2 .300 400 500 600 700 800 900 100000. number of screeningsProportion of bad transplants  Risk−based policiesRank−based policiesModel−based policiesBest risk−based policyBest rank−based policyBest model−based policy2.6 ConclusionsThis chapter provides a new modeling framework for finding improvedscreening policies for patients on the kidney transplant waiting list. Wenot only provide the first evidence-based tool for designing such policies,but also highlight several important insights regarding good policies. Ourmodel balances the trade-off between two costs: the penalty cost as a resultof offering a kidney to a patient with unknown CVD and screening costs.We prove several properties of the optimal patient-specific screening policyfor this model and use these properties to develop a binary search solutionalgorithm. In particular, we show that the lengths of the screening intervalsare decreasing under reasonable assumptions. Later, with the help of adiscrete event simulation model, we suggest a heuristic method that usesour single-patient model to develop dynamic screening policies within themulti-patient waiting list setting.252.6. ConclusionsThe current screening policies are based on simple rules which may beeasier to follow in practice. However, as we discussed earlier, transplantcenters view these policies as general guidelines and deviate from them byperiodically reviewing each patient’s information. On the other hand, themodel-based policy developed by our model can be summarized in the formof a look-up table (based on age, gender, diabetes status, blood type, PRAscore, and rank) that indicates how long a transplant center should waitbefore requesting a new screening. The screening schedule is obtained bythe binary search algorithm of our analytical model, and therefore our ap-proach may be seen as an efficient alternative to a general simulation-basedoptimization approach to finding screening policies. We also note that ourlook-up table can be easily implemented in the form of a spreadsheet, andbased on our discussion with British Columbia transplant coordinators, thiswould significantly facilitate the screening process.As mentioned in Section 2.3, our analytical model of Section 2.3 madesome simplifying assumptions that may pose limitations: perfect testing,and zero lead time for test results. Our DES model, on the other hand,relaxed each of these assumptions and reflected the reality of the process. InSection 2.5.3, we discussed our approach for mitigating the first assumptionby estimating a screening cost parameter of the model (cs) that reflected thetwo stages of testing that occur in practice. The incorrect assumption of azero lead time would only matter if a patient had developed CVD since thelast screening and a kidney were offered to the patient during the time ittook to receive the test results of the new screening. The probability of thishappening will be negligible for patients further down the waiting list butmay be worth considering for patients with shorter times until receiving akidney offer. Despite the disconnect between aspects of our analytical modeland the simulation model, our model-based screening policy performed wellcompared to other classes of policies.Our numerical experiments provide several important insights regardingthe effective and efficient screening policies. First, we observe that variable-interval screening policies perform better than the fixed-interval policies usedin practice. Furthermore, our results suggest that the factors affecting thewaiting time of the patient, such as rank and blood type, should be con-sidered in determining the screening intervals. This contrasts sharply withcurrent guidelines which are only based on patients’ risk for developing CVD.Finally, we note that while our numerical results are based on data for theBritish Columbia Transplant Center, our framework can be easily appliedto other regions by using appropriate data to calibrate the various modelparameters.26Chapter 3Inspecting a VitalComponent Needed uponEmergency3.1 IntroductionConsider a vital component that fails after some random amount oftime and that will be needed at some other random future time when anemergency occurs. If the component is not operational at the time of theemergency, the system incurs a large penalty cost. Failures are hidden andrevealed only upon inspections or upon attempted usage, at which time thecomponent is replaced (or repaired). Furthermore, the component can bereplaced preemptively after some time.As an example, consider stand-by safety systems, such as smoke detec-tors and fire alarms, that are needed in emergencies. As stand-by units, theirfailure may go unnoticed until they are needed, which could result in verycostly or even catastrophic outcomes. For instance, the National Fire Pro-tection Association reports that 24% of fire deaths in the US between 2005and 2009 resulted from fires in homes in which smoke alarms were presentbut did not operate (Ahrens [2]). Regular inspections of such systems isclearly important, though it is not obvious how frequently to perform suchinspections. Maintaining emergency back-up equipment, such as power gen-erators, is another application of this problem. For instance, during a majorstorm, scattered power outages can require the use of standby power systemsinstalled at hospitals, commercial businesses, and government buildings. Ifthe backup generators are not working at these times, there may be majorconsequences.There are several important questions in designing a cost-effective main-tenance plan for these systems, which arise from the trade-offs among dif-ferent decisions. First, there is a trade-off between performing frequentreplacements, accumulating high replacement costs, versus infrequent re-273.2. Literature Reviewplacements, with higher risk of failure happening prior to the attempteduse. In other words, the first decision is determining the right time to re-place the component (i.e., the cycle length). This preemptive replacementcan be delayed by scheduling inspections to detect the component failure.However, as the component ages and is more likely to fail, inspections mustbe scheduled more frequently, and their increasing cost can make delayingthe replacement no longer economical. Therefore, one should decide on theright number of inspections performed in each cycle before replacing thecomponent. Finally, one should decide how to space the inspections withina cycle so as to effectively reduce the likelihood of a catastrophic outcome(i.e., attempting to use a failed component). We answer all these questionsand provide several managerial insights for designing the optimal policy.The rest of this chapter is organized as follows. First we review therelevant literature and indicate the contribution of our work in Section 3.2.In Section 3.3, we state our assumptions and present our formulation of theproblem. We derive several structural properties of the optimal solution inSection 3.4, and we exploit these properties to develop a solution algorithm.In Section 3.5, we present and discuss numerical examples. Finally, wediscuss managerial insights and future work in Section 3.6. Proofs of mainresults appear in the appendix.3.2 Literature ReviewOptimal inspection policies have such a rich history in operations man-agement that several articles have surveyed this literature (Chelbi and Ait-Kadi [15], Jardine and Buzacott [27], McCall [37], Nakagawa [47], Pier-skalla and Voelker [59], Sherif and Smith [69], Valdez-Flores and Feldman[75], Wang [77]). Of particular relevance to our setting is a seminal paperby Barlow et al. [11] on optimal inspection policies and various extensionsof the ideas therein. They considered an inspection problem in which theyassumed that (a) system failure is known only through inspection, (b) in-spections do not degrade the system and take negligible time, (c) a costis associated with each inspection (d) a cost is associated with each unitof time that the failure is undetected, and (e) the problem ends upon de-tection of the failure. Note that assumption (d) makes this model suitablefor a system in continuous operation (such as a production system), wheresystem failure may result in producing defected items proportional to theduration of the time that the system has failed. Barlow et al. [11] developedstructural properties of the optimal solution, as well as a method to find283.2. Literature Reviewthe optimal inspection times for a broad class of failure densities. Barlowand Proschan [10] relaxed assumption (e), and extended their analysis tothe case where the component is replaced upon detection of failure. Theyconsidered the objective of expected cost per unit of time over an infinitehorizon.Many other extensions to Barlow et al. [11] have been considered in theliterature. Luss and Kander [34] extended their model to the case wherethe inspection time is not negligible. Sengupta [68] considered a systemfor which failure becomes evident at some random time after failure. Forexample, in a manufacturing process, the operator eventually would detectthe machine failure because of the deterioration in product quality. Parmi-giani [55] considered a system where the inspections are fallible and takenon-negligible time.While the papers mentioned above assign a penalty cost for each unitof time that the failure is undetected, in our problem, a fixed penalty costis incurred only if one attempts to use a failed component. This relates toliterature examining inspection policies for stand-by systems. For example,Nakagawa [46] considered inspection policies for a stand-by unit that re-places the main unit if it fails. He assumed the inspection times are equallyspaced and the problem ends when the main unit fails. With these assump-tions, he considered the problem of finding the inspection interval that min-imizes the expected cost, and found sufficient conditions for the existence ofthe optimal inspection interval. However, he did not provide any algorithmto obtain one. Whereas Nakagawa [46] studied the problem of determiningthe optimal inspection interval within the class of policies of equally spacedintervals, Thomas et al. [73] modeled the problem as a discrete Markov deci-sion process to find the inspection/repair times that maximizes the expectedtime until a catastrophe occurs (i.e., stand-by unit is needed but it is notoperational). Their model considered that inspections are fallible and theinspection and repair durations are not negligible. Sabouri et al. [62] con-sidered the problem of screening patients on the kidney transplant waitinglist and modeled it as a type of inspection model for a stand-by system.Another stream of models developed for systems in standby or storageconsider system availability (ratio of the system up time to the total of sys-tem up and down times) as the primary performance criterion instead of theaverage total cost. The goal in these models is to maintain a certain level ofavailability with minimum inspection effort. Parmigiani [54] considered theinspection of stand-by units in continuous time by minimizing the expectednumber of inspections under the constraint of a maximum probability thatthe stand-by unit is not ready upon the failure of the main unit. He used an293.2. Literature Reviewapproach similar to Barlow et al. [11], and by imposing certain assumptionson both the failure distributions, he provided an algorithm to obtain theoptimal inspection times. Yeh [78] developed a model to find an optimalinspection-repair-replacement policy that maintains a certain level of avail-ability at any time and minimizes the long-run expected cost per unit time.As suggested in Kim and Thomas [31], the models studied by Yeh [78] andseveral other authors did not consider the case where the need for the com-ponent changes over time. In contrast, Kim and Thomas [31] characterizedthe optimal repair decisions in the case where the need for the equipmentvaries over time according to a Markov chain. However, their model did notconsider finding an optimal inspection schedule.Our model in this chapter assumes that inspections only reveal whetherthe system has failed or not. While this assumption is reasonable for sev-eral applications (e.g., fire alarms), it is worth mentioning that a more re-cent stream of research considers situations where at the time of an inspec-tion, the degree of equipment degradation can be determined by performingmeasurements. Then, preventive replacement is performed when a certainthreshold of equipment degradation is reached. The focus of these condi-tional maintenance models (reviewed in Chelbi and Ait-Kadi [15]) is eitherin finding an optimal inspection policy for a given threshold or finding theoptimal threshold for a given inspection schedule. As an exception, Dieulleet al. [20] proposed a model to optimize both the threshold and the inspec-tion schedule.Our contributions to the literature are as follows. First, instead of focus-ing on an availability criterion, we consider a system in which componentfailure is only a problem at certain times (i.e., time of emergency), andtherefore it is critical that our objective function considers the interactionsbetween the component failure distribution and the emergency time distri-bution. In this context, we consider the optimal design of a joint inspectionand preventive maintenance policy by finding the optimal number of in-spections and their timings before a preventive replacement. Second, ouranalysis of the case where only a finite number of inspections are scheduledreveals a property of the optimal inspection schedule which contrasts withthe structure of optimal policies for models with an unlimited number ofinspections (Theorem 3). We also provide insights on the impact of changesin the model parameters by solving several numerical examples. Finally, weexplore the performance of constant interval (periodic) inspection policies,and provide insights on the performance loss when one is restricted to thisclass of policies.303.3. Problem Formulation and Assumptions3.3 Problem Formulation and AssumptionsThe time between emergencies is a random variable, which we denoteby T . We suppose that at the time of emergency, a vital component isneeded (e.g., back-up power generator), and an attempt will be made touse it. This component deteriorates over time and has a random lifetimeS (independent of T ), where the probability density function of S is f(s),and its cumulative distribution function is F (s). If the component fails andthe failure remains undetected until the emergency occurs (we refer to thisevent as a catastrophe), the system incurs a penalty cost, cp, at the time ofthe emergency (as the component cannot be used). Failure can be detectedonly by inspection, at a cost of ci per inspection. We assume that uponidentifying component failure (either before or at the time of emergency),upon using the component at the time of emergency, or at a scheduled timein future, it is replaced (or repaired to become as good as new) in negligibletime at a replacement cost of r (in addition to possibly cp or ci). We alsoassume that:1. the remaining time until the next emergency is independent of the timethat has passed since the last emergency (i.e., the memoryless propertyholds), and therefore T has an exponential probability density functionwith parameter λ (i.e., g(t) = λe−λt).2. f(s) is a continuous (and differentiable) Polya Frequency functions oforder 2 (PF2), and the support of S is [0,+∞) and f(s) > 0 for alls > 0. Note that PF2 density functions include a range of probabil-ity densities, including all Exponential and Normal distributions, aswell as a large subset of the Gamma and Weibull family. These distri-butions have the increasing failure rate property, which makes themsuitable lifetime distributions for components subject to deteriorationover time.3. ci < cp and r < cp; otherwise, we are not willing to perform inspectionsor replace the component to avoid the penalty cost. Furthermore,inspections are error-free, take negligible time to perform, and do notaffect the failure rate of the component.4. the planning horizon starts with a newly replaced component.Our model considers that a decision maker can perform a preventive re-placement if it is no longer economical to perform further inspections. Thismay happen if the interaction between the component failure rate and the313.3. Problem Formulation and Assumptionsemergency time distribution requires a very high inspection frequency toavoid the large penalty cp. Therefore, we must identify the optimal num-ber of inspections to perform before scheduling a preventive replacement.Toward this aim, we first formulate a subproblem for finding the optimaltiming of the inspections and the replacement for a given number of inspec-tion opportunities per cycle (the time between replacements). Then, onecan solve several instances of this problem to obtain the optimal number ofinspection opportunities.Since the emergency arrival density has the memoryless property, a re-newal happens each time the component is replaced. For the subproblem,we assume that there are a limited number n of inspection opportunitiesduring each cycle, and that any time after performing n inspections, the de-cision maker can preventively replace the component. Our goal is to find aninspection policy for each cycle that minimizes the infinite horizon expectedtotal discounted cost C. An inspection policy is defined by an increasingsequence of inspection times Tn ={tj}n+1j=1 (where t1 ≤ t2 ≤ . . . ≤ tn ≤ tn+1and tn+1 is the scheduled replacement time). Note that since the problemrenews itself after each cycle, the same inspection policy is optimal for eachcycle. Therefore, without loss of generality, we restrict our attention to theclass of policies where the same inspection policy is used for all cycles, andwe set the beginning of each cycle to time 0. Then, tj represents the timesince the last renewal, and C(Tn) represents the infinite horizon discountedexpected total cost when in each cycle we use the same inspection policy Tn.We revisit the optimal choice of n in the numerical results of Section The discounted expected total cost of an inspectionpolicyEach cycle ends with a replacement in one of the following four ways:(a) by identifying failure upon emergency, (b) by identifying failure uponinspection prior to an emergency, or (c) by replacing the component at thescheduled time tn+1, or (d) by using the functioning component upon emer-gency (in which case we assume it needs to be replaced or restored to newcondition at the same cost). The objective function can be written recur-sively based on which of these scenarios causes a component replacement.In equation (3.1), the first three summands correspond to these cases (case(c) is combined with (b)), respectively, and the last expression is the total323.3. Problem Formulation and Assumptionsdiscounted expected inspection cost in one cycle:C(Tn) = (cp + r + C(Tn))A1(Tn) + (r + C(Tn))A2(Tn)+ (r + C(Tn))A3(Tn) + ciA4(Tn). (3.1)Now we explain and derive the different expressions in equation (3.1). Thefirst expression, (cp + r+ C(Tn))A1(Tn), represents the discounted expectedcost if a failure remains undetected until the time of an emergency (mean-ing A1(Tn) can be viewed as the discounted probability of such an event).To derive the A1(Tn), suppose that the emergency occurs at some time t(according to density function g(t) = λe−λt) between the jth and (j + 1)stinspection times (i.e., tj < t < tj+1) and the component is still operatingat time tj (which occurs with probability 1−F (tj)). Then the penalty costis incurred if the failure happens in time interval (tj , t), which occurs withconditional probability of F (t)−F (tj)1−F (tj) . Letting θ be the discount factor, itfollows that the discounted probability of incurring the penalty cost isA1(Tn) :=n∑j=0(1− F (tj))∫ tj+1tjF (t)− F (tj)1− F (tj)λe−λte−θtdt=n∑j=0∫ tj+1tj(F (t)− F (tj))λe−λte−θtdt,where t0 = 0. The second expression, (r + C(Tn))A2(Tn), represents thediscounted expected cost if either one of two replacement scenarios occur: afailure is detected by inspections or a replacement takes place at the sched-uled time tn+1. For j ≤ n, we detect a failure at time tj if the componenthas failed in interval (tj−1, tj) and the emergency has not occurred by thetime of jth inspection. Furthermore, a preventive replacement is performedat time tn+1, if the component is still functional at the time of last inspectiontn and the emergency happens after the time of replacement tn+1. Then,similar to the previous case, we can writeA2(Tn) :=[ n∑j=1(F (tj)− F (tj−1))e−λtje−θtj]+(1− F (tn))e−λtn+1e−θtn+1 .The third expression, (r + C(Tn))A3(Tn), corresponds to the discountedexpected cost if the component has not failed by the time of emergency,in which case the emergency prompts the use of a good component, which333.3. Problem Formulation and Assumptionsneeds restoration/replacement after use. Similar to the derivation of A1(Tn),one can show thatA3(Tn) :=n∑j=0∫ tj+1tj(1− F (t))λe−λte−θtdtFinally, the fourth expression, ciA4(Tn), is the total discounted expectedinspection cost in one cycle induced by policy Tn. We derive this using theexpected sum of indicator functions∑nj=1E[Ij ], where each Ij = 1 if thejth inspection is performed and 0 otherwise. Then, the expected numberof inspections performed is equal to the sum of the probabilities that eachinspection is performed for j = 1, . . . , n. We perform the jth inspection ifthe component has not failed by the time of (j − 1)th inspection and theemergency has not occurred by the time of jth inspection. The correspondingprobability associated with this event is (1 − F (tj−1))e−λtj . Therefore, wehaveA4(Tn) :=n∑j=1(1− F (tj−1))e−λtje−θtj .Now, we can rewrite (3.1) as follows:C(Tn) =(cp + r)A1(Tn) + rA2(Tn) + rA3(Tn) + ciA4(Tn)1−A1(Tn)−A2(Tn)−A3(Tn)=N (Tn)D(Tn), (3.2)where N (Tn) and D(Tn) are defined as the numerator and the denominatorof the ratio after the first equality sign, respectively. Our goal is then to findan inspection policy that minimizes the above ratio. To this aim, we define:Lα(Tn) := N (Tn)− αD(Tn), and (3.3)R(α) := minTnLα(Tn). (3.4)Our problem is then equivalent to finding an α∗ such that R(α∗) = 0, sinceit implies that for any Tn, N (Tn) − α∗D(Tn) ≥ R(α∗) = 0 (i.e., C(Tn) =N (Tn)D(Tn)≥ α∗). It follows that T ∗n (α∗), the minimizer of (3.4) for α∗, is theoptimal inspection policy that minimizes (3.2) (because N (T∗n (α∗))D(T ∗n (α∗))= α∗).There exists a unique α∗ that solvesR(α) = 0, sinceR(0) > 0, andR(α) < 0for any α > N (Tn)D(Tn) (where Tn is any arbitrary inspection policy), and R(α)is continuous and strictly decreasing in α (since ∂R(α)∂α = −D(T∗n (α)) < 0 bythe envelope theorem and since D(Tn) is strictly positive due to discounting).343.4. Structural ResultsTherefore, we can find α∗ by performing a simple binary search. Then, foreach candidate value α = α˜, we need to find the optimal inspection policyT ∗n (α˜) that minimizes Lα˜(Tn). In Section 3.4, we discuss the properties ofthis minimization problem and provide an algorithm to obtain T ∗n (α˜).We remark that the above approach for minimizing (3.2) is referred toas λ-minimization and was previously discussed and studied in Aven andBergman [8].3.4 Structural ResultsIn this section, we provide several properties of the optimal inspectionpolicy and use these properties to develop an algorithm for obtaining the op-timal inspection policy. We remark that since the optimal inspection policyfor (3.2) is also the optimal inspection policy of (3.4) for α∗, it also satisfiesall the properties presented in this section. Also, in this section, we treatα as a parameter and discuss solving the problem (3.4) for a fixed valueof α. Therefore, we do not show the dependence of the optimal inspectionpolicies on α in our notation. Before characterizing and identifying an opti-mal inspection policy, one first must establish its existence (later we discussuniqueness as well). Proposition 3 in Appendix A shows the existence ofan optimal inspection policy for problem (3.4) for any given value of α. Wedenote this policy by T ∗n .Now we consider the first order optimality condition. The function L =Lα defined in (3.3) is differentiable with respect to each tj since F (s) is adifferentiable function (differentiability of F (s) follows from the continuityof f(s)). The following lemma establishes that the optimal inspection policymust satisfy the first order necessary condition and cannot be a boundarysolution (i.e., 0 < t1 < t2 < . . . < tn−1 < tn < tn+1). The first ordernecessary condition provides a tool for characterizing the optimal inspectionpolicy. To be more specific, using the necessary condition, we are able toreduce the dimension of the decision variable space from n + 1 to 1, whichwe discuss more following Lemma 1. It is first useful to define:Ω(t, x, y) :=[F (t)− F (t− x)f(t)−1− e−(λ+θ)yλ+ θ]−cik[1− F (t)f(t)+1λ+ θ],(3.5)where k = λλ+θ (cp+r+α)−(ci+r+α). We assume that k > 0 for all instancesof the problem (3.4) that we solve. This assumption holds when the penaltycost cp is significantly larger than the inspection cost ci and the replacement353.4. Structural Resultscost r, or if the discount factor θ is small. In most practical settings, thisassumption must hold to justify performing inspections and replacements.Function Ω(t, x, y) will be used in Lemma 1, as well as in proving severalproperties of the optimal inspection policy. Also, for ease of representation,we define the length of the jth inspection interval as xj := tj − tj−1.Lemma 1 Any optimal inspection policy T ∗n ={tj}n+1j=1 satisfies 0 < t1 <. . . < tn < tn+1 < ∞. Furthermore, necessary conditions for the optimalityof an inspection policy areΩ(tj , xj , xj+1) = 0 for each 1 ≤ j < n, (3.6)Ω(tn, xn, xn+1) = −cie−(λ+θ)xn+1k(λ+ θ), (3.7)F (tn + xn+1)− F (tn)1− F (tn)=θ(r + α)λcp. (3.8)The necessary conditions (3.6-3.8) produce a relationship among thethree subsequent values of tj ’s, i.e., {tj−1, tj , tj+1}. Since t0 = 0, we canuse (3.6) and (3.7) to find recursively all the inspection times by just de-termining the optimal first inspection time t1. Therefore, for inspectionpolicies that satisfy the necessary conditions (3.6-3.8), the inspection timesare implicitly functions of t1,n (note we use the second subscript n to denotethe total number of inspection opportunities available); thus, we denote theinspection times by tj [t1,n] and the length of the inspection intervals byxj [t1,n] to indicate this dependence.Now we use properties of PF2 densities (Lemma 9 of Appendix A) to de-velop some useful insights on the optimal inspection policy. Intuitively, theincreasing failure rate property of PF2 densities should induce decreasinglengths of inspection intervals as the component ages. In fact, other papersin the reliability literature have shown that when there are an unlimitednumber of inspection opportunities, the lengths of the inspection intervalsare indeed decreasing in other contexts (e.g., Barlow et al. [11], Sengupta[68] and Parmigiani [54]). In contrast to these papers, our model consid-ers a random variable for the time of emergency in addition to the failuretime, and schedules only a finite number of inspections, after which, thecomponent can be replaced. We will demonstrate in the numerical results ofSection 3.5 that in our setting, inspection intervals may decrease at first butincrease for later inspection intervals. The intuition is that in certain set-tings, one might use the inspection opportunities more conservatively whenfewer of them remain and during periods where it is less likely to experience363.4. Structural Resultsan emergency. This is formalized through the following theorem, which in-dicates that if there is an increase in duration from one interval to the next,the remaining intervals continue to increase.Theorem 3 Suppose that T ∗n ={tj [t∗1,n]}n+1j=1 is an optimal inspection pol-icy. If there exists m ∈ {1, . . . , n− 1} such that xm+1[t∗1,n] > xm[t∗1,n], thenxj+1[t∗1,n] > xj [t∗1,n] for all m ≤ j ≤ n.Note that Theorem 3 does not imply that the optimal inspection intervalsnecessarily increase; just that if there is an increase, then all subsequentintervals are also increasing in length.Now we establish other properties of the inspection policies that satisfythe necessary conditions (3.6-3.8). We mentioned that for these inspec-tion policies, the inspection times are implicitly functions of t1,n. Our nextlemma states how tj [t1,n] and xj [t1,n] change as functions of t1,n. This sen-sitivity result will also be used to show that the optimal inspection policyis unique. Furthermore, this result plays a crucial role in developing thesolution algorithm for finding the optimal inspection policy.Lemma 2 For any 1 ≤ j ≤ n+1, xj [t1,n] and tj [t1,n] are strictly increasingin t1,n.We can use Lemma 2 to prove that a unique value of t1,n satisfies the nec-essary conditions (3.6-3.8), and therefore, the optimal inspection policy isunique. Our solution algorithm is based on finding this unique optimal valueof t1,n.Proposition 1 The optimal inspection policy T ∗n ={tj [t∗1,n]}n+1j=1 is uniquefor all n.Now we briefly discuss an algorithm for finding the optimal inspectionpolicy (details of the algorithm can be found in Appendix E). Based on thediscussion following Lemma 1, finding the optimum first inspection time t∗1,nsuffices to determine the entire optimum inspection policy by using (3.6) and(3.7) (note that by Proposition 1, the optimal inspection policy is unique).Our algorithm uses Lemma 2 to perform a one-dimensional binary search todetermine the optimal first inspection time t∗1,n. The rest of the inspectiontimes can then be determined using (3.6) and (3.7).373.5. Numerical Examples3.5 Numerical ExamplesIn the previous section, we established properties of the optimal inspec-tion policy and outlined how we can use them to develop a solution algo-rithm. In this section, we explore the effect of changes in the model parame-ters as well as the effect of the availability of more inspection opportunities.Finally, we compare the performance of the optimal inspection policy withthe best constant interval inspection policy (where the inspection times arescheduled equally-spaced from each other), which is easier to compute andimplement.To perform our experiments, we used Matlab 7.13 to implement oursolution algorithms. It took negligible time to find the optimal inspectionpolicy in all of our experiments. For our base-case scenario, we assumecp, ci and r are equal to 1000, 1 and 10, respectively. Furthermore, weassume that the emergency arrival time has an Exponential density withrate λ = 0.2 (i.e., g(t) = 0.2e−0.2t), and the component fails according to aWeibull density function (f(s) = γβ(sβ)γ−1e−(s/β)γ), where γ = 2 and β = 5.These instances of the emergency arrival and component failure densitieshave (mean, standard deviation) of (5, 5) and (4.46, 1.62), respectively. Notethat the Weibull distribution is commonly used to model failure times andfor γ = 1, it coincides with the Exponential distribution. It is also knownthat the Weibull density is PF2 for values of γ ≥ Effect of changes in the number of availableinspection opportunitiesIn this section, we explore the impact of having access to more inspectionopportunities. In other words, we investigate how the optimal inspectionpolicy T ∗n and the optimal discounted expected total cost C(T∗n ) change asthe limit n on the number of available inspection opportunities per cycleincreases.In Figure 3.1a, we see that the discounted expected total cost corre-sponding to the optimal inspection policy for the base-case strictly decreasesat first when more inspection opportunities are available, but it becomesstrictly increasing for n ≥ 9. The cost becomes increasing because as thecomponent ages, it requires more frequent inspections to protect against thecatastrophe, which is costlier than replacing the component. Therefore, inthis example, it is optimal to have nine inspection opportunities per cycle.Figure 3.1b depicts the optimal inspection policy for different valuesof n, where each dashed curve corresponds to one value of n, and the star383.5. Numerical ExamplesFigure 3.1: The optimal inspection policy and the optimal discounted ex-pected total cost (DETC) for different values of n (F represents the replace-ment interval tn+1 − tn).(a) Optimal DETC for different n0 5 10 15 20 25 30 35 40190200210220230240250260Number of inspection opportunities (n)Optimal discounted expected total cost(b) Optimal inspection policies for different n1 2 3 4 5 6 7 8 index (j)Interval length (t  j−t j−1)n=0n=1n=8393.5. Numerical Examplescorresponds to the replacement interval after the last inspection. We observein Figure 3.1b that for fixed n, the length of the inspection intervals arestrictly decreasing (i.e., inspections are scheduled closer to each other asthe component ages), which is consistent with the increasing failure rateproperty of the failure density. However, this need not hold for all sets ofparameter values. If we change γ from 2 to 1.2, Figure 3.2a shows how fordifferent values of n, inspection intervals are strictly decreasing at first, andwhenever the lengths of the inspection intervals become strictly increasing,they remain strictly increasing, as predicted in Theorem 3. The reasonfor this behavior is that the failure rate increases at a slower rate whenγ = 1.2 (compared to the base-case of γ = 2), and the optimal inspectionpolicy is mostly derived by the emergency time distribution, meaning thatinspections are scheduled during periods where it is more likely that anemergency occurs sooner rather than later when a failure is more likely.We also observe in Figure 3.1b that for a fixed j, the length of theoptimal inspection interval x∗j,n[t∗1,n] = t∗j,n[t∗1,n] − t∗j−1,n[t∗1,n] is strictly de-creasing in n, meaning that we schedule inspections closer to each otheras more inspections become available. While this may also seem intuitive,Figure 3.2b demonstrates that this also is not a necessary condition of anoptimal inspection policy. In this example, ci is increased from 1 to 8 (allother baseline parameters being the same), which is close to the replacementcost (r = 10). Consequently, performing inspections and postponing the re-placement is not as beneficial as before. Therefore, the optimal inspectionpolicy schedules the inspection times farther apart to decrease the expectedinspection cost because the resulting savings justify a slight increase in theprobability of catastrophe.3.5.2 Effect of changes in the failure time distributionFor our second experiment, we evaluate how sensitive our results are tochanges in the component failure time density. In particular, we considerhow changes in the probability density f interacts with g to affect cost. Wedo this by fixing the rate of emergency probability density λ at 0.2 andvarying the parameter β from the Weibull distribution for the componentfailure time. In Figures 3.3a, 3.3b and 3.3c, we plot the discounted expectedtotal cost, the probability of catastrophe in each cycle, and the expectednumber of inspections performed in each cycle, respectively, induced bythe optimal inspection policy (for the case n = 9). However, instead ofusing β for the horizontal axis, we use a more intuitive indicator, p, whichis defined as the probability that the failure occurs before the emergency403.5. Numerical ExamplesFigure 3.2: Examples of the optimal inspection policy with counter-intuitiveproperties.(a) The lengths of the inspection intervals can be increasing forfixed n (for γ = 1.2).1 2 3 4 5 6 7 8 index (j)Interval length (t  j−t j−1)n=0n=2n=8(b) The inspection times can be scheduled farther apart with moreopportunities (for ci = 8).1 2 3 index (j)Interval length (t  j−t j−1)n=3n=2n=0n=1413.5. Numerical ExamplesFigure 3.3: Three outcome measures when p = prob(S < T ) varies between0 and 1 ( corresponds to the base-case scenario).(a) Optimal discounted expected total cost0 0.2 0.4 0.6 0.8 105001000150020002500300035004000Prob(failure happens before emergency in each cycle)Optimal discounted expected total cost(b) Probability of catastrophe in each cycle0 0.2 0.4 0.6 0.8 100.0020.0040.0060.0080.01Prob(failure happens before emergency in each cycle)Probability of catastrophe in each cycle(c) Expected number of inspections per-formed in each cycle0 0.2 0.4 0.6 0.8 10123456Prob(failure happens before emergency in each cycle)Expected # of inspections in each cycle423.5. Numerical Examples(i.e., prob(S < T )). For a constant value of the emergency arrival rate λ,this probability approaches 0 if β → ∞, and it approaches 1 if β → 0.In one extreme, when the component has a relatively long lifetime (i.e.,as p → 0), the discounted expected total cost of the optimal inspectionpolicy C(T ∗9 ) approaches 40. This cost only includes the discounted expectedtotal replacement cost from the infinite stream of replacements after usinga functioning component upon emergency. This is reasonable since evenwithout performing any inspections, the probability that the componentfails before the emergency is very small. Figures 3.3b and 3.3c also confirmsthis observation.On the other extreme, if the failure occurs before the emergency with aprobability close to 1 (i.e., the component has a short life), the discountedexpected total cost is the largest. Again, this cost is also mainly derived bythe cost of the replacements, as the probability of catastrophe is relativelysmall. In this case, the replacements are done after detecting the failurethrough the first inspection (note that the expected number of inspectionsperformed per cycle approaches 1 as p → 1). Since the component has ashort lifetime (close to 0), one can wait and identify the failure by perform-ing a single properly timed inspection. However, due to the component’sshort life, more frequent replacements are necessary in this case to providecoverage against the catastrophe. Consequently, as the component’s lifetimedecreases, the discounted expected total cost increases. We remark that for0.98 < p < 1, the component’s extremely short lifetime makes it no longereconomical to keep and maintain; therefore, we observe an increase in theprobability of catastrophe (Figure 3.3b) because we are willing to accept ahigher risk of incurring the penalty cost due to the high maintenance cost.Note that our base-case scenario (β = 5) results are shown by black squares.In Figure 3.3c, we observe that for mid-range values of p, for whichthe chance of failure happening before emergency is close to the chanceof emergency happening before failure, the expected number of inspectionsperformed in each cycle is at its peak. For this range of p values, sinceit is harder to predict whether the emergency will happen before or afterthe failure, it is harder to guard against a catastrophe from occurring, de-spite optimally timing the inspection intervals (note that in Figure 3.3b, theprobability of the catastrophe also has a peak for the intermediate values ofp).433.5. Numerical Examples3.5.3 Effect of changes in the cost parametersFinally, we explored the effect of changes in the cost parameters. Tothis aim, we consider the replacement cost r to be fixed, and vary ci and cp.Figure 3.4a depicts the optimal discounted expected total cost for ci = 1, 2, 5and 9. As expected, as the inspection cost increases and approach r, itis optimal to schedule smaller number of inspections before scheduling areplacement. In fact, for ci = 5 and 9, our results suggest that we replacethe component without scheduling any inspections because the inspectioncost for these cases are close to the replacement cost. In contrast, when wevary the penalty cost cp, our experiments does not reveal any specific patternon the optimal number of inspection opportunities to schedule before thereplacement (it is always optimal to schedule 9-11 inspections before thereplacement). However, we observe that for the larger penalty cost, themagnitude of decrease in the discounted expected total cost is larger for thefirst few inspections opportunities.Also, as expected, the discounted expected total cost increases as any ofthe cost parameters increase. Returning to our discussion in Section 3.5.2,the magnitude of this change depends on the value of p (i.e., probability offailure happening before emergency). As we mentioned earlier, in the twoextremes, the optimal discounted expected total cost consists of mainly theexpected total replacement cost. Therefore, the optimal discounted expectedtotal cost is the most sensitive to the replacement cost r. On the other hand,for mid-range values of p, the penalty cost has a larger contribution to thetotal cost, and therefore its changes can also affect the total cost.3.5.4 Comparison with constant interval inspection policiesIn this experiment, we compare the performance (the discounted ex-pected total cost) of the optimal inspection policy T ∗n with the best constantinterval inspection policy. The constant interval inspection policy may beeasier to compute and implement in practice. However, since this inspectionpolicy is no longer optimal, it is important to know the performance lossassociated with implementing it. First, we define an inspection policy withconstant inspection interval of length T as T˜n :={j · T}n+1j=1 , where n is thelimit on the number of available inspection opportunities as before. In otherwords, we schedule n inspections at times T, 2T, . . . , nT , and a replacementat time (n+ 1)T . For this experiment, we obtained T˜ ∗n by minimizing C(T˜n)over the single variable T using Matlab’s built-in solver.Figure 3.5a shows the discounted expected total cost C(T˜n) as a function443.5. Numerical ExamplesFigure 3.4: Optimal discounted expected total cost (DETC) for different nas ci and cp change.(a) DETC for ci = 1, 2, 5 and 9.0 5 10 15 20150200250300350400450Number of inspection opportunities (n)Optimal discounted expected total cost  ci=1ci=2ci=5ci=9(b) DETC for cp = 50, 200, 600 and 1000.0 5 10 15 2050100150200250300Number of inspection opportunities (n)Optimal discounted expected total cost  cp=1000cp=600cp=200cp=50453.5. Numerical ExamplesFigure 3.5: Comparison of constant interval inspection policies and optimalinspection policies.(a) Discounted expected total cost as a function of T for differentvalues of n0 1 2 3 4 5 6 7 8 9 100500100015002000Constant inspection interval (T)Optimal discounted expected total cost  n=1n=7n=15(b) Performance of optimal policies vs. best constant interval poli-cies0 2 4 60.0140.0160.0180.020.0220.024Expected # of inspections performed in each cycleProbability of catastrophe in each cycle  Optimal policiesConstant interval policiesn=0n=3n=2 n=10n=10463.6. Conclusionsof constant interval length T for the values of n = 1, 7 and 15. For thebaseline parameters and n = 15, the best constant interval policy is attainedfor T ∗ = 0.36 with the discounted expected total cost of 233.38, which is18.2% more than the optimal expected total cost (C(T ∗9 ) = 197.53).Figure 3.5b depicts two outcome measures: the probability of catastro-phe and the expected number of inspections performed in each cycle bothfor the optimal inspection policies (dashed line) and the constant intervalinspection policies (solid line) for the values of n = 0, 1, . . . , 10. We observethat for n = 0, both policies perform exactly the same since in this case,the constant interval property does not impose any additional constraints.However, we observe as n increases, for the same probability of catastrophe,the expected number of inspections performed is much smaller if we spacethe inspections optimally. This means that the constant interval policiescan maintain the same probability of catastrophe only at the expense of alarger expected number of inspections performed.3.6 ConclusionsThis chapter provides a new modeling framework for determining theoptimal inspection times for a reliability problem. We defined a penaltycost for the situation where the component is not ready at the time ofan emergency, and we also considered that there is a limit on the numberof inspections opportunities, after which a replacement can be scheduled.Under the assumption that the component failure satisfies a mild technicalcondition (i.e., the PF2 distribution), we showed that the optimal inspectionpolicy is unique, and we provided an algorithm for finding it. Moreover, weestablished several interesting properties of the optimal solution. We alsoprovided intuitive explanations for changes in the inspection policy due tochanges in different parameters and supported the intuition with numericalexamples. Our experiments also highlighted some counterintuitive results,which we discussed as well.There are a number of managerial insights derived from our analysisthat can be of interest to practitioners. First, one can use our model todecide when it is beneficial to pay extra to increase the inspection resourcesavailable by comparing the reduction in expected cost for each marginalinspection opportunity with the cost of obtaining it. Also, our numericalexamples suggest that more inspections are expected to be performed in sit-uations where it is harder to predict whether the emergency happens beforeor after the failure (Figure 3.3c), and when inspections are cheaper relative473.6. Conclusionsto the replacement cost (Figure 3.4a). Furthermore, we showed in Theo-rem 3 and observed in our numerical examples, in certain situations, therelative positioning of the emergency and failure distributions can result inan inspection policy where the inspection intervals could become increas-ing over time. This result sharply contrasts with the existing literature inwhich infinite inspection opportunities lead to inspection intervals that aredecreasing. Therefore, despite the intuition that a component with the IFRproperty should be inspected more frequently as time passes, this logic mayno longer hold when limited inspection opportunities are available becausewe want to schedule the limited remaining inspections over a longer periodto delay the scheduled replacement (since short replacement cycles result inincreased expected replacement cost).Our approach of considering limited number of inspection opportunitiesand allowing for a preemptive replacement is not specific to this problem,and it can be applied to many similar problems previously studied in liter-ature. Moreover, as a direction for future research, it would be interestingto study other versions of the problem, such as the case where inspectionsmay be inaccurate or the inspections/replacements may take non-negligibletime.48Chapter 4Issuing Policies for HospitalBlood Inventory4.1 IntroductionRed blood cells (RBCs), which deliver oxygen to body tissues, are themost common blood product used in transfusions. Donated RBC units areperishable and have a shelf life of 42 days in the United States and Canada.Hospitals regularly receive RBC units of different ages (measured from thetime of donation) from regional blood centers and store them locally. Later,when demand for these units arise, they are issued (allocated) accordingto an issuing policy that considers factors such as the compatibility withrecipient, the age of RBC unit issued, and the current available inventory.The efficiency of an issuing policy can be measured based on severalkey performance metrics. The first metric is the outdate rate, which isthe proportion of supplied RBC units that are discarded because they havereached the maximum allowable age of 42 days. In addition to the costsassociated with collecting, distributing, holding, and discarding these units,reducing the outdates rate is especially important when the overall supply ofblood is not sufficient to meet the demand. Another metric is the shortagerate, or the proportion of demand satisfied from another source since thehospital has no on-hand inventory. Again, dealing with shortages can becostly or difficult in urgent cases. Finally, while transfusing an RBC withinits the allowable shelf life is considered safe by the current standards, severalrecent studies suggest that the transfusion value of the RBC units deteriorateover time (Wang et al. [76]), and that transfusing older blood can increasethe risk of complications, particularly for critically ill patients (Koch et al.[33], Zallen et al. [79]). For instance, Koch et al. [33] concluded in their studythat in patients undergoing cardiac surgery, transfusion of older RBCs wasassociated with a significantly increased risk of postoperative complicationsas well as reduced survival.The current practice at hospitals is to issue RBCs in order from oldest494.1. Introductionto youngest inventory in order to minimize the number of outdates andshortages cases. In the Operations Research literature, this issuing policy,referred to as FIFO, has been shown to be the optimal issuing policies forseveral objective functions including outdate and shortage rates (Pierskallaand Roach [58]). The underlying assumption for these models is that thequality of a RBC unit remains constant throughout the 42 days lifespan.However, as we discussed above, recent findings in medicine suggest thatthe age of transfused blood can affect health outcomes, with older bloodcontributing to more complications. Given that the impact of RBC’s agecannot be ignored, FIFO is no longer the optimal issuing policy. In fact,considering the objective of minimizing the average age of transfused bloodwould imply issuing RBCs in order from youngest to oldest (i.e., a LIFOpolicy).In response to these clinical findings, there is a recent interest in the clin-ical community to design issuing policies that balance the trade-off betweenthe shortage (and/or wastage) and the average age of transfused blood. Forinstance, Atkinson et al. [7] proposed the following class of policies basedon a single age threshold: transfuse the oldest blood that is younger thanthe threshold, and if there is no blood younger than the threshold, transfusethe youngest blood that is older than the threshold. They used a simu-lation model based on data from the Stanford University Medical Centerand showed that with a threshold of 14 days they can reduce the age oftransfused blood without significantly affecting the amount of wastage orshortage. They demonstrated how changing the threshold affects the meanage of blood transfused and shortage percentage.Atkinson et al. [7] suggested a simple class of policies, which aims tofind the right balance between conflicting objectives of reducing the ageof transfused blood and shortage. However, they neither characterized anoptimal issuing policy, nor provided a framework for obtaining one. In thischapter, we analyze this problem as a perishable inventory managementproblem using an infinite-horizon dynamic programming model. We assumethat the supply and demand processes are exogenous and random. Then, theonly way to reduce shortages is to avoid outdates, meaning that an issuingpolicy that minimizes shortages also minimizes the outdates. Therefore, wedefine our objective function by considering only two costs: (1) a penaltycost associated with each RBC unit transfused, which is proportional to theage of the unit at the time of issuance, and represents the expected cost ofany complications after the transfusion. (2) a penalty for each unit shortagewhich is the cost of satisfying the demand from another source. Then, ourgoal is to minimize the total expected discounted cost by deciding which504.2. Literature Reviewunits of blood on-hand and of what age to issue to satisfy the demand ineach period. This dynamic programming formulation suffers from the curseof dimensionality due to large state and decision spaces. In order to dealwith the intractable number of states, we use methods from the approximatedynamic programming (ADP) literature. In particular, we approximate thevalue function of the dynamic programming with an affine combination ofa set of basis functions. We assign different weights to these functions bysolving a linear program. Then, we use this approximate value functionto find the approximate optimal issuing policy in each period by solving atractable integer program.The remainder of the chapter is organized as follows. In the next section,we review the relevant literature. In Section 4.3, we present our dynamicprogramming formulation of the problem. In Section 4.4, we discuss oursolution method based on the linear programming approach to ADP, andwe develop an efficient algorithm that finds an approximate optimal issuingpolicy. In Section 4.5, we present our numerical results, which are based ondata from a large hospital in British Columbia. Finally, we discuss conclud-ing remarks and future work in Section Literature ReviewOur research in this chapter is related to the literature on blood inventorymanagement, which is part of a larger stream of research on perishableinventory management. We restrict our focus to the models that are closelyrelated to our problem (i.e., issuing policies) and refer the reader to Nahmias[43], Nahmias [44], and Karaesmen et al. [28] for comprehensive reviews ofthe early and recent developments in the area of perishable inventory systems(e.g., models dealing with optimal ordering policies).The focus of the perishable inventory management literature (includingthe models that consider the management of the blood products) is more onthe ordering decisions rather than the issuing policies, which is in most casesassumed to be FIFO. The limited studies that study the optimal issuingpolicies are mostly for the situations where either FIFO or LIFO is theoptimal issuance policy. For instance, Pierskalla and Roach [58] showed thatFIFO is in fact the optimal issuing policy for the following three objectivefunctions: (1) maximizing the value of all demands satisfied, (2) minimizingthe total number of units backlogged, and (3) minimizing the total number ofoutdates. More recently, Haijema et al. [25] used a Markov Decision Processmodel and simulation to develop near-optimal order-up-to replenishment514.2. Literature Reviewpolicies for a number of issuing policies. Moreover, Deniz et al. [19] providedheuristics for finding the joint replenishment-issuing policies for a productwith two periods of lifetime.Another stream of research uses queueing theory to analyze perishableinventory systems. The general approach of these models is to analyticallydescribe different performance metrics under simple issuing policies (in mostcases, only the FIFO policy). As an example, Kaspi and Perry [29] obtainedperformance metric such as the average number of units in the system andthe distribution of time between outdates for the FIFO issuing policy (also,see Kaspi and Perry [30], Perry [57], and Parlar et al. [53] for several exten-sions to this work). In a more recent work, Abouee-Mehrizi et al. [1] usedthis approach to find the distribution of the age of transfused blood and theshortage rates for the threshold policy introduced by Atkinson et al. [7]. Us-ing queueing theory to analyze issuing policies has a major drawback, whichis the fact that it can only consider very simple issuing rules and thereforeone cannot use it to study general state-dependent issuing policies.In general, dynamic inventory management models that deal with opti-mal ordering decisions for the perishable products are known to be extremelycomplicated because the dynamic programming formulation of these prob-lems suffer from the curse of dimensionality. As a consequence, except forvery simple cases (such as the case of two-period lifetime studied by Nah-mias and Pierskalla [45]), the main focus of the literature is on developingefficient heuristic for finding near optimal ordering policies (see Nahmias[40], Fries [22], Nahmias [41], Nahmias [42], Cooper [16] as examples).4.2.1 Contribution to related literatureOur work contributes to the literature on the allocation policies of perish-able products. To our knowledge, our model is the first work that providesa dynamic (i.e., state-dependent) issuing policy whereas previous literatureconsiders only static policies such as FIFO, LIFO, or age-based thresholdpolicies as in Atkinson et al. [7] and Abouee-Mehrizi et al. [1]. While theFIFO issuing policy may be optimal for certain objective functions (seePierskalla and Roach [58]), it does not capture the trade-offs between theconflicting objectives of age and shortages. Also, as we show in this chapter,the static issuing policies such as the threshold policy proposed by Atkinsonet al. [7] is no longer optimal when we try to balance the shortage rate andthe average age of blood transfused simultaneously. We develop an efficientADP algorithm to find approximate optimal issuing policies and show thatthey can outperfom other classes of policies. Furthermore, our numerical ex-524.3. Model and Formulationperiments reveal several managerial insights regarding efficient blood issuingpolicies. In particular, the approximate optimal issuing policy found by ourADP algorithm motivates a simple, easily implementable policy, which stilloutperforms other policies.4.3 Model and FormulationWe formulate this problem as an infinite horizon, discounted MarkovDecision Process. We assign a penalty cost to each RBC unit transfused,which is proportional to the age of the unit at the time of issuance. Forinstance, this penalty cost can represent the expected cost of any compli-cations after the transfusion. Furthermore, we consider another penalty foreach unit shortage, which is the cost of satisfying the demand from anothersource. We consider a single blood type meaning that we do not considertransfusion of blood from other compatible blood types. We assume thatthe supply of blood units (and their age) and demand in each period areexogenous and uncertain, but their probability distributions are available.Then, our goal is to minimize the total expected cost by deciding whichunits of blood on-hand and of what age to issue to satisfy the demand ineach period. First we define the notation:• i ∈ {1, . . . , 42}: age of the blood.• p(i) = ic: penalty of satisfying a unit of demand with blood of age i,where c > 0 denotes the per-unit-period penalty cost.• `: penalty of satisfying one unit of demand from an outside source,when a shortage occurs. We assume ` > 42c.• Qi, D: random variables for the number of age i blood arrivals and thenumber of demand units, respectively. We assume that these randomvariables are independent and identically distributed (iid) for differentperiods. We let qi and d indicate the realized arrival of blood of age iand the realized demand.• si: total supply of age i blood before satisfying the demand. This in-cludes the leftover from the previous period as well as the new arrivals.• ui: total supply of age at most i before satisfying the demand (i.e.,ui =i∑j=1sj).534.3. Model and Formulation• xi: number of units of age i used to satisfy the demand in the currentperiod (0 ≤ xi ≤ si for each i).• λ: the discount factor.In each period the sequence of events is as follows. We observe thisperiod demand d and the current supply vector (s1, s2, . . . , s42), and decidewhich units, (x1, x2, . . . , x42, to issue in order to satisfy the demand. Anypart of the demand that is not satisfied by the units on-hand are satisfiedfrom a secondary source through a rush order. Then, the remaining units ofage 42 are discarded and the remaining blood units age one period. The newsupply of the blood of different ages (q1, q2, . . . , q42) arrives and are addedto the leftover units, resulting in a total supply inventory of (q1, q2 + s1 −x1, . . . , q42 +s41−x41) at the beginning of the next period. Finally, the nextperiod’s demand d′ is observed. Now, we define the different components ofthe MDP formulation.Decision epochs: We assume that issuing decisions are made daily, afterthe demand for that day is realized.State space: The state of the system consists of this period’s supply vec-tor and demand. In other words, we represent the state vector as S =(s1, s2, . . . , s42, d), where each si denotes the available blood units of age iand d denotes the current demand.Action space: In each decision epoch, we let integer vector X = (x1, x2, . . . , x42)represent the number of units, xi, of each age i blood to issue. Note thatif the units issued do not satisfy the whole demand, then the remaining de-mand is met from a secondary source through a rush order, but the systemincurs a shortage cost per unit. Furthermore, for each state S, the set offeasible actions must satisfy the following constraints.xi ≤ si for i = 1, . . . , 4242∑i=1xi ≤ dxi ≥ 0, integer for i = 1, . . . , 42. (4.1)The first set of constraints specify that we cannot issue units more than theavailable supply of each age, whereas the second constraint ensures that wecannot issue units more than the current demand.544.3. Model and FormulationTransition probabilities: At the end of each period, the new supply ofblood Q = (q1, . . . , q42 arrives and the next period’s demand d′ is realized.We assume that there is a finite number K of possible scenarios for therealized new supply and demand. The probability for each scenario is known,which we represent by Pr(Q, d′), and it is independent of the current stateor our action. Then, we can define the transition probabilities as follows:p(S ′|S,X ) ={Pr(Q, d′) if S ′ = (q1, q2 + s1 − x1, . . . , q42 + s41 − x41, d′);0 otherwise.(4.2)Basically, (4.2) suggest that given the starting state S and the action X ,with probability Pr(Q, d′), we will start the next period with inventoryvector (q1, q2 + s1 − x1, . . . , q42 + s41 − x41) and we must meet the demandd′. Note that the remaining units of age 42, s42 − x42, at this period arediscarded and the remaining units, si − xi for i < 42, have aged by oneperiod.Immediate cost: The immediate cost is associated with satisfying thisperiod’s demand and is a function of the current state and action. Wedefine it as follows:C(S,X ) =42∑i=1icxi + `(d−42∑i=1xi), (4.3)where the first part,42∑i=1icxi, denotes the total penalty cost associated withissuing blood from units on-hand and the second part, `(d −42∑i=1xi), corre-sponds to the cost of obtaining the shortage units from a secondary source.Optimality equation: First, we define the value function for state S asthe optimal expected discounted cost-to-go over an infinite horizon if westart the current period with state S. We denote this cost by V (S), whichshould satisfy the Bellman equations:V (S) = minX{C(S,X ) + λ∑S′p(S ′|S,X )V (S ′)}∀S. (4.4)Because of the large state and action spaces, we cannot use the traditionalmethods for solving MDPs, such as the value iteration or the policy iteration554.4. Solution Approachalgorithms. For instance, if the demand and the number of units of each agenever exceeds 100, the state space is of size 10043.4.4 Solution ApproachSince it is intractable to exactly solve the MDP formulation of Section4.3, we solve the equivalent linear programming formulation through ADP.We first define the following approximation to the value function:V (S) ∼= V˜ (S) = θ0 +42∑i=1θiui + δd+ σ[d− u42]+, (4.5)where ui :=i∑j=1sj represents the total supply available of age at most i, and[d−u42]+ = max(0, d−u42) represents the shortage given the total availablesupply of u42 and the demand d. Then, we can use ADP algorithms to findthe best set of coefficients (θ0, ..., θ42, δ, σ) such that (4.5) would be a goodapproximation for the exact value function. Note that each θi (if negative)can be viewed as the marginal savings in cost for each additional unit ofage at most i, whereas δ can be interpreted as the marginal cost for eachadditional demand unit and σ as the marginal cost for each additional unitof shortage. By defining the approximation as above, we try to capture themain factors deriving the cost, i.e., the supply of different ages, the demand,and the magnitude of a shortage if it occurs.In the remainder of Section 4.4, we discuss our approach for determiningthe best values for coefficients (θ0, ..., θ42, δ, σ) and how to use the result-ing approximation to determine the issuing policy in each period. To thisaim, we introduce several optimization problems, which we overview here.To tune the coefficients (θ0, ..., θ42, δ, σ), we solve the linear programmingmodel described in (4.6) or its dual (4.7) using column generation. In orderto generate new columns, we solve mixed integer programs of form (4.9).Finally, we solve problem (4.15) or its equivalent form (4.17) to determinethe approximate issuing policy in each period.4.4.1 Calibrating approximate value function coefficientsTo tune the coefficients (θ0, ..., θ42, δ, σ), we use the linear programmingapproach to ADP (originally proposed by Schweitzer and Seidmann [67]).We first introduce the linear program form of our original MDP by rewriting564.4. Solution Approachthe optimality equations (4.4) as follows.max∑Sα(S)V (S)subject toV (S) ≤ C(S,X ) + λ∑S′p(S ′|S,X )V (S ′) ∀S,X .In the above linear program, we have a decision variable V (S) for eachpossible state vector S. The optimal solution to the above linear program isthe same as the solution to the optimality equations of the MDP provided in(4.4) given that the objective coefficients α(S) in the above linear programare all positive. It is convenient to normalize these coefficients such that∑Sα(S) = 1 and view them as a probability distribution over the initialstate of the system (Puterman [61, p. 223]).Note that due to the large state and action spaces, this linear programalso suffers from curse of dimensionality, meaning it cannot be solved effi-ciently. To overcome the curse of dimensionality, we can replace V (S) by ourapproximation value function defined in (4.5). The resulting problem is alinear programming problem that has 45 decision variables (θ0, ..., θ42, δ, σ):max θ0 +42∑i=1Eα [ui] θi + Eα [d] δ + Eα[[d− u42]+]σ (4.6)subject to(1− λ) θ0 +42∑i=1Θi(S,X )θi + ∆(S)δ +Σ(S,X )σ ≤ C(S,X ) ∀S,XwhereEα [ui] :=∑Sα(S)ui(S) ∀iEα [d] :=∑Sα(S)d(S)Eα[[d− u42]+]:=∑Sα(S)[d(S)− u42(S)]+574.4. Solution ApproachandΘi(S,X ) := ui(S)− λ∑(Q,d′)Pr(Q, d′)u′i(S,X ,Q) ∀i∆(S) := d(S)− λ∑(Q,d′)Pr(Q, d′)d′Σ(S,X ) := [d(S)− u42(S)]+ − λ∑(Q,d′)Pr(Q, d′)[d′ − u′42(S,X ,Q)]+.Note that in (4.6), the expectations over vector α are estimated by sam-pling states (see Bertsekas and Tsitsiklis [13, p. 377] for more details). Theabove formulation reduces the number of decision variables significantly,but this problem still has a large number of constraints because we have oneconstraint for each possible state-action pair. Fortunately, for finding theoptimal solution, it suffices to find at most 45 of these constraints which arebinding at optimality (by the fundamental theorem of linear programming).Then, we can start with an initial set of 45 constraints and add new cuts(i.e., constraints) by finding the most violated constraint. We stop addingnew cuts and report the solution when the optimality gap is smaller than arequired precision. Equivalently, we can solve the dual of the above problemusing delayed column generation. The dual to problem (4.6) can be writtenas follows:min∑S,XC(S,X )W(S,X ) (4.7)subject to(1− λ)∑S,XW(S,X ) = 1∑S,XΘi(S,X )W(S,X ) = Eα [ui] ∀i∑S,X∆(S)W(S,X ) = Eα [d]∑S,XΣ(S,X )W(S,X ) = Eα[[d− u42]+]W(S,X ) ≥ 0 ∀S,X .The above problem has a dual variable for each state-action pair, butat most 45 of these variables are needed to be non-negative at optimality.584.4. Solution ApproachTherefore, we can use delayed column generation approach and add newvariables as needed. Finding an initial set of columns (variables), whichproduce a feasible solution to problem (4.7) is not straightforward. Thus,we use the Phase I method of linear programming to find this initial set.The Phase I method starts with columns of an identity matrix of size 45,meaning that we add a non-negative slack variable to each constraint of thedual problem. Then, we try to minimize the sum of these slack variablesby generating and adding columns from the original dual problem. If thePhase I objective function becomes zero, then we can remove the columnsof the identity matrix and the remaining columns provide a feasible solutionto the dual problem. We do not explain how we choose the columns thatare added to the Phase I problem because it is similar to our approach foradding constraints to the primal problem, which we explain next.Finally, having this initial set of columns for problem (4.7), we solvethe relaxed dual problem (which we call the master problem) and find itsoptimal solution as well as the corresponding optimal solution to the relaxedprimal problem (4.6) (i.e., (θ∗0, ..., θ∗42, δ∗, σ∗)). Since we did not consider allthe constraints from the original problem, this solution may not satisfy allthe constraints to the primal problem. We find the most violated constraintby solving a pricing sub-problem that finds a feasible state-action pair (S,X )that maximizesV˜ (S)− λ∑S′p(S ′|S,X )V˜ (S ′)− C(S,X ). (4.8)Recall that the primal constraints for problem (4.6) are of the formV˜ (S) ≤ C(S,X ) + λ∑S′p(S ′|S,X )V˜ (S ′) ∀S,X .If the maximum of (4.8) is greater than 0 for the optimal state-actionpair (S∗,X ∗), it means that the constraint corresponding to this state-actionpair is the most violated constraint. On other hand, if the maximum isnot positive, then the current solution (θ∗0, ..., θ∗42, δ∗, σ∗) satisfies all theconstraints from the original primal problem.Given (θ∗0, ..., θ∗42, δ∗, σ∗), we can represent the pricing sub-problem asthe follows:max (1− λ) θ∗0 +42∑i=1θ∗i Θi(S,X ) + δ∗∆(S) + σ∗Σ(S,X )− C(S,X ) (4.9)594.4. Solution ApproachwhereΘi(S,X ) :=i∑j=1sj − λ∑(Q,d′)Pr(Q, d′)i∑j=1qj +i−1∑j=1(sj − xj) ∀i∆(S) := d− λ∑(Q,d′)Pr(Q, d′)d′Σ(S,X ) :=d−42∑j=1sj+− λ∑(Q,d′)Pr(Q, d′)[d′ − u′42]+u′42 :=42∑j=1qj +41∑j=1(sj − xj).In the sub-problem (4.9), the decision variables are the state (s1, . . . , s42, d)and the action (x1, . . . , x42). Therefore, to ensure their feasibility (meaningthat the action vector does not issue blood units more than what is avail-able according to the state vector), we consider only state-action pairs thatsatisfy the following set of linear constraints:xi ≤ si ∀i42∑i=1xi ≤ dxi, si ≥ 0, integer ∀id ≥ 0, integer .Note that Θi(S,X ), ∆(S), and all the constraints are linear in the deci-sion variables. However, Σ(S,X ) is not a linear function of the decision vari-ables because it contains piecewise linear functions of the decision variables.We convert this function into a linear function by defining integer variablesk+0 , k−0 , k+(Q, d′) and k−(Q, d′), and binary variables b0 and b(Q, d′):Σ(S,X ) = k+0 − λ∑(Q,d′)Pr(Q, d′)k+(Q, d′),where k+0 satisfies the following set of linear constraints (letting N be a large604.4. Solution Approachpositive integer):k+0 + k−0 −N = d−42∑j=1sj (4.10)k+0 ≤ Nb0 (4.11)k−0 ≥ Nb0 (4.12)k−0 ≤ N (4.13)k+0 , k−0 ≥ 0, integer and b0 ∈ {0, 1}.Note that if d−42∑j=1sj > 0 (i.e., we face shortage), then the first constraint(4.10) together with (4.13) imply that k+0 > 0. Then, it follows from (4.11)that b0 = 1. Then, we have k−0 = N from (4.12) and (4.13). Consequently,k+0 denotes the shortage because k+0 = d −42∑j=1sj by (4.10). On the otherhand, if d−42∑j=1sj ≤ 0, then the above set of constraints ensure that k+0 = 0.Similarly, for each (Q, d′), k+(Q, d′) must satisfy the following:k+(Q, d′) + k−(Q, d′)−N = d′ −42∑j=1qj +41∑j=1(sj − xj) (4.14)k+(Q, d′) ≤ Nb(Q, d′)k−(Q, d′) ≥ Nb(Q, d′)k−(Q, d′) ≤ Nk+(Q, d′), k−(Q, d′) ≥ 0, integer and b(Q, d′) ∈ {0, 1}.Consequently, sub-problem (4.9) becomes an integer program, which inour case can be solved quickly. After solving the above integer program, theoptimal values of the decision variables (s∗1, . . . , s∗42, d∗) and (x∗1, . . . , x∗42)provides us with the state-action pair that corresponds to the most violatedconstraint for the current solution to the master problem. We add thisconstraint to the master problem and resolve it to find a new solution.Then, we use the new solution to find another violated constraint. We stopadding more cuts when the termination criteria is met (i.e., when no moreconstraints are violated or when the optimality gap for the master problemis within the required range).614.4. Solution Approach4.4.2 ADP-based issuance policyNow, we explain how we can use the above approximation to determinean approximate optimal issuing policy in each period. Since it is impracticalto store the approximate optimal issuing policy for each possible state, weuse our approximate value function to find the approximate optimal issuingpolicy as needed for each state realized in practice.In each period, given the state vector S, we solve the following problemto find an approximate optimal issuing policy:minX{C(S,X ) + λ∑S′p(S ′|S,X )V˜ (S ′)}, (4.15)where given the initial state S, our action X , the new arrival vector Q, andthe new demand d′, we haveV˜ (S ′) = θ0 +42∑i=1θiu′i + δd′ + σ[d′ − u′42]+. (4.16)Note that in (4.16), each u′i =i∑j=1qj +i−1∑j=1(sj − xj) is the total inventory ofage at most i in the next period given the initial state S, our action X , andthe new arrival vector Q. This quantity is equal to the sum of new bloodunits arrived of age at most i, and the remaining aged units of age at mosti after satisfying this period’s demand.A feasible issuing policy must satisfy the constraints in (4.1). Then, wecan write the minimization problem (4.15) as follows using (4.3) to replacethe immediate cost C(S,X ):min42∑i=1icxi + `(d−42∑i=1xi) + λ∑(Q,d′)Pr(Q, d′)V˜ (S ′) (4.17)subject toxi ≤ si for i = 1, . . . , 4242∑i=1xi ≤ dxi ≥ 0, integer for i = 1, . . . , 42Note that the constraints of the above problem are all linear in the decisionvariables xi. However, the objective function has a nonlinear part (i.e.,624.5. Numerical Experiments[d′ − u′42]+). We can use an approach similar to (4.14) to convert the aboveproblem to an integer program. We solve this integer program in eachperiod to find the approximate optimal issuing policy. In Section 4.5, wewill evaluate the performance of the ADP-based policy and provide severalinsights based on our numerical experiments. Furthermore, we comparethe performance of our policy with other classes of policies proposed in theliterature.4.5 Numerical ExperimentsIn this section, we use our solution approach discussed in Section 4.4 tofind approximate optimal issuing policies for the case of a large hospital inBritish Columbia. We use historical data for this hospital to calibrate differ-ent parameters of our model. Then, using a simulation model, we evaluatethe performance of our policy and provide several managerial insights onthe properties of good issuing policies that balance the trade-offs betweenthe age of blood transfused and the shortage rate. Furthermore, we showhow our policy compares to issuing policies currently used in practice aswell as previously proposed policies in the literature. Finally, using insightsfrom our ADP-based issuing policy, we propose a simple static issuing policythat performs nearly as good as the ADP-based policy, but is easier to beimplemented in practice. The simulation model was implemented in MatlabR2013a while the column generation algorithm and the integer programmingmodels were implemented in AMPL with CPLEX 12.2 as the solver.4.5.1 Simulation of the hospital blood bankIn order to evaluate the performance of different blood issuing policies,we developed a simulation model that mimics the dynamics of a hospitalblood bank (the blood bank is a division of a hospital where the receivedRBC units are stored before being issued for transfusion). Our simulationmodel consists of four steps which we discuss next.1. Demand realization: In each period, we randomly generate thedaily demand according to an empirical distribution obtained from historicaldata for our hospital. In particular, we used the data on daily demand fora period of one year from April 1, 2010 to March 31, 2011. The demandand supply information for different blood types is not specified in our data.Therefore, we consider only a single blood type for this study.2. Supply realization: We also generate the number of blood unitsarriving at the hospital each day, by age, using the empirical distribution634.5. Numerical Experimentsbased on historical data. In practice, the hospital receives blood from twodifferent sources. The main source of blood supply is by ordering directlyfrom Canadian Blood Services (CBS). In addition to receiving blood fromCBS, the hospital receives blood units from smaller hospitals. These smallerhospitals send their blood units to the larger hospital when these units arewithin 10 days from expiration. The reason for this inter-hospital redistri-bution program is to reduce the wastage of blood since these units are morelikely to be transfused at the larger hospital which faces a higher demandrate.3. Issuing policy: The new blood arrived is added to our currentinventory. Then, the simulation model passes the demand and total supplyvector to the issuing policy module. For a given issuing policy, this moduledetermines which units should be allocated to satisfy the demand and if thesystem faces a shortage. For instance, if the current issuing policy is simplyFIFO, then the issuing policy allocates the oldest units on hand to satisfythe demand. On the other hand, if we want to test our ADP-based issuingpolicy, the simulation program calls our optimization model to determinewhich blood units should be issued to satisfy the demand.4. Updating metrics: Finally, knowing the units issued on each day,we update our performance metrics. The simulation program gathers infor-mation regarding the shortage, wastage, and age of blood transfused as ourmain performance metrics. In calculating the average age of blood trans-fused, we do not consider the age of blood units received in case of a shortage.In this step, we also update the inventory of blood at the start of the fol-lowing period. In other words, the blood units of age 42 are discarded andthe remaining units age by 1 day.4.5.2 Results and insightsIn this section, we use our simulation program to evaluate the perfor-mance of the ADP-based issuing policy and compare it against other classesof policies. Moreover, we discuss several important insights regarding goodissuing policies gleaned from our numerical experiments. Finally, we explorethe sensitivity of our results with respect to changes in the blood supply anddemand rates.The performance metrics reported for each issuing policy are based on100 simulation repetitions, where each repetition consists of simulating 1000days of a hospital blood bank. We consider the first 700 days as the warm-up period and calculate all metrics using the information for the last 300days.644.5. Numerical ExperimentsFor our baseline scenario, we set the per-unit-period penalty cost c = 10and the shortage cost ` = 1000. The values for the cost parameters arechosen arbitrarily and do not represent actual medical costs. In practice,the relationship between the age of blood transfused and the correspondingcost of complications is not well understood. In the absence of such data,we decided to find the approximate optimal issuing policies for differentvalues of the cost parameters and depict the performance of these policiesin the form of a trade-off curve of two conflicting objectives (the averageage of blood transfused and the shortage rate). Then, policy makers canuse this curve and choose the issuing policy that they believe balances theseobjectives in the best way.Comparison of ADP-based and age-based threshold policiesThe results of our first set of experiments are depicted in Figure 4.1. Inthis figure, each point represents a blood issuing policy. The dashed linecorresponds to the threshold policies proposed by Atkinson et al. [7] andthe solid line corresponds to our ADP-based issuing policies. The verticalaxis denotes the average age of blood transfused, whereas the horizontal axisdenotes the other performance metric of interest, the shortage rate.The threshold policy of Atkinson et al. [7] issues blood unit based onthe following rule: on each day, issue the oldest blood that is the same ageor younger than the threshold, and if there is no blood younger than thethreshold then issue the youngest blood that is older than the threshold.The different points on the dashed-line are associated with different choicesof the threshold, where the upper-left point corresponds to the thresholdof 42 days (which is equivalent to FIFO policy) and the lower-right pointcorresponds to the threshold of 1 day (i.e., LIFO issuing policy).For the ADP-based policies on the solid line, different issuing policies areobtained by varying the cost ratio `/c (in fact, we fix c = 10 and change `).The lower-right point corresponds to the ADP-based issuing policy obtainedfor the case of ` = 420, meaning that the shortage cost is the same as thepenalty cost for issuing a blood unit of age 42. In this case, the issuing policyperforms very similar to the LIFO policy because there is no incentive toavoid a shortage scenario by issuing the units which are going to expiresoon. In contrast, as we increase the shortage cost to the other extreme(` = 10, 000, upper-left point of the solid curve), the corresponding issuingpolicy resembles a FIFO issuing policy because it tries to avoid any shortagescenarios which are very costly.When the shortage cost has a moderate value, the ADP-based issuing654.5. Numerical ExperimentsFigure 4.1: Comparison of ADP-based policies and age-based threshold poli-cies.0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.12022242628303234Fraction of transfused blood that is importedMean age of transfused blood(days)  Age−based threshold policiesADP−based policypolicy outperforms the threshold policies. For instance, for our baselinescenario (` = 1000), the average age of blood transfused for the ADP-basedissuing policy is 25.10 and the shortage proportion is 0.037. If we issue theblood according to a threshold policy that has the same value of average ageof blood transfused, then we face a 30% increase in the shortage proportion.Furthermore, for the shortage proportion of 0.052, the ADP-based policyresults in 8% lower average age of blood transfused (23.13 vs. 25.10).Our ADP-based policy is state-dependent, meaning that it considers thecurrent state of the system in deciding which units to issue in each period.For instance, if the current on-hand inventory suggests that a shortage mightoccur soon, then the ADP-based policy would suggest issuing blood accord-ing to the FIFO policy, whereas it might suggest issuing fresher blood if wehave excess supply. In contrast, the threshold policy is static and always usethe same threshold regardless of the current state of the system. Atkinsonet al. [7] showed that using their threshold policy with a carefully chosen664.5. Numerical Experimentsthreshold, one can reasonably decrease the average age of blood transfusedwith only a moderate increase in the shortage rate. Our results suggest thatwe can achieve the same average age of blood transfused with an even lowerincrease in the shortage rate if the issuing policy adapts to current state ofthe system.Our results provide stronger evidence for policy makers that they candecrease the average age of blood transfused without jeopardizing the avail-ability of the blood supply. Moreover, we showed that the state-dependentissuing policies perform better than the static policies such as FIFO, LIFOor the threshold policy. Our ADP-based policy smartly issues fresher bloodwhen the likelihood of facing a shortage is low, and avoids outdates by is-suing older blood units if the current on-hand inventory suggests possibilityof a shortage scenario.Sensitivity to supply-demand ratioOur second set of numerical experiments explore the sensitivity of ourresults under different supply-demand regimes. To this aim, in addition toour base-line scenario where the annual total supply matches the annual totaldemand (i.e., supply-demand ration of 1), we consider two more scenarioswhere the supply-demand ratio is equal to 1.10 in one and 0.96 in the other.The results of these experiments are summarized in Figure 4.2.First, we observe that in the case where the overall supply is smallerthan the overall demand (i.e., S/D = 0.96), the difference in terms of theaverage age of blood transfused between the FIFO and LIFO issuing policiesis not significant. This happens because the hospital does not have muchchoice in the way it issues the blood units due to the scarcity of the supply.In other words, for most days, the hospital should use all the blood on hand.Consequently, we see that the units do not stay in the inventory for longperiods and even under the FIFO policy, the average age of blood transfusedis 30 days. For the same reason, we cannot gain much improvement byissuing blood according to our ADP-based policy.In contrast, when the overall supply is more than the demand (i.e.,S/D = 1.10), the choice of the issuing policy is very important. In sucha system, the hospital inevitably faces outdates, but having these outdatesdo not necessarily results in having shortages because of the excess supply.Consequently, we can issue fresher blood and still keep the shortage propor-tion very low. We observe that for the same shortage rate, the ADP-basedpolicy achieves a significantly smaller average age of blood transfused. Aswe mentioned earlier, this is due to the fact that ADP-based policy only674.5. Numerical ExperimentsFigure 4.2: Comparison of ADP-based policies (solid lines) and age-basedthreshold policies (dashed lines) for different supply-demand ratios.0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11202530354045Fraction of transfused blood that is importedMean age of transfused blood(days)  S/D=1.1S/D=1S/D=0.96issues older units if the current inventory suggests a considerable chance ofa shortage in the near future. In summary, our results suggest that usingADP-based policies is more beneficial when there is more flexibility in howwe can issue blood to satisfy the demand.Simple threshold policy inspired by ADP-based policyIn practice, using the ADP-based policy requires solving the problempresented in (4.15) in each period to determine which blood units should beissued to meet the demand. Aside from requiring software and an interfaceto do this, the solution might not have nice structure. This may causeconcern among users and may limit the uptake of our results. Therefore,we studied the form of our ADP-based issuing policies to see if they mightbe translated into a simpler class of policies, analogous to the age-basedthreshold policies proposed by Atkinson et al. [7].Our experiments based on the ADP-based issuing policies revealed sev-684.5. Numerical Experimentseral interesting observations. First, we observed that in cases where theremaining inventory at the end of the period is relatively low and a shortagesituation in the next period is more likely, the ADP-based policy issues bloodaccording to the FIFO rule. Second, the solution of the ADP often has mul-tiple optimal solutions, including the issuance of blood in consecutive orderof age. Using these observations, we proposed the following quantity-basedthreshold policy: for a fixed threshold κ, issue blood in consecutive orderstarting from units older than the freshest κ units. If the blood older thanthe first κ units is not sufficient to meet the demand, then issue blood fromthe κth oldest unit and younger (i.e., FIFO issuing policy).Similar to the ADP-based policy, the threshold policy proposed abovealso issues blood in consecutive order of age and on a FIFO basis when thecurrent inventory is low (i.e., when the blood older than the first κ units isnot sufficient to meet the demand). However, this threshold policy is staticbecause a fixed threshold κ is used regardless of the current state of theinventory. In contrast to the threshold policies proposed in Atkinson et al.[7], the threshold in our policy is defined for the quantity of blood units,and not the age of blood.We investigated the performance of our quantity-based threshold policyusing the simulation program by trying different values for the thresholdκ. The results of our experiments are presented in Figure 4.3 for valuesof κ = 50, 100, . . . , 500. We observe in Figure 4.3 that our quantity-basedthreshold policy outperforms the age-based threshold policy and performsnearly as good as ADP-based policy.The quantity-based threshold policy performs better because it explic-itly considers the total remaining inventory at the end of period in makingissuing decisions whereas the age-based threshold policy ignores any infor-mation regarding the quantity of blood units of different ages. Furthermore,the age-based policy let the blood of age 42 days expire and only issues theseunits if there are no fresher blood units available. However, if the currentoverall inventory suggests that a shortage is likely in future, the quantity-based threshold policy issues the oldest blood and keeps the fresher bloodfor future use.The quantity-based policy is easier to characterize and implement inpractice compared to the ADP-based policy. By choosing the right value fora single parameter κ, one can achieve the right balance between the age ofblood transfused and the shortage rate. As discussed above, the resultingpolicy also performs very close to the more complicated ADP-based policy.694.6. ConclusionsFigure 4.3: Performance of quantity-based threshold policies for values ofκ = 50, 100, . . . , 500.0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.12022242628303234Fraction of transfused blood that is importedMean age of transfused blood(days)  Age−based threshold policiesADP−based policyQuantity−based threshold policies4.6 ConclusionsIn this chapter, we studied the problem of issuing blood units in a hospi-tal for transfusion when in addition to reducing shortages and outdates, thepolicy maker wants to decrease the average age of blood transfused. Theoptimal issuing policy in this case is not trivial and the dynamic program-ming formulation of this problem suffers from the curse of dimensionality.We overcome this difficulty by using ADP techniques. In particular, wedefine a set of basis functions to approximate the value function of the dy-namic programming and solve the linear programming form of the dynamicprogramming using a column generation algorithm.Our numerical results suggests that our ADP-based issuing policy (whichis state-dependent) outperforms other classes of policies previously suggestedin the literature. The ADP-based policy performs better than the thresholdpolicy because it considers the on-hand inventory vector in making issuing704.6. Conclusionsdecisions and adapts itself to the current state of the system, whereas thethreshold policy is static and always use the same issuing rule based on afixed pre-chosen threshold. Our results are especially of interest to policy-makers as it shows the average age of blood transfused can be significantlyreduced at the expense of a reasonable increase in the shortage rate. Finally,we showed that there is more value in using state-dependent policies whenthe supply is greater than the demand.Our work in this chapter also opens up several interesting directions forfurther research. The first natural extension to this work is consideringdifferent blood types and the possibility of issuing compatible but noniden-tical blood units to satisfy the demand. Another important extension tothis work is finding the optimal ordering policies assuming that the hos-pital issues blood according to the ADP-based issuing policy proposed inthis chapter. More interestingly, one can jointly optimize the ordering andissuing policies. Finally, the blood supplier (e.g., Canadian Blood Services)also allocates blood from their inventory to satisfy the demand of differenthospitals. Considering the fact that the average age of blood transfused isimportant, one might consider developing a model for finding the optimalallocation of blood of different ages to different hospitals.71Chapter 5Conclusion, Extensions andFurther ApplicationThe research in this dissertation focused on three different decision mak-ing problems with applications of the stochastic optimization models inhealth care as a central theme. In this section, we provide a review of theseproblems, our solution approaches, and the main results. Furthermore, foreach problem, we discuss possible extensions and avenues for further re-search.First, in Chapter 2, we provided a novel framework for finding goodscreening policies for patients on the kidney transplant waiting list. We de-veloped an analytical model for the single-patient case, and proved severalproperties of the optimal screening policy. Then, we used these propertiesand developed an efficient binary search algorithm to obtain the optimalpolicy. Finally, we incorporated our solution for the single-patient screeningproblem into a discrete event simulation model that heuristically (and dy-namically) updates the screening policy for each patient on the waiting list.We also performed several numerical experiments using real data and madeseveral important observations regarding good screening policies.Analytically, we were able to show that the screening intervals should bedecreasing under reasonable assumptions. This property contrasts sharplywith the current practice of screening patients over fixed intervals wherethe interval only depends on the patients’ risk for developing cardiovasculardisease. Our numerical results suggested that screening guidelines shouldconsider patients’ remaining waiting time (or their rank on the waiting list)as a main factor in designing screening guidelines.In practice, our results can help policy makers in designing better screen-ing guidelines. In particular, as we showed, considering factors that affectthe waiting time of patients in developing screening guideline could not onlysave money, but significantly reduce the likelihood of offering a kidney to apatient with unknown cardiovascular disease.Since our analytical framework does not consider all the complexities ofthe real problem, we suggested heuristic methods to include several issues72Chapter 5. Conclusion, Extensions and Further Applicationfaced in practice. Alternatively, one can use other approximation methodssuch as approximate dynamic programming (ADP) to model and solve thisproblem. The main component of an ADP model is a set of basis functionsfor approximating the value function, for which, the insights and resultsfrom our work can be found useful.In Chapter 3, we extended our previous results and developed a modelto find the right timing for the inspections and replacements of a componentthat fails silently and is needed at a random future time. We developed analgorithm to obtain the optimal inspection policy that consists of schedulinga finite number of inspections as well as an age-based preventive replacementscheduled after the last inspection.As directions for future research, one might consider the case wherethe inspections are not error-free. Furthermore, it is interesting to studythe case where inspections and replacements take non-negligible time toperform. Finally, one might consider extending our results to the case wherethe back-up component replaces a main unit and the inspection/replacementdecisions of both components need to be considered.Finally, in Chapter 4 we examined the problem of finding the optimal is-suing policy for the blood units in a hospital. Our modeling framework triesto balance the existing trade-off between minimizing shortages and mini-mizing the average age of blood transfused. We used approximate dynamicprogramming methods to design an algorithm that finds state-dependentapproximate optimal issuing policies and showed that efficiencies can beachieved by using our ADP-based issuing policies compared to simpler staticpolicies currently being used in practice or previously proposed in the liter-ature.Our results are useful for policy makers by providing evidence that theage of transfused blood can be reduced without a significant increase in therate of shortages. Furthermore, we introduce simple to use issuing policiesthat only use the oldest blood when a shortage scenario in the near futureis very likely. Using these policies, better health outcomes can be achievedwhile the current standards of efficiency are also met.Our work in Chapter 4 can be extended in several ways. We consideredonly a single blood type in our analysis. However, in practice compati-ble (but nonidentical) blood units can be issued to satisfy the demand. Itwould be interesting to extend our results to the case where we managethe inventory of all the different blood types. Another important problemthat hospital blood banks face is determining how many units of blood toorder in each period. It is obvious that the ordering decision can affect theissuing policy and vice versa. Thus, one might consider optimizing both73Chapter 5. Conclusion, Extensions and Further Applicationdecision simultaneously. We believe that our work provides the first steptowards this goal and insights from our results might prove valuable whenwe consider this more complicated problem. Finally, at the system level, itis interesting to study the problem of how the supplier should allocate theblood units to different hospitals, given the new issuing policies suggestedin this dissertation.74Bibliography[1] H. Abouee-Mehrizi, O. Baron, O. Berman, and V. Sarhangian. Alloca-tion policies in blood transfusion. Working paper, 2013.[2] M. Ahrens. Smoke alarms in u.s. home fires. Technical report, NationalFire Protection Association, Fire Analysis and Research Division, Sep2011.[3] O. Alagoz, L. M. Maillart, A. J. Schaefer, and M. S. Roberts. The opti-mal timing of living-donor liver transplantation. Management Science,50(10):1420–1430, 2004.[4] O. Alagoz, L. M. Maillart, A. J. Schaefer, and M. S. Roberts. Choosingamong living-donor and cadaveric livers. Management Science, 53(11):1702–1715, 2007.[5] O. Alagoz, L. M. Maillart, A. J. Schaefer, and M. S. Roberts. Deter-mining the acceptance of cadaveric livers using an implicit model of thewaiting list. Operations Research, 55(1):24–36, 2007.[6] K. M. Anderson, P. M. Odell, P. W.F. Wilson, and W. B. Kannel.Cardiovascular disease risk profiles. American Heart Journal, 121(1,Part 2):293 – 298, 1991.[7] M. P. Atkinson, M. J. Fontaine, L. T. Goodnough, and L. M. Wein. Anovel allocation strategy for blood transfusions: investigating the trade-off between the age and availability of transfused blood. Transfusion,52(1):108–117, 2012.[8] T. Aven and B. Bergman. Optimal replacement times: A general set-up. Journal of Applied Probability, 23(2):432 – 442, 1986.[9] T. Ayer, O. Alagoz, and N. K. Stout. A POMDP approach to personal-ize mammography screening decisions. Operations Research, 2012. (toappear).75Bibliography[10] R. E. Barlow and F. Proschan. Mathematical Theory of Reliability.Wiley, New York, 1965.[11] R. E. Barlow, L. C. Hunter, and F. Proschan. Optimum checking pro-cedures. J. Soc. Indust. Appl. Math., 11(4):1078–1095, 1963.[12] B.C. Transplant Stats, 2011. URL accessed Dec 25, 2011.[13] D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming.Athena Scientific, 1996.[14] D. Bertsimas, V. F. Farias, and N. Trichakis. On the efficiency-fairnesstrade-off. Management Science, 2012.[15] A. Chelbi and D. Ait-Kadi. Inspection strategies for randomly fail-ing systems. In M. Ben-Daya, S. O. Duffuaa, A. Raouf, J. Knezevic,and D. Ait-Kadi, editors, Handbook of Maintenance Management andEngineering. Springer London, 2009.[16] W. L. Cooper. Pathwise properties and performance bounds for a per-ishable inventory system. Operations Research, 49(3):455–466, 2001.[17] G. M. Danovitch, S. Hariharan, J. D. Pirsch, D. Rush, D. Roth,E. Ramos, R. C. Starling, C. Cangro, and M. R. Weir. Management ofthe waiting list for cadaveric kidney transplants: Report of a survey andrecommendations by the clinical practice guidelines committee of theamerican society of transplantation. Journal of the American Societyof Nephrology, 13:528–535, 2002.[18] G. M. Danovitch, S. Hariharan, J. D. Pirsch, D. Rush, D. Roth,E. Ramos, R. C. Starling, C. Cangro, and M. R. Weir. Management ofthe waiting list for cadaveric kidney transplants: Report of a survey andrecommendations by the clinical practice guidelines committee of theamerican society of transplantation. Journal of the American Societyof Nephrology, 13:528–535, 2002.[19] B. Deniz, I. Karaesmen, and A. Scheller-Wolf. Managing perish-ables with substitution: inventory issuance and replenishment heuris-tics. Manufacturing & Service Operations Management, 12(2):319–329,2010.76Bibliography[20] L. Dieulle, C. Brenguer, A. Grall, and M. Roussignol. Sequentialcondition-based maintenance scheduling for a deteriorating system. Eu-ropean Journal of Operational Research, 150(2):451 – 461, 2003.[21] R. N. Foley, P. S. Parfrey, and M. J. Sarnak. Clinical epidemiology ofcardiovascular disease in chronic renal disease. American Journal ofKidney Diseases, 32(5, Supplement 3):S112 – S119, 1998.[22] B. E. Fries. Optimal ordering policy for a perishable commodity withfixed lifetime. Operations Research, 23(1):46–61, 1975.[23] R. S. Gaston, G. M. Danovitch, P. L. Adams, J. J. Wynn, R. M. Merion,M. H. Deierhoi, R. A. Metzger, J. M. Cecka, W. E. Harmon, A. B. Le-ichtman, A. Spital, E. Blumberg, C. A. Herzog, R. A. Wolfe, D. B.Tyan, J. Roberts, R. Rohrer, F. K. Port, and F. L. Delmonico. The re-port of a national conference on the wait list for kidney transplantation.American Journal of Transplantation, 3(7):775–785, 2003.[24] J. S. Gill, I. Ma, D. Landsberg, N. Johnson, and A. Levin. Cardiovas-cular events and investigation in patients who are awaiting cadaverickidney transplantation. Journal of the American Society of Nephrology,16(3):808–816, 2005.[25] R. Haijema, J. van der Wal, and N. M. van Dijk. Blood platelet pro-duction: Optimization by dynamic programming and simulation. Com-puters & Operations Research, 34(3):760–779, 2007.[26] A. Humar, S. R. Kerr, T. Ramcharan, K. J. Gillingham, and A. J.Matas. Peri-operative cardiac morbidity in kidney transplant recipients:incidence and risk factors. Clinical Transplantation, 15(3):154 – 158,2001.[27] A. K. S. Jardine and J. A. Buzacott. Equipment reliability and main-tenance. European Journal of Operational Research, 19(3):285 – 296,1985.[28] I. Z. Karaesmen, A. Scheller-Wolf, and B. Deniz. Managing perish-able and aging inventories: review and future research directions. InPlanning production and inventories in the extended enterprise, pages393–436. Springer, 2011.[29] H. Kaspi and D. Perry. Inventory systems of perishable commodities.Advances in Applied Probability, pages 674–685, 1983.77Bibliography[30] H. Kaspi and D. Perry. Inventory systems for perishable commoditieswith renewal input and poisson output. Advances in Applied Probability,pages 402–421, 1984.[31] Y. H. Kim and L. C. Thomas. Repair strategies in an uncertain envi-ronment: Markov decision process approach. The Journal of the Oper-ational Research Society, 57(8):957–964, 2006.[32] R. L. A. Kirch and M. Klein. Surveillance schedules for medical exam-inations. Management Science, 20(10):1403–1409, 1974.[33] C. G. Koch, L. Li, D. I. Sessler, P. Figueroa, G. A. Hoeltge, T. Mihal-jevic, and E. H. Blackstone. Duration of red-cell storage and complica-tions after cardiac surgery. New England Journal of Medicine, 358(12):1229–1239, 2008.[34] H. Luss and Z. Kander. Inspection policies when duration of checkingsis non-negligible. Operational Research Quarterly, 25(2):299–309, 1974.[35] L. M. Maillart, J. S. Ivy, S. Ransom, and K. Diehl. Assessing dynamicbreast cancer screening policies. Operations research, 56(6):1411–1427,2008.[36] L.M. Maillart and S.M. Pollock. Cost-optimal condition-monitoringfor predictive maintenance of 2-phase systems. IEEE Transactions onReliability, 51(3):322–330, 2002.[37] J. J. McCall. Maintenance policies for stochastically failing equipment:A survey. Management Science, 11(5):493–524, 1965.[38] P. A. McCullough. Coronary artery disease. Clinical Journal of theAmerican Society of Nephrology, 2(3):611 – 616, 2007.[39] A. G. Munford and A. K. Shahani. A nearly optimal inspection policy.Operational Research Quarterly (1970-1977), 23(3):pp. 373–379, 1972.[40] S. Nahmias. Optimal ordering policies for perishable inventory–ii. Op-erations Research, 23(4):735–749, 1975.[41] S. Nahmias. Myopic approximations for the perishable inventory prob-lem. Management Science, 22(9):1002–1008, 1976.[42] S. Nahmias. Higher-order approximations for the perishable-inventoryproblem. Operations Research, 25(4):630–640, 1977.78Bibliography[43] S. Nahmias. Perishable inventory theory: A review. Operations Re-search, 30(4):680–708, 1982.[44] S. Nahmias. Perishable Inventory Systems, volume 160. Springer, 2011.[45] S. Nahmias and W. P. Pierskalla. Optimal ordering policies for a prod-uct that perishes in two periods subject to stochastic demand. NavalResearch Logistics Quarterly, 20(2):207–229, 1973.[46] T. Nakagawa. Optimum inspection policies for a standby unit. Journalof the Operations Research Society of Japan, 23:13–26, 1980.[47] T. Nakagawa. Maintenance and optimum policy. In Hoang Pham,editor, Handbook of Reliability Engineering. Springer, London, 2003.[48] National Kidney Foundation. K/doqi clinical practice guidelines forcardiovascular disease in dialysis patients. American Journal of KidneyDiseases, 45(4):S1–S153, 2005.[49] P. M. Odell, K. M. Anderson, and W. B. Kannel. New models forpredicting cardiovascular events. Journal of Clinical Epidemiology, 47(6):583 – 592, 1994.[50] A. O. Ojo, J. A. Hanson, R. A. Wolfe, A. B. Leichtman, L. Y. Agodoa,and F. K. Port. Long–term survival in renal transplant recipients withgraft function. Kidney International, 57:307–313, 2000.[51] OPTN. Organ procurement and transplantation network (OPTN) na-tional data report: kidney kaplan-meir median waiting times for regis-trations listed 1999–2004, 2011. URL accessed Dec 25, 2011.[52] P. S. Parfrey and R. N. Foley. The clinical epidemiology of cardiacdisease in chronic renal failure. Journal of the American Society ofNephrology, 10(7):1606–1615, 1999.[53] M. Parlar, D. Perry, and W. Stadje. Fifo versus lifo issuing policies forstochastic perishable inventory systems. Methodology and Computingin Applied Probability, 13(2):405–417, 2011.[54] G. Parmigiani. Inspection times for stand-by units. Journal of AppliedProbability, 31(4):1015–1025, 1994.[55] G. Parmigiani. Optimal scheduling of fallible inspections. OperationsResearch, 44(2):360–367, 1996.79Bibliography[56] R. E. Patterson, R.t L. Eisner, and S. F. Horowitz. Comparison ofcost-effectiveness and utility of exercise ECG, single photon emissioncomputed tomography, positron emission tomography, and coronaryangiography for diagnosis of coronary artery disease. Circulation, 91(1):54–65, 1995.[57] D. Perry. Analysis of a sampling control scheme for a perishable inven-tory system. Operations Research, 47(6):966–973, 1999.[58] W. P. Pierskalla and C. D. Roach. Optimal issuing policies for perish-able inventory. Management Science, 18(11):603 – 614, 1972.[59] W. P. Pierskalla and J. A. Voelker. A survey of maintenance models:The control and surveillance of deteriorating systems. Naval ResearchLogistics Quarterly, 23(3):353–388, 1976.[60] F. K. Port, R. A. Wolfe, E. A. Mauger, D. P. Berling, and K. Jiang.Comparison of survival probabilities for dialysis patients vs cadavericrenal transplant recipients. JAMA: The Journal of the American Med-ical Association, 270(11):1339–1343, 1993.[61] M. Puterman. Markov decision processes: discrete stochastic dynamicprogramming. Wiley-Interscience, New York, 1994.[62] A. Sabouri, W. T. Huh, and S. M. Shechter. Screening strategies forpatients on the kidney transplant waiting list. 2013. (working paper).[63] A. K. Salahudeen, N. Haider, and W. May. Cold ischemia and thereduced long-term survival of cadaveric renal allografts. Kidney Inter-national, 65:713–718, 2004.[64] B. Sandikci, L. M. Maillart, A. J. Schaefer, O. Alagoz, and M. S.Roberts. Estimating the patients price of privacy in liver transplan-tation. Operations Research, 56(6):1393–1410, 2008.[65] M. J. Sarnak and A. S. Levey. Epidemiology of cardiac disease indialysis patients. Seminars in Dialysis, 12(2):69 – 76, 1999.[66] P. Schnuelle, D. Lorenz, M. Trede, and F. J. Van Der Woude. Impactof renal cadaveric transplantation on survival in end-stage renal failure:evidence for reduced mortality risk compared with hemodialysis duringlong-term follow-up. Journal of the American Society of Nephrology, 9(11):2135–2141, 1998.80Bibliography[67] P. J. Schweitzer and A. Seidmann. Generalized polynomial approxima-tions in markovian decision processes. Journal of mathematical analysisand applications, 110(2):568–582, 1985.[68] B. Sengupta. Inspection procedures when failure symptoms are delayed.Operations Research, 28(3):768–776, 1980.[69] Y. S. Sherif and M. L. Smith. Optimal maintenance models for systemssubject to failure–a review. Naval Research Logistics Quarterly, 28(1):47–74, 1981.[70] M. Shwartz. A mathematical model used to analyze breast cancerscreening strategies. Operations Research, 26(6):937–955, 1978.[71] X. Su and S. A. Zenios. Patient choice in kidney allocation: A sequen-tial stochastic assignment model. Operations Research, 53(3):443–455,2005.[72] X. Su and S. A. Zenios. Recipient choice can address the efficiency-equity trade-off in kidney transplantation: A mechanism design model.Management Science, 52(11):1647–1660, 2006.[73] L. C. Thomas, P. A. Jacobs, and P. Gaver. Optimal inspection policiesfor standby systems. Communications in Statistics-Stochastic Models,3(2):259–273, 1987.[74] USRDS. Annual Data Report: 2011 Atlas of CKD and ESRD. UnitedStates Renal Data System, 2011.[75] C. Valdez-Flores and R. M. Feldman. A survey of preventive mainte-nance models for stochastically deteriorating single-unit systems. NavalResearch Logistics, 36(4):419–446, 1989.[76] D. Wang, J. Sun, S. B. Solomon, H. G. Klein, and C. Natanson. Trans-fusion of older stored blood and risk of death: a meta-analysis. Trans-fusion, 52(6):1184 – 1195, 2012.[77] H. Wang. A survey of maintenance policies of deteriorating systems.European Journal of Operational Research, 139(3):469 – 489, 2002.[78] L. Yeh. An optimal inspection-repair-replacement policy for standbysystems. Journal of Applied Probability, 32(1):212–223, 1995.81[79] G. Zallen, P. J. Offner, E. E. Moore, J. Blackwell, D. J. Ciesla,J. Gabriel, C. Denny, and C. C. Silliman. Age of transfused bloodis an independent risk factor for postinjury multiple organ failure. TheAmerican Journal of Surgery, 178(6):570 – 572, 1999.[80] S. A. Zenios. Optimal control of a paired-kidney exchange program.Management Science, 48(3):328–342, 2002.[81] S. A. Zenios, G. M. Chertow, and L. M. Wein. Dynamic allocationof kidneys to candidates on the transplant waiting list. OperationsResearch, 48(4):549–569, 2000.[82] S. Zhang, P. Hanagal, P. I. Frazier, A. J. Meltzer, and Schneider D.B. Optimal patient-specific post-operative surveillance for vascularsurgery. Proceedings of the 7th INFORMS Workshop on Data Miningand Health Informatics (DM-HI 2012), 2012.82Appendix AChapter 2: SupportingResultsFirst we define function Ω(t, x, y), which will be used in Lemma 3 tocharacterize the first order necessary condition. Furthermore, we prove sev-eral properties of this function and use them to establish properties of theoptimal screening policy.Ω(t, x, y) :=F (t)− F (t− x)f(t)− cp∫ y0g(t+ u)H¯(t+ u)Λ(t)g(t)H¯(t)du−csΛ(t)[ F¯ (t)f(t)cp − Λ(t)cs+G¯(t+ y)H¯(t+ y)g(t)H¯(t)], (A.1)whereΛ(t) = cp − cs(1 +h(t)G¯(t)g(t)H¯(t)), (A.2)is the function introduced in Assumption 1. We remark that Λ(t) < cp sincethe expression in the parentheses is positive.Lemma 3 Any optimal screening policy T ∗ ={t∗j}nj=1 satisfies 0 < t∗1 <t∗2 < . . .. Furthermore, a necessary condition for optimality of a screeningpolicy isΩ(t∗j , x∗j , x∗j+1) = 0 for each 1 ≤ j. (A.3)Proof. Recall that the objective is to minimize C(T ) subject to 0 ≤ t1 ≤t2 ≤ . . .. We need to show that the optimal screening policy cannot bea boundary solution. Suppose, by way of contradiction, that a screeningpolicy, T , satisfies tm = tm−1 for some m ≥ 1. We will show that thisscreening policy cannot be optimal. Let T ′ ={t′j}∞j=1 be a new screeningpolicy in which, t′j = tj for j < m and t′j = tj+1 for j ≥ m. In otherwords, T ′ performs a screening at every time T does, but at time tm, T ′83Appendix A. Chapter 2: Supporting Resultsperforms one less screening than T . Using (2.1), it can be shown thatfor the new screening policy, the expected penalty cost remains unchangedwhile it removes the redundancy of screenings at time tm. More specifically,the expected screening cost of the new screening policy is smaller by theproduct of cs and the probability that the patient is alive, CVD-free andstill on the waiting list by time tm, i.e., csF¯ (tm)G¯(tm)H¯(tm). Therefore, T ′achieves lower expected total cost, from which we conclude that the optimalscreening policy is an interior solution. Thus, it should satisfy the firstorder necessary condition: ∂C(T )∂tj = 0 for each j ≥ 1. By differentiatingthe expression of C(T ) with respect to tj and setting it equal to zero, aftersimplification and rearrangement, we obtain for each j ≥ 1:Λ(tj)F (tj)− F (tj−1)f(tj)− cp∫ tj+1tjg(u)H¯(u)g(tj)H¯(tj)du− cs[ F¯ (tj)f(tj)cp − Λ(tj)cs+G¯(tj+1)H¯(tj+1)g(tj)H¯(tj)]= 0, (A.4)where, Λ(t) is defined in (A.2). Note that since Λ(tj) < cp, (A.4) impliesΛ(tj) > 0; otherwise, the left hand side of (A.4) is negative. After dividingboth sides by Λ(tj), the left hand side is equal to Ω(tj , xj , xj+1). 2Lemma 4 Suppose both the kidney arrival time and the death time followWeibull distribution, i.e., g(t) = αλ (tλ)α−1e−(tλ )αand h(t) = βµ(tµ)β−1e−(tµ )β.Also, assume that α > β ≥ 1. Then, the following statements hold forfunction Λ(t) defined in (A.2):(a) Λ(t) is increasing in t.(b) There exists some ψˆ such that Λ(t)H¯(t)g(t) is strictly decreasing in tfor all t > ψˆ.Proof. (a) This statement holds for α > β since h(t)G¯(t)g(t)H¯(t)= βλααµβ tβ−α isdecreasing in t.(b) By differentiation and after simplification, we can write:(Λ(t)H¯(t)g(t))′ = e−(tλ )αe−(tµ )β[− (cp − c1 − c2)α2λ2αt2(α−1) +O(tk)],where k < 2(α− 1). Then, the square bracket approaches −∞ as t→ +∞.It follows that there exists some ψˆ such that (Λ(t)H¯(t)g(t))′ is negative forall t > ψˆ. 284Appendix A. Chapter 2: Supporting ResultsLemma 5 For PF2 densities f and g, and for (t, x, y) ∈ R3+ such thatΛ(t) > 0, the following statements hold:(a) Ω(t, x, y) is increasing in t.(b) Ω(t, x, y) is strictly increasing in x for all y and for all t such thatt− x > 0.(c) Ω(t, x, y) is strictly decreasing in y for all t and x.Proof. (a) The following facts suffice to prove that Ω(t, x, y) is increasingin t: F (t)−F (t−x)f(t) is increasing in t andF¯ (t)f(t) is decreasing in t (Theorem 3and Corollary 3.1 in Barlow et al. [11]); Λ(t) is increasing in t (Assumption1(a)) and Λ(t) < cp;g(t+u)g(t) is decreasing in t for u > 0 since density g isPF2 (see Barlow et al. [11]); andH¯(t+u)H¯(t)= 1 − H(t+u)−H(t)H¯(t)is decreasing int since density h has IFR property.(b) Since the density function f satisfies f(a) > 0 for any a > 0, we have∂Ω(t,x,y)∂x =f(t−x)f(t) > 0. Thus, Ω(t, x, y) is strictly increasing in x.(c) Since function g(t) and H¯(t) are positive for any t > 0, we have ∂Ω(t,x,y)∂y =−Λ(t+y)H¯(t+y)g(t+y)Λ(t)H¯(t)g(t)< 0. Thus, Ω(t, x, y) is strictly decreasing in y. 2Lemma 6 Let ψf be the mode of f . For (t, x, y) ∈ R3+ such that t − x >max(ψf , ψˆ), where ψˆ is defined in Assumption 1(b), the following statementshold:(a) Ω(t, rx, ry) > rΩ(t, x, y) for any r > 1.(b) Ω(t, x+ δ, y + δ) > Ω(t, x, y) for any δ > 0.Proof. (a) Since f ′(t) < 0 for t > ψf (see Theorem 2 in Appendix 1 of Bar-low and Proschan [10]) and t−x > ψf , we have A :=∂2Ω(t,x,y)∂x2 =−f ′(t−x)f(t) >0. Similarly, for t > ψˆ, we have B := ∂2Ω(t,x,y)∂y2 = −(Λ(t+y)g(t+y)H¯(t+y))′Λ(t)g(t)H¯(t)> 0by Assumption 1(b). It follows that for t − x > max(ψf , ψˆ), the Hes-sian matrix ∇2Ω(t, x, y) =[A 00 B]is positive definite (note we take tas constant), i.e., the function Ω(t, x, y) is strictly convex in (x, y) for allt > x+ max(ψf , ψˆ). Now, for any r > 1, we can write:Ω(t, x, y) <1rΩ(t, rx, ry) +r − 1rΩ(t, 0, 0) <1rΩ(t, rx, ry),85Appendix A. Chapter 2: Supporting Resultswhere the first inequality follows from the strict convexity of Ω(t, x, y) in(x, y), and the second inequality holds since Ω(t, 0, 0) < 0 (see (A.1)).(b) Since we have f ′(t) < 0 for any t > ψf , it follows that f(t − x) > f(t)for t − x > ψf . Therefore,∂Ω(t,x,y)∂x =f(t−x)f(t) > 1 for all x and t such thatt − x > ψf and for all y. Similarly, one can show that for t > ψˆ, we have∂Ω(t,x,y)∂y =−Λ(t+y)g(t+y)H¯(t+y)Λ(t)g(t)H¯(t)> −1. Now, since Ω(t, x, y) is strictly convexin (x, y) for all t > x+ max(ψf , ψˆ) (see proof of part (a)), for any δ > 0, wecan writeΩ(t, x+ δ, y + δ) > Ω(t, x, y) +∂Ω(t, x, y)∂xδ +∂Ω(t, x, y)∂yδ > Ω(t, x, y),where the first inequality comes from the strict convexity of Ω(t, x, y) in(x, y), and the second inequality holds since ∂Ω(t,x,y)∂x > 1 and∂Ω(t,x,y)∂y > −1.2Lemma 7 Suppose that T ={tj}∞j=1 obtained recursively from (A.3). Ifthere exists m ≥ 1 such that xm+1 > xm, then xj+1 > xj for all j ≥ m.Proof. It suffices to show that if xm+1 > xm for some m, then xm+2 >xm+1 follows. From (A.3), we haveΩ(tm+1, xm+1, xm+2) = Ω(tm, xm, xm+1) = 0. (A.5)Note that tm+1 > tm and xm+1 > xm. Now, since Ω(t, x, y) is increasing int, strictly increasing in x and strictly decreasing in y (Lemma 5), we musthave xm+2 > xm+1 in order to satisfy (A.5). This completes the proof. 2Lemma 8 For any j ≥ 1, xj and tj obtained recursively from (A.3) arestrictly increasing in t1.Proof. Since x1 = t1, from (A.3) for j = 1, we have Ω(t1, t1, x2) = 0. Tosatisfy this equation, x2 must be strictly increasing in t1 since Ω(t, x, y) isincreasing in t, strictly increasing in x and strictly decreasing in y (Lemma5). Consequently, t2 = t1 + x2 is strictly increasing in t1. Now by inductivereasoning it follows that tj and xj are strictly increasing in t1 for any j ≥ 1.286Appendix BChapter 2: Proofs of MainResultsProof of Theorem 1. Suppose, by way of a contradiction, that inan optimal screening policy, the lengths of the screening intervals are notdecreasing (i.e., xm > xm−1 for some m). Then by Lemma 7, xj is strictlyincreasing in j for all j ≥ m. In particular, there exists k such that xk >rxk−1 for some r > 1 and tk−2 = tk−1 − xk−1 > max(ψf , ψˆ), where ψf andψˆ are defined in Lemma 6 (and the existence of such tk−2 is ensured byassumption that limj→∞tj =∞). Now, we can writeΩ(tk, xk, rxk) > Ω(tk, rxk−1, rxk) ≥ Ω(tk−1, rxk−1, rxk)> rΩ(tk−1, xk−1, xk) = 0 = Ω(tk, xk, xk+1),where the first two inequalities hold since Ω(t, x, y) is strictly increasing inx and increasing in t (Lemma 5), the third inequality holds by Lemma 6(a),and the last two equalities hold by Lemma 3. It follow that xk+1 > rxk sinceΩ(t, x, y) is strictly decreasing in y (Lemma 5(c)). Then, using induction,we can show that limj→∞xj =∞.From (A.1) and Lemma 3, Ω(tj , xj , xj+1) = 0 impliesF (tj)− F (tj − xj)f(tj)= cp∫ xj+10H¯(tj + u)g(tj + u)Λ(tj)H¯(tj)g(tj)du+csΛ(tj)[ F¯ (tj)f(tj)cp − Λ(tj)cs+G¯(tj + xj+1)H¯(tj + xj+1)g(tj)H¯(tj)]≤ cp∫ +∞0H¯(tj + u)g(tj + u)Λ(tj)H¯(tj)g(tj)du+csΛ(tj)[ F¯ (tj)f(tj)cp − Λ(tj)cs+G¯(tj)g(tj)], (B.1)where the inequality holds since the integrand is nonnegative and G¯(t)H¯(t)is decreasing in t. Note that the right hand side of (B.1) is bounded since87Appendix B. Chapter 2: Proofs of Main Resultsnon-negative functions F¯ (t)f(t) ,G¯(t)g(t) andH¯(t+u)g(t+u)Λ(t)H¯(t)g(t)are decreasing in t (seeproof of Lemma 5(a)). However, since F (t)−F (t−x)f(t) is strictly convex andstrictly increasing in x, and increasing in t (proofs are similar to their coun-terparts in Lemma 6(a) and Lemma 5(a)-(b)), it follows that xj → ∞ andtj → ∞ imply that the left hand side of (B.1) is unbounded. This contra-diction shows that the lengths of the optimal inspection intervals must bedecreasing. 2Proof of Theorem 2. First, we show the “if part” of the both statements.Assume t1 > t∗1. Then by Lemma 8, tj > t∗j and xj > x∗j > 0 for all j. Letδj = xj − x∗j . Then, δj > 0 for all j. Moreover, since limj→∞t∗j = ∞, thereexists some k such that t∗k−1 = t∗k − x∗k > max(ψf , ψˆ) (where ψf and ψˆ aredefined in Lemma 6). First, we establish that δj is strictly increasing for allj ≥ k. We can write:Ω(tk, x∗k + δk, x∗k+1 + δk) ≥ Ω(t∗k, x∗k + δk, x∗k+1 + δk)> Ω(t∗k, x∗k, x∗k+1)= 0= Ω(tk, xk, xk+1)= Ω(tk, x∗k + δk, x∗k+1 + δk+1),where the first inequality holds since Ω(t, x, y) is increasing in t and tk > t∗k,the second inequality follows from Lemma 6(b), and the last equality followsfrom the definition of δk and δk+1 (the other two equalities hold by (A.3)).It follow that δk+1 > δk since Ω(t, x, y) is strictly decreasing in y (Lemma5(c)). Now, we claim that limk→∞δk = +∞. To prove this claim suppose, byway of contradiction, that limk→∞δk = δˆ. Then, we have:limk→∞Ω(tk, xk, xk+1) = limk→∞Ω(tk, x∗k + δk, x∗k+1 + δk+1)= limk→∞Ω(tk, x∗k + δˆ, x∗k+1 + δˆ)> limk→∞Ω(tk, x∗k, x∗k+1)≥ limk→∞Ω(t∗k, x∗k, x∗k+1)= 0,where the first equality follows from the definition of δk and δk+1, the secondequality holds since limk→∞δk = δˆ, the last equality holds by (A.3), and the88Appendix B. Chapter 2: Proofs of Main Resultsinequalities hold by Lemma 6(b) and Lemma 5(a), respectively. However,Ω(tk, xk, xk+1) = 0 for all k and therefore cannot converge to a positivenumber. This contradiction shows that limk→∞δk = +∞. It follows that thereexists some m such that δm > t1 = x1. Then, xm = x∗m + δm > x1. Then,we have xj > xj−1 for all j ≥ m by Lemma 7. This completes the “if part”of (A).Now we consider the case that t1 < t∗1. Here, we have δj < 0 (i.e., tj < t∗jand xj < x∗j for all j), and the rest of the proof can be derived similarly toshow the existence of m such that xm < 0. More specifically, all inequalitieswould be in the reverse direction, and we conclude that limk→∞δk = −∞.Thus, there exists some m such that δm < −t∗1 = −x∗1. Then, xm = x∗m +δm < 0 since x∗m < x∗1 by Theorem 1. Since both x∗j and δj decrease asj ≥ m increases, we have xj < 0 for all j ≥ m. This completes the “if part”of (B).To show the “only if part” of (A), suppose there exists some m such thatxj > xj−1 > 0 for all j ≥ m, but t1 > t∗1 is not true, i.e., t1 ≤ t∗1. For t1 = t∗1,we cannot have xm > xm−1 for any m by Theorem 1. Furthermore, t1 < t∗1implies that there exists some q such that xj < 0 for all j ≥ q by the “ifpart” of (B). This result contradicts our initial assumption. Thus, we musthave t1 > t∗1.Finally, we show that the “only if part” of (B) is also true. Suppose thereexists some m such that xj < 0 for all j ≥ m, but t1 < t∗1 is not true, i.e.,t1 ≥ t∗1. Then, by Lemma 8, we have xj ≥ x∗j > 0. This result contradictsour assumption that xm < 0. It follows that t1 < t∗1. 289Appendix CChapter 3: Proofs of MainResultsProof of Lemma 1. Recall that the objective is to minimize C(Tn) subjectto 0 ≤ t1 ≤ t2 ≤ . . . ≤ tn ≤ tn+1. We need to show that the optimal inspec-tion policy cannot be a boundary solution. In Proposition 2 (Appendix A),we established that tn < tn+1 <∞. Suppose, by way of contradiction, thatan inspection policy, Tn, satisfies tm = tm−1 for some 1 ≤ m ≤ n. We willshow that this inspection policy cannot be optimal. Let T ′n ={t′j}n+1j=1 bea new inspection policy that performs an inspection at every time Tn does,but at time tm, T ′n performs one less inspection than Tn, and schedules thisinspection at a later time. Using (3.3), it can be shown that for the newinspection policy, the probability of incurring the penalty does not increasewhile the expected discounted inspection cost decreases since this inspec-tion is scheduled at a later time. Therefore, T ′n achieves lower expecteddiscounted cost, from which we conclude that the optimal inspection policyis an interior solution. Thus, it should satisfy the first order necessary con-dition: ∂Lα(Tn)∂tj = 0 for each 1 ≤ j ≤ n+ 1. By differentiating the expressionof Lα(Tn) given in (3.3) with respect to tj and setting it equal to zero, aftersimplification and rearrangement, we obtain for each 1 ≤ j < n:[F (tj)− F (tj−1)f(tj)−1− e−(λ+θ)(tj+1−tj)λ+ θ]−cik[1− F (tj)f(tj)+1λ+ θ]= 0,(C.1)where k = λλ+θ (cp + r + α) − (ci + r + α) by definition. Note that the lefthand side of (A.4) is equal to Ω(tj , xj , xj+1). Similarly, we can show thatthe first order necessary conditions for j = n and j = n + 1 are equivalentto (3.7) and (3.8). 2Proof of Theorem 3. It suffices to show that if xm+1[t∗1,n] > xm[t∗1,n] forsome m, then xm+2[t∗1,n] > xm+1[t∗1,n] follows. From (3.6) and (3.7), we haveΩ(tm+1[t∗1,n], xm+1[t∗1,n], xm+2[t∗1,n]) ≤ Ω(tm[t∗1,n], xm[t∗1,n], xm+1[t∗1,n]) = 0,(C.2)90Appendix C. Chapter 3: Proofs of Main Resultswhere the inequality is strict if m = n − 1. Note that tm+1[t∗1,n] > tm[t∗1,n]and xm+1[t∗1,n] > xm[t∗1,n]. Now, since Ω(t, x, y) is increasing in t, strictlyincreasing in x and strictly decreasing in y (Lemma 9 in Appendix A), wemust have xm+2[t∗1,n] > xm+1[t∗1,n] in order to satisfy (A.5). This completesthe proof. 2Proof of Lemma 2. Since x1[t1,n] = t1,n, from (3.6) for j = 1, we haveΩ(t1,n, t1,n, x2[t1,n]) = 0. To satisfy this equation, x2[t1,n] must be strictlyincreasing in t1,n since Ω(t, x, y) is increasing in t, strictly increasing inx and strictly decreasing in y (Lemma 9 in Appendix A). Consequently,t2[t1,n] = t1,n + x2[t1,n] is strictly increasing in t1,n. Now by inductive rea-soning it follows that tj [t1] and xj [t1] are strictly increasing in t1 for any 1 ≤j ≤ n. Now, from (3.7) for j = n, we have Ω(tn[t1,n], xn[t1,n], xn+1[t1,n]) =− cie−(λ+θ)xn+1k(λ+θ) < 0. Similar to the discussion above, since Ω(t, x, y) is in-creasing in t, strictly increasing in x and strictly decreasing in y, we concludethat tn+1[t1] and xn+1[t1] are also strictly increasing in t1. 2Proof of Proposition 1. By Lemma 1, the optimal inspection policy mustsatisfy the first order necessary condition. Recall the necessary condition(3.8) is given byF (tn[t1,n] + xn+1[t1,n])− F (tn[t1,n])1− F (tn[t1,n])=θ(r + α)λcp.Now, by Lemma 2 and the fact that F (t+x)−F (t)1−F (t) is increasing in t and strictlyincreasing in x (by the increasing failure rate property of density f), the lefthand side of this equality is strictly increasing in t1,n. It follows that thevalue of t1,n satisfying the necessary condition is unique (which we denoteby t∗1,n). Now, using (3.6) and (3.7), the remaining inspection times (tj [t∗1,n]for each 1 < j ≤ n) can be obtained recursively (and uniquely) by havingt∗1,n. Thus, we conclude the optimal inspection policy is unique. 291Appendix DChapter 3: SupportingResultsProposition 2 It is always optimal to schedule a replacement at a finitetime tn+1 after the last inspection time, i.e., tn < tn+1 < +∞.Proof. Let T˜n be the inspection policy that does not schedule a replace-ment at a finite time (i.e., tn+1 = +∞). First, we show that the best of suchpolicies must schedule the inspection times t1, . . . , tn at finite times. Weshow that for any inspection policy that schedules m finite inspection times(m < n) of the allotted inspection opportunities, there exists a strictly betterinspection policy that schedules m+1 inspection times. For any 1 ≤ m < n,let T˜m ={tj}mj=1 be an inspection policy with m inspection opportunitiesscheduled at finite times t1, t2, . . . , tm. Moreover, consider T˜m+1 as an inspec-tion policy with m+ 1 inspection opportunities where the first m inspectiontimes {t1, t2, . . . , tm} are the same as T˜m, and we choose the (m + 1)th in-spection time tm+1 such that 1 > F (tm+1) > F (tm)+cik+ci(1−F (tm)). Sucha value of tm+1 exists since F (tm) +cik+ci(1− F (tm))< 1 by the fact k > 0,and the F (tm+1) is strictly increasing in tm+1 (since we assumed f(t) > 0)and approaches 1 when tm+1 is sufficiently large. Then, from (3.3) and afterfurther simplification, we haveLα(T˜m+1)− Lα(T˜m) =[− (k + ci)(F (tm+1)− F (tm))+ ci(1− F (tm))]e−(λ+θ)tm+1 .By the choice of tm+1, this expression is negative. Thus, the expected totalcost can be (strictly) decreased by scheduling one more inspection at anappropriate time.92Appendix D. Chapter 3: Supporting ResultsNow, for a general inspection policy Tn, we can write after simplification:Lα(Tn) = Lα(T˜n)+∫ +∞tn+1[− cp(F (t)− F (tn))+θ(r + α)λ(1− F (tn))]λe−(λ+θ)tdt.(D.1)Then, we choose a tn+1 > tn such that the integral in (D.1) is negative (notethat for tn+1 = +∞, the integral in (D.1) is equal to zero). It suffices tofind a tn+1 that satisfies the following inequality:F (tn+1) > F (tn) +θ(r + α)λcp(1− F (tn)).Such a value of tn+1 exists sinceθ(r+α)λcp= θ(r+α)θ(r+α)+(λ+θ)(k+ci) < 1 by thefact k > 0, and the F (tn+1) is strictly increasing in tn+1 (since we assumedf(t) > 0) and approaches 1 when tn+1 is sufficiently large. Thus, an optimalinspection policy should schedule a replacement at a finite time after thelast inspection. 2Proposition 3 For any n, an optimal inspection policy T ∗n exists.Proof. For some ε > 0, let tMn+1 be a replacement time such that theintegral in (D.1) is larger than −ε for all tn+1 > tMn+1 and any value of tn.Such tMn+1 exists since the integral approaches 0 as tn+1 →∞.By Proposition 2, the optimal inspection policy should schedule a re-placement at a finite time. Now, consider an arbitrary inspection policy Tnsuch that tMn+1 < tn+1 < +∞ and let T˜∗n be the optimal inspection policy inthe class of policies that do not schedule a replacement at a finite time andtn < tn+1. Such an optimal policy exists because Lα(T˜n) is continuous andattains its minimum over the following compact set:D˜ ={0 ≤ tj ≤ tn+1, tj ≥ tj−1 for all 1 ≤ j ≤ n}.Then, we obtain from (3.3) after simplification:Lα(Tn) = Lα(T˜n)+∫ +∞tn+1[− cp(F (t)− F (tn))+θ(r + α)λ(1− F (tn))]λe−(λ+θ)tdt> Lα(T˜∗n )− ε,93Appendix D. Chapter 3: Supporting Resultswhere the first equality follows from (3.3), and the inequality comes fromthe choice of tn+1 and the fact that T ∗n minimizes Lα(T˜n). In other words,a policy that schedules inspections based on T ∗n and a replacement at tMn+1is better than any Tn with tn+1 > tMn+1. It implies that if the minimum ofLα(Tn) exists, it belongs to the following set:D ={0 ≤ tj ≤ tMn+1, tj ≥ tj−1 for all 1 ≤ j ≤ n+ 1}.Since Lα(Tn) is continuous and D is compact, it follows that Lα(Tn) attainsits minimum over the set D. Thus, an optimal inspection policy T ∗n exists.This completes the proof. 2Lemma 9 For PF2 densities f and g, and for (t, x, y) ∈ R3+, the followingstatements hold:(a) Ω(t, x, y) is increasing in t.(b) Ω(t, x, y) is strictly increasing in x for all y and for all t such thatt− x > 0.(c) Ω(t, x, y) is strictly decreasing in y for all t and x.Proof. We only prove parts (a) and (b). Proof of part (c) is similar topart (b).(a) Since the first square bracket of (3.5) is increasing in t (Theorem 3 inBarlow et al. [11]), the second square bracket of (3.5) is decreasing in t(Corollary 3.1 in Barlow et al. [11]), and k > 0, it follows that Ω(t, x, y) isincreasing in t.(b) Since the density function f satisfies f(a) > 0 for any a > 0, we have∂Ω(t,x,y)∂x =f(t−x)f(t) > 0. Thus, Ω(t, x, y) is strictly increasing in x. 294Appendix EChapter 3: SolutionAlgorithmWe first present the approximation algorithm and then we explain itslogic. The algorithm starts with an initial search interval (t, t), for whichwe can conveniently choose t = 0 and t a sufficiently large number (suchthat the probability that the failure occurs before t is close to 1). Then, thefollowing steps are followed (note for the sake of clarity, we do not show thedependence of the inspection times tj on the first inspection time):1. Given the search interval (t, t), set t1 =t+t2 , x1 = t1, and j = 1.2. If t−t < 2, STOP and return tout1,n =t+t2 as the optimal first inspectiontime t∗1,n.3. While j < n, take the following steps:(a) Compute Q := F (tj)−F (tj−xj)f(tj) −cik[1−F (tj)f(tj)+ 1λ+θ].(b) If Q ≤ 0, then set t = t1,n, and go back to Step 1.(c) If Q ≥ 1λ+θ , then set t = t1,n, and go back to Step 1.(d) Find xj+1 that satisfies 1−e−(λ+θ)xj+1λ+θ = Q. Increase j by 1 andgo back to Step 3.4. Compute Q := F (tn)−F (tn−xn)f(tn) −cik[1−F (tn)f(tn)+ 1λ+θ].(a) If Q ≤ − 1λ+θcik , then set t = t1,n, and go back to Step 1.(b) If Q ≥ 1λ+θ , then set t = t1,n, and go back to Step 1.(c) Find xn+1 that satisfies1−(1+ cik )e−(λ+θ)xn+1λ+θ = Q, and go to Step5.5. Compute Q := F (tn+xn+1)−F (tn)1−F (tn) .95Appendix E. Chapter 3: Solution Algorithm(a) If Q < θ(r+α)λcp , then set t = t1,n, and go back to Step 1.(b) If Q > θ(r+α)λcp , then set t = t1,n, and go back to Step 1.In each iteration of the algorithm, we choose the midpoint of the searchinterval as the first inspection time t1. Then, using (3.6) and (3.7), wetry to recursively find the other inspection times {t2, . . . , tn} by solving theequation 1−e−(λ+θ)xj+1λ+θ = Q for each j = 1, . . . , n− 1, which is equivalent to(3.6) (see Step 3(d)). Now, since the choice of t1 is not necessarily optimal,for some j, we might not be able to find any xj+1 that satisfies the aboveequation. Since Q is increasing in tj and strictly increasing in xj (see theproof of Lemma 9(a)-(b)), it follows that Q is strictly increasing in t1 (byLemma 2). Therefore, by checking whether the value of Q is too large ortoo small, we can decide whether to update either the lower bound or theupper bound of the search interval (see Steps 3(b) and 3(c)). The same logicapplies to the case j = n and j = n+ 1 (see Steps 4 and 5). The length ofthe next iteration’s search interval is half of the previous iteration’s searchinterval. We continue in this manner until we conclude that t∗1,n belongs to asearch interval of a required length 2. Then, the approximation algorithmreturns the midpoint of the last search interval as t∗1,n.96


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items