J Driver

G Thomas Professeur

THÈSE Na GENG Spécialités doctorales

This research is motivated by our collaborations with a large French university teaching hospital in order to reduce the Length of Stay (LoS) of stroke patients treated in the neurovascular department. Quick diagnosis is critical for stroke patients but relies on expensive and heavily used imaging facilities such as MRI (Magnetic Resonance Imaging) scanners. Therefore, it is very important for the neurovascular department to reduce the patient LoS by reducing their waiting time of imaging examinations.

From the neurovascular department perspective, this thesis proposes a new MRI examinations reservation process in order to reduce patient waiting times without degrading the utilization of MRI. The service provider, i.e., the imaging department, reserves each week a certain number of appropriately distributed contracted time slots (CTS) for the neurovascular department to ensure quick MRI examination of stroke patients. In addition to CTS, it is still possible for stroke patients to get MRI time slots through regular reservation (RTS).

This thesis first proposes a stochastic programming model to simultaneously determine the contract decision, i.e., the number of CTS and its distribution, and the patient assignment policy to assign patients to either CTS or RTS. To solve this problem, structure properties of the optimal patient assignment policy for a given contract are proved by an average cost Markov decision process (MDP) approach. The contract is determined by a Monte Carlo approximation approach and then improved by local search. Computational experiments show that the proposed algorithms can efficiently solve the model. The new reservation process greatly reduces the average waiting time of stroke patients. At the same time, some CTS cannot be used for the lack of patients.

To reduce the unused CTS, we further explore the possibility of the advance cancellation of CTS. Structure properties of optimal control policies for one-day and two-day advance cancellation are established separately via an average-cost MDP approach with appropriate modeling and advanced convexity concepts used in control of queueing systems. Computational experiments show that appropriate advance cancellations of CTS greatly reduce the unused CTS with nearly the same waiting times.

 .................................................................................... FIG. 3.5
Introduction

This thesis is motivated by our collaborations with a large French university teaching hospital in order to reduce the Length of Stay (LoS) of stroke patients treated in the neurovascular department.

A stroke is a sudden loss of the brain function caused by lack of blood supply to the brain (ischemic stroke) or rupture of blood vessels in the brain (hemorrhagic stroke). Stroke patients may suffer from the inability to speak or speak clearly, walk, or move a limb because of the lack of blood supply to the brain. The brain cannot tolerate long periods without blood flow and stroke patients need the appropriate treatment as soon as possible.

Before starting the treatment, a number of examinations are needed for diagnosis purpose. Significant delays are observed as many key examinations rely on expensive and heavily used imaging facilities such as MRI (Magnetic Resonance Imaging) scanners facing demand from all medical units of the hospital. Therefore, it is very important to reduce the LoS of stroke patients by reducing their waiting time for imaging examinations.

In this thesis, we restrict ourselves to MRI examinations for two reasons. First, delays for MRI examinations are observed as the longest ones, from 30 to 40 days. Second, joint optimization of all medical examinations is fairly complex and will be subject of our further research. Insights gained from this thesis will be exploited in joint optimization of all medical examinations.

MRI examination reservation for stroke patients 1.2.1 Stroke and MRI scan

A stroke (sometimes called an acute cerebrovascular attack) is a sudden loss of the brain function due to disturbance in the blood supply to the brain. Strokes can be grouped into two major classes: ischemic and hemorrhagic [START_REF] Kidwell | Acute ischemic cerebrovascular syndrome: diagnostic Reference 135 criteria[END_REF]), as shown in Fig. 1.1. Ischemic strokes are due to block of the blood supply to the brain, whereas hemorrhagic strokes are due to rupture of a blood vessel or an abnormal vascular structure in the brain. The affected area of the brain is unable to function, which leads to the inability to move one or more limbs in one side of the body, inability to understand or speak clearly, or inability to see one side of the visual field. A stroke is a medical emergency which can cause permanent neurological damage, complications, and death. It is the leading cause of adult disability in the United States and Europe. It is the number two cause of death worldwide and may soon become the leading cause of death worldwide (Donnan et al. (2008)).

Stroke diagnosis needs rapid access to medical personnel and diagnosis facilities. So all tests can be done timely, and the right diagnosis can be made, and appropriate treatment can be provided. The diagnosis of stroke itself is clinical, with assistance from the imaging techniques in finding the causes of stroke. There are two major imaging techniques: Computed Tomography (CT) scanner and MRI scanner.

When stroke patients are diagnosed, many other examinations have to be performed in order to determine the underlying etiology. Commonly used techniques include: an ultrasound/doppler study of the carotid arteries (to detect carotid stenosis) or dissection of the precerebral arteries an electrocardiogram (ECG) and echocardiogram (to identify arrhythmias and resultant clots in the heart which may spread to the brain vessels through the bloodstream)

Chapter 1 Planning of MRI examinations: Introduction 3 a Holter monitor study to identify intermittent arrhythmias an angiogram of the cerebral vasculature (if a bleed is thought to have originated from an aneurysm or arteriovenous malformation) blood tests to determine hypercholesterolemia, bleeding diathesis and some rarer causes such as homocysteinuria Among all the examinations, MRI scan is one of the most helpful tests in the diagnosis of stroke because it can detect strokes within minutes of their onset and is superior to CT. As shown in Fig. 1.2, MRI scanner, or nuclear magnetic resonance imaging (NMRI) scanner, is primarily a medical imaging technique most commonly used in radiology to visualize detailed internal structure and limited function of the body. MRI provides much greater contrast between different soft tissues of the body than CT does, which makes it especially useful in neurological, musculoskeletal, cardiovascular, and oncological imaging. Unlike CT, it uses no ionizing radiation, but uses a powerful magnetic field to align the nuclear magnetization of hydrogen atoms in water in the body.

A new MRI scanner is very expensive, cost about $2 million, with a commensurate cost for building and preparing the space it needed. Therefore, hospital managers are under great pressure to keep high utilization ratio of such facilities, which makes patients to wait long time for imaging examinations.

MRI examination reservation process

The pathway of stroke patients is shown in Fig. 1.3. Nearly all stroke patients arrive at the hospital through the emergency department. When a potential stroke patient arrives at the hospital, CT scan and/or Echocardiography is scheduled to identify the type of the stroke. After this examination, the patient is transferred to the neurovascular department of the hospital. The first checkup is performed by an intern. Then a senior physician examines the patient. Patient LoS is initially determined by neurologists. A certain number of medical examinations are needed and requested by neurologists during the visits.

Patient Leave

Reserve by Phone/fax FIG. 1.3 Pathway of stroke patients If the stroke is not so heavy, the patients may be allowed to leave the hospital before getting all examinations. In this case, the LoS of patients depends on the waiting time for imaging examinations. At the end of his/her stay, the patients go back home or is transferred to a special medical unit for rehabilitation. The transfer time also depends on the time of medical examinations.

In the related French hospital, the same-day examinations are requested by phone for emergency patients. For the patients with stable status, appointments are made by the secretaries by fax. If patients are available, then examinations are scheduled. The delay for examinations depends heavily on the experiences of the secretary and the personal relationship with the secretary of the imaging department. Often, appointments for patients that no longer need the examination for various reasons are not cancelled but kept by the neurovascular department for other patients. This examination reservation process seems simple but time-consuming as it needs the informal collaboration of neurovascular department, medical imaging department and patients. In France, the actual delay for obtaining a time slot for examination is very long, more than 30 days for a regular MRI request. This negatively impacts the LoS but most importantly threatens the life of patients.

Problems and contributions

Imaging examination delays can be improved either from the service provider side (the imaging department), i.e. better schedule of examination demands, or from the client side, i.e. the neurovascular department side. The management of a diagnostic facility from imaging department side consists of two interrelated tasks [START_REF] Green | Managing patient service in a diagnostic medical facility[END_REF]): establishing an appointment schedule for outpatients, and designing a system of dynamic priority rules for admitting patients into service in real time. Appointment scheduling refers to the determination of the duration, number, and timing of time slots for a particular day. Dynamic priority rules provide the real-time control of access to the facility by priorities of different patients.

The improvement of the operations of the imaging department involves the whole hospital and concerns too many medical services. For this reason, we start from the neurovascular department perspective and develop solutions. We performed six-month field observation of the neurovascular department and collected data concerning patient arrival, medical examinations requested for each patient, delays of these examinations, and LoS of the patient. A detailed analysis of the historical data, as shown in Fig. 1.4, reveals that the neurovascular department has a large but rather stable weekly demand for medical examinations. The neurovascular department is actually the largest customer of the imaging department. Further, MRI examination of stroke patients takes nearly the same time, i.e. one time slot of about 30 minutes. FIG. 1.4 Historical data collected from the neurovascular department Fri.

Sat.

Sun.

Chapter 1 Planning of MRI examinations: Introduction Based on the observation in the neurovascular department in the hospital under study, we propose a contract-based MRI examination reservation process. The imaging department reserves each week a certain number of appropriately distributed time slots (contracted time slots, CTS) for the neurovascular department. When needed, patients can still get extra MRI time slots through regular reservation (regular time slots, RTS) which takes much longer time with a delay of over 30 days. The contract-based examination reservation process is characterized by the following decisions and control policies: Contract decisions, i.e., the number of CTS and its distribution over time; Patient assignment control policy, which assigns patients to either CTS or RTS. If the patient is assigned to CTS, then he/she will wait for CTS in the following days. Else, his/her examination will be reserved through regular MRI examination reservation process. Advance CTS cancellation policy, which cancels the CTS in advance when there are no enough stroke patients to fill contracted time slots. This thesis provides a mathematical analysis of the contract-based approach under the following assumptions: Assumption 1: Only MRI examinations are considered and each patient requires one MRI time slot. Each patient can be assigned to either one CTS or one RTS. Assumption 2: Emergency patients are not considered in this thesis. All patients have equal priority.

Assumption 3: Patient arrivals vary during a week but are stationary from one week to another. Further, the number of arrivals in one day is independent of the arrivals of other days.

Assumption 4:

The same contract is used for different weeks, i.e. n t = n t+7 for all t where n t denotes the number of CTS of day t. As a result, the contract can be represented by a 7-entry integer-valued vector n= {n 1 ,…, n7}.

Another major assumption is the focus on the neurovascular department which is the most important consumer of MRI examinations. The impact of the MRI examination reservations from this department on other departments sharing the MRI facilities is neglected.

The contributions are described as follows:

The first chapter introduces the stroke, MRI scanner, and regular MRI examination reservation process for stroke patients. We also define the problems solved in this thesis.

The second chapter reviews the state-of-the-art of methods and approaches used for the related problems.

The third chapter proposes a stochastic programming model to simultaneously determine the contract decision and patient assignment policy. In order to solve this model, patient assignment policy is first established via a Markov Decision Process (MDP) method. Then, Monte Carlo optimization and local search are used to determine the contract decisions. Computational experiments show that the proposed algorithms can efficiently solve the model. The new reservation process can greatly reduce the average waiting time of stroke patients at the expense of some unused CTS.

The fourth chapter exploits the possibility of one-day advance CTS cancellation to improve the contract-based MRI examination reservation process. An average-cost MDP formulation is proposed to determine patient assignment and one-day advance CTS cancellation control policies at the same time. Local search is used to improve the contract decisions with the known policies. Computational results show that one-day advance CTS cancellation can greatly reduce the unused CTS ratio with a little increase in average delay.

In the fifth chapter, we extend the one-day advance cancellation to two-day advance cancellation. The patient assignment, one-day advance cancellation, and two-day advance cancellation control policies for average-cost MDP are established via discounted-cost MDP and advanced convexity concepts. Contract decisions are further improved by local optimization. Computational results show that the criterion values can be further reduced.

Chapter 6 concludes the thesis.

Chapter 2

Literature review

This chapter presents a literature review for existing methods and approaches related to the MRI examination reservation problem. There are several streams relevant for this thesis, including the management of diagnostic services, appointment scheduling, capacity allocation of hospital resources; and similar problems in other fields.

Managing diagnostic services

The management of diagnostic devices, such as computer tomography (CT) and MRI scanners, has received limited coverage. The two earliest contributions are [START_REF] Walter | A comparison of appointment schedules in a hospital radiology department[END_REF] and [START_REF] Lev | Patient flow analysis and the delivery of radiology service[END_REF]. Simulation studies were performed in [START_REF] Walter | A comparison of appointment schedules in a hospital radiology department[END_REF] to investigate the effect of scheduling rules on patient waiting time for X-rays in a radiology department. [START_REF] Lev | Patient flow analysis and the delivery of radiology service[END_REF] pointed out that the design of the management systems and scheduling techniques were the emphasis for improving radiology services. [START_REF] Vasanawala | Accommodation of requests for emergency US and CT: Applications of queueing theory to scheduling of urgent studies[END_REF] used queuing theory to predict the optimal number of schedule slots to reserve for urgent CT and ultrasonography. Emergency studies were modeled as a Poisson process; and slots were reserved such that the rate of rescheduling of routine studies to accommodate emergencies is below a certain level. Effective allocation of expensive imaging diagnosis capacity among several classes of patients within a day was addressed in [START_REF] Green | Managing patient service in a diagnostic medical facility[END_REF]. Three classes of patients were considered: inpatients, outpatients, and emergency patients. They considered two interrelated problems: the outpatient appointment schedule and the dynamic priority rules for admitting patients into service. The problem was formulated as a finite-horizon dynamic program and properties of the optimal policies have been identified, in order to design the outpatient appointment schedule, and establish dynamic priority rules for admitting patients into services. A simple approach for dividing the available diagnosis capacity between emergency and inpatients on the one hand and outpatients on the other was proposed in [START_REF] Patrick | Improving resource utilization for diagnostic services through flexible inpatient scheduling: A method for improving resource utilization[END_REF]. The authors looked at the benefit of reserving space for carrying over a percentage of non-emergency inpatient demand to the next day. [START_REF] Patrick | Dynamic Multipriority Patient Scheduling for a Diagnostic Resource[END_REF] addressed the admission of multi-priority patients on a waiting queue to a diagnostic resource. They used an MDP framework to model the dynamical scheduling problem of multi-priority patients to a diagnosis facility in a public health care setting and proposed an Chapter 2 Literature review approximate dynamic programming approach to overcome the state space explosion problem. A dynamic capacity allocation problem for several priority classes patients was considered in Erdelyi and Topaloglu (2009) with protection level policies. Protection levels were used to "protect" a part of the capacity from the lower priority jobs so as to make it available for the future higher priority jobs. A simulation-based optimization approach was proposed to find a good set of protection levels. It combined a perturbation analysis technique to evaluate the gradient with respect to the protection levels and a stochastic approximation approach to determine the optimal protection levels.

The allocation of two CT-scanners was considered in [START_REF] Kolish | Providing radiology health care services to stochastic demand of different customer classes[END_REF] by providing medical services to three patient groups with different arrival patterns and cost-structures. The problem was formulated as an MDP with the aim of allocating the available resources dynamically to patients of the three groups such that the expected total reward was maximized. [START_REF] Sickinger | A generalized bailey-welch rule and simple tabu search procedure for outpatient appointment scheduling[END_REF] pursued the previous work to determine the optimal number of outpatients to be scheduled and assign the outpatients to a variableblock/fixed-interval appointment schedule. An MDP approach was proposed in [START_REF] Schutz | Capacity allocation for magnetic resonance imaging scanners[END_REF] to decide whether to accept requests for MRI examinations from patients with different priorities such as inpatients and outpatients. Different examination types, cancellations, no-shows and over-booking, and same-day demand were considered.

Appointment scheduling

Appointment scheduling is the problem of assigning a specific time when the patient is scheduled to start receiving care [START_REF] Gupta | Appointment scheduling in health care: Challenges and opportunities[END_REF]). The appointment scheduling in general was reviewed in [START_REF] Mondschein | Appointment policies in service operations: A critical analysis of the economic framework[END_REF], while [START_REF] Magerlein | Surgical demand scheduling: A review[END_REF] and [START_REF] Blake | Surgical process scheduling: a structured review[END_REF] summarized articles on surgery scheduling, and [START_REF] Cayirli | Outpatient scheduling in health care: A review of literature[END_REF] provided excellent reviews on outpatient appointment systems, and [START_REF] Gupta | Appointment scheduling in health care: Challenges and opportunities[END_REF] surveyed appointment scheduling in health care system. Here we focus on the two latest reviews and some latest articles which are not included in the review. [START_REF] Cayirli | Outpatient scheduling in health care: A review of literature[END_REF] classified the outpatient appointment scheduling literature as follows: 1) static vs. dynamic appointment scheduling; 2) performance measures; 3) system design; and 4) methodology. The most common appointment system in health care is the static appointment scheduling, where all decisions must be made before the start of a clinic session. The dynamic case can adjust the appointment time based on the current state of the system, which is most applicable in situations where patients are already admitted to a hospital or clinic. Most of the literature focuses on the static case, because the outpatient schedule for a session must be finished before the session begins. The simplest case is when all scheduled patients arrive on time and a single doctor serves them with stochastic processing times. If more doctors and more services are considered, the problem becomes more difficult. The patient lateness, no-shows, walk-ins, and emergencies may make it more complex. A representative set of papers on static appointment scheduling includes Vanden [START_REF] Vanden Bosch | Minimizing expected waiting in a medical appointment system[END_REF], [START_REF] Denton | A sequential bounding approach for optimal appointment scheduling[END_REF], and [START_REF] Robinson | Scheduling doctors' appointments: optimal and empirically-based heuristic policies[END_REF] et al. There is numerous performance criteria used to evaluate a given schedule. They are classified as time, congestion, and fairness. Time based measures include patients' waiting time, physician idle time, and staff overtime. Congestion based measures mainly refer to the mean number of patients in the queue. Fairness based measures focus on the even distribution of patients' waiting time over the day. [START_REF] Mondschein | Appointment policies in service operations: A critical analysis of the economic framework[END_REF] provide a detailed review of performance measures. The design of the appointment system can be decomposed into three decisions: a) the appointment rule, b) the use of patient classification, and c) the adjustments made to reduce the disruptive impact of walk-ins, no-shows, and/or emergency patients. The appointment rule is typically specified by three parameters, the "block-size", i.e., the number of patients scheduled to this block, the "initial-block", i.e., the number of patients given the same appointment time at the start of a session, and "appointment interval", i.e., the interval between two appointments. Any combination of the above parameters is a possible appointment rule. Patient classification in outpatient scheduling can be used for two purposes: to sequence patients at the time of booking; and/or make the adjustment for the intervals based on the different service time of different patient class. The design of an appointment system must consider the possible adjustments for no-shows, walk-ins, urgent patients, and /or emergencies. This problem is addressed in [START_REF] Ho | Minimizing total cost in scheduling outpatient appointments[END_REF], [START_REF] Cayirli | Designing appointment scheduling systems for ambulatory care services[END_REF], [START_REF] Harper | Reduced outpatient waiting times with improved appointment scheduling: a simulation modelling approach[END_REF], [START_REF] Wijewickrama | Simulation analysis of appointment scheduling in an outpatient department of internal medicine[END_REF] and [START_REF] Wijewickrama | Simulation analysis for reducing queues in mixed-patients' Reference outpatient department[END_REF]. Methods can be classified as analytical and simulation-based. Analytical methods include queuing theory and mathematical programming methods. The simulation studies include [START_REF] Babes | Out-patient queues at the Ibn-Rochd health centre[END_REF], [START_REF] Cayirli | Designing appointment scheduling systems for ambulatory care services[END_REF], [START_REF] Harper | Reduced outpatient waiting times with improved appointment scheduling: a simulation modelling approach[END_REF], and [START_REF] Rohleder | Rolling horizon appointment scheduling: A simulation study[END_REF], etc., while the analytical include [START_REF] Robinson | Scheduling doctors' appointments: optimal and empirically-based heuristic policies[END_REF][START_REF] Vanden Bosch | Scheduling customer arrivals to a stochastic service system[END_REF][START_REF] Vanden Bosch | Minimizing expected waiting in a medical appointment system[END_REF], etc. [START_REF] Gupta | Appointment scheduling in health care: Challenges and opportunities[END_REF] described the appointment scheduling in three different environment, including primary care appointment scheduling, specialty clinic appointment scheduling, and scheduling elective surgery appointments. Complicating factors were discussed, including arrival and service time variability, patient and care provider preferences, and available information technology, etc. The articles were characterized into three themes according to the complicating factors. The readers are referred to [START_REF] Gupta | Appointment scheduling in health care: Challenges and opportunities[END_REF] for details. [START_REF] Cayirli | Assessment of patient classification in appointment system design[END_REF] investigated two approaches to patient classification by simulation. The first one used patient classification only for sequencing patient appointments at the time of booking. The second used patient classification for both sequencing and appointment interval adjustment, in which appointment intervals were adjusted to match the consultation time characteristics of different patient classes. Simulation results showed that new appointment systems that used interval adjustment for patient class were efficient in improving doctors' idle time, doctors' overtime and patients' waiting times without any trade-offs. Practical guidelines have been developed for managers responsible for designing appointment systems. To deal with the problem of last-minute cancellation or "no-shows", [START_REF] Green | Reducing Delays for Medical Appointments: A Queueing Approach[END_REF] proposed a new conception of appointment system, which was similar to a single-server queuing system. In this system, customers to enter service had a state-dependent probability of not being served and might rejoin the queue. Experimental results showed that the queuing models could provide efficient guidance in identifying patient panel sizes for medical practices that were trying to implement a policy of "advanced access". [START_REF] Muthuraman | A stochastic overbooking model for outpatient clinical scheduling with no-shows[END_REF] developed an appointment scheduling policy for outpatient clinics with overbooking used to compensate for the possible patient no-show. The objectives were to minimize patient wait times, maximize resource utilization, and minimize the number of patients waiting at the end of the day. Patients should be served during over time if there were patients waiting at the end of day. Conditions under which the objective evolution is unimodal have been derived and the behavior of the scheduling policy has been investigated under a variety of conditions. A Markov decision process model was proposed in [START_REF] Gupta | Revenue management for a primary-care clinic in the presence of patient choice[END_REF] to solve the capacity management problem of a the clinic, i.e. the determination of which appointment requests to accept in order to maximize revenue. In this model, the patients' choice behavior was modeled explicitly. When the clinic is served by a single physician, the optimal policy has been identified as a threshold-type policy as long as the choice probabilities satisfy a weak condition. For a multiple-doctor clinic, the structure of the optimal policy has been partially characterized. Several heuristics and an upper bound were proposed. Numerical experiments demonstrated that the two heuristics based on the partial characterization of the optimal policy were quite accurate. A semiclosed migration network was used in [START_REF] Lee | Optimal Capacity Overbooking for the Regular Treatment of Chronic Conditions[END_REF] to capture patient flow into a clinic and between the clinic and hospital. Temporary patient absences were considered. A simple class of stationary control policies for patient admissions was proposed and algorithms were provided for selecting the one that maximizes long-run average earnings.

Planning and allocation of hospital resources

Planning and allocation of operating rooms

Decisions pertaining to the planning and allocation of operating rooms are among the most critical day-to-day problems faced by hospitals. These decisions have influence not only on the quality of care of patients but also on the crucial relationship between the hospital and physicians who work there. [START_REF] Cardoen | Operating room planning and scheduling: A literature review[END_REF] provided a comprehensive review of recent operational research literature on operating room planning and scheduling. The related articles have been classified into 7 classes based on the criteria, including patient characteristics, performance measures, decision levels, type of analysis, solution techniques, uncertainty, and applicability of research. Some interesting articles are reviewed according to the above classifications. 1) In the literature of operating room planning and scheduling, two major patient classes are considered: elective and non-elective patients. The former refers to patients whose surgery can be planned in advance, and the latter usually refers to emergency patients, needing surgery as soon as possible, and urgent patients, needing surgery within a short period. Elective patients can be divided into inpatients and outpatients. The surgery operation scheduling problem with elective patients considered was addressed in [START_REF] Perdomo | Operating theatre scheduling using Lagrangian relaxation[END_REF] and [START_REF] Augusto | Operating theatre scheduling using Lagrangian relaxation[END_REF], with two types of resources considered, including operating rooms and recovery beds. The problem was formulated as the assignment of patients to operating rooms and recovery beds with the objective of minimizing the sum over all patients of one defined function of their completion times. A Lagrangian relaxation approach was proposed to determine a near optimal schedule and a tight lower bound. The allocation of medical service capacity between distinct demand streams was analyzed in [START_REF] Gerchak | Reservation planning for elective surgery under uncertain demand for emergency surgery[END_REF] in the setting of an operating room where the capacity was shared between elective and emergency surgeries. This reference focused on the reservationplanning policy for elective patients by determining at the start of each day how many additional elective surgeries to assign for that day. A stochastic dynamic programming model was proposed for this problem. The nature of the optimal policy was analyzed and characterized, which was not necessarily of a control-limit type.

2) There are many performance measures used to evaluate the performance of the planning and scheduling methods. The waiting time of patients or surgeons is one common evaluation measures. The other criteria include throughput, utilization, leveling, makespan, patient deferral/refusal, finance, and preferences, etc.

Chapter 2 Literature review [START_REF] Denton | Optimization of surgery sequencing and scheduling decisions under uncertainty[END_REF] examined how case sequencing influenced patient waiting time, operating room idling and overtime. A stochastic optimization model was formulated and some practical heuristics were proposed for computing operating room schedules that hedged against the uncertainty in surgery durations. Sequencing surgeries and scheduling start times were also considered by a simple sequencing rule based on surgery duration variance. The rule was used to generate substantial reductions in total surgeon and operating room team waiting, operating room idling, and overtime costs.

3) There are many solution techniques, including mathematical programming, simulation, constructive heuristics, improvement heuristics, dedicated branch-and-bound, and analytical procedures. Mathematical methods are well applied in planning and scheduling of operating rooms. [START_REF] Guinet | Operating theatre planning[END_REF] addressed the operating theatre planning over a medium term horizon (one or two weeks). The operating theatre under consideration was composed of several operating rooms and one recovery room where several beds were available. An extension of the Hungarian method has been developed to calculate the operating theatre planning. [START_REF] Belien | Building cyclic master surgery schedules with leveled resulting bed occupancy[END_REF] proposed and evaluated a number of models for building surgery schedules with leveled bed occupancy. A number of mixed integer programming based heuristics and a metaheuristic have been developed to minimize the expected total bed shortage. A stochastic programming model for operating room planning with two types of surgery demands: elective and emergency was proposed in Lamiri et al. (2008a). A Monte Carlo optimization method was used to solve this model. Lamiri et al. (2008b) addressed the problem of scheduling patients in a hospital operating theatre, where three types of resources were considered: porters, operating rooms and recovery beds. The problem was formulated as the assignment of patients to the different resources in order to minimize a criterion function of patients' completion times. Column generation was used as a decomposition approach to solve the scheduling problem. Numerical results have illustrated that column generation is a promising decomposition approach for the scheduling problem. A methodology was developed in [START_REF] Zhang | A mixed integer programming approach for allocating operating room capacity[END_REF] for allocating operating room capacity to specialties. A finite-horizon mixed integer programming (MIP) model was built to determine a weekly operating room allocation template that minimizes inpatients' cost measured as their length of stay. [START_REF] Wang | A Fuzzy Multi-objective Optimizing Scheduling for Operation Room in Hospital[END_REF] developed a fuzzy multi-objective programming model to optimize the operating room scheduling. A multi-objective combinatorial optimization problem was addressed in [START_REF] Cardoen | Optimizing a multiple objective surgical case sequencing problem[END_REF], which determined the sequence of patients within the operating rooms of a freestanding ambulatory surgical center. Mixed integer linear programming solution approaches have been developed. Discrete-event simulation is an effective tool for planning and allocation of resources to improve patient flow, while minimizing health care delivery costs and increasing patient satisfaction. Intensive care unit (ICU) is a limited and critical resource. [START_REF] Ridge | Capacity planning for intensive care units[END_REF] developed a simulation model for bed capacity planning in intensive care. By this model, they have found non-linear relationship exists between numbers of beds, average occupancy level and the numbers of patients that have to be transferred due to the lack of beds. The compromise between bed occupancy and the number of transfers was also considered. [START_REF] Kim | Analysis of capacity management of the intensive care unit in a hospital[END_REF] utilized queuing and simulation models to analyze the admission-anddischarge processes of one particular ICU. The beds of an ICU are scarce resources. The stochastic demands and random service times make it difficult to manage that resource. The admission of elective-surgery patients can be delayed. In order to minimize the number of cancelled surgeries, [START_REF] Kim | Flexible bed allocation and performance in the intensive care unit[END_REF] proposed a simulation model to evaluate the bedreservation schemes by reserving the ICU beds for the exclusive use of the elective-surgery patients. [START_REF] Shmueli | Optimizing Admissions to an Intensive Care Unit[END_REF] presented a model for optimizing admissions to an ICU in order to maximize the expected incremental number of lives saved from operating the ICU. Queuing theory was used to model the probability distribution of the number of occupied ICU beds. Three different admissions policies have been considered: first come first served, first come first served for all referrals whose expected incremental survival benefits gained from ICU admission exceed some threshold, and first come first served for all referrals whose expected incremental survival benefits exceed a bed specific threshold that depends upon the number of occupied beds. Experimental results showed that the last two methods could save more lives. [START_REF] Persson | Analysing management policies for operating room planning using simulation[END_REF] analyzed the operating room planning at a department of orthopedic surgery in Sweden. A discrete-event model was used to solve the problem of handling uncertainty in patient arrival and surgery duration and at the same time maximizing the utilization of operating room. The experiments have demonstrated that the operating room department can perform much better by applying a different policy in reserving operating room capacity for emergency cases together with a policy to increase staff in stand-by. 4) In terms of decision levels, there are different combinations between type, i.e., date, time, room, capacity, and level, i.e., discipline, surgeon, and patient level. For example, Blake et al. (2002) and Blake and donald (2002) used integer programming model for a decision concerning date and room, i.e., the determination of each specialty what operating room types were assigned to what days of the week. At the surgeon level, [START_REF] Belien | Visualizing the demand for various resources as a function of the master surgery schedule: A case study[END_REF] introduced a software tool in order to decide when and where the surgeries had to be performed.

5)

The types of analysis mainly include optimization, scenario analysis, and complexity analysis. The combinatorial optimization methods are either exact, for instance, [START_REF] Belien | A branch-and-price approach for integrating nurse and surgery scheduling[END_REF] and [START_REF] Calichman | Creating an optimal operating room schedule[END_REF], or heuristic, for example, Blake and donald (2002) and [START_REF] Marcon | The operating theatre planning by followup of the risk of no realization[END_REF]. Scenario analysis refers to those focusing on the impact of different operating room setting. For example, [START_REF] Niu | Performance analysis of the operating room using simulation[END_REF] used a simulation model with different scenarios of resource capacities. The computational complexity of the combinatorial problem or the corresponding solution approach was also analyzed. For example, Lamiri et al. (2008a) used the 3-partition problem in order to prove that their problem is strongly NP-hard and very difficult to solve. 6) With respect to uncertainty, there are two classes: deterministic and stochastic. Deterministic planning and schedule approaches ignore the uncertainties inherent to surgical services, for example, [START_REF] Adan | Patient mix optimisation in hospital admission planning: a case study[END_REF] and [START_REF] Arenas | Analysis via goal programming of the minimum achievable stay in surgical waiting lists[END_REF]; whereas uncertain approaches try to include such uncertainties. Two types of uncertainty are mainly considered, i.e., arrival uncertainty and duration uncertainty. The former refers to the uncertain arrival of emergency patients and the lateness of surgeons at the start of the surgery session, and the latter represents deviations between the actual and the planned durations of activities associated with the surgical process. For example, [START_REF] Harper | A framework for operational modelling of hospital resources[END_REF] included the patient arrival uncertainty in a detailed hospital capacity simulation model and [START_REF] Persson | Analysing management policies for operating room planning using simulation[END_REF] considered both patient arrival uncertainty and surgery duration variability to study how resource allocation policies affected the waiting time and utilization of emergency resources.

Planning and allocation of other hospital resources

Mathematical method is one of the most popular methods in this field. [START_REF] Hsu | Scheduling patients in an ambulatory surgical center[END_REF] presented a deterministic approach to schedule patients in an ambulatory surgical center with the objective of minimizing the number of post anesthesia care unit nurses at the center. The patient scheduling problem was formulated as new variants of the no-wait, two-stage process shop scheduling problem. A tabu search-based heuristic algorithm has been proposed to solve the patient scheduling problem. With respect to the problem of nurse scheduling, [START_REF] Cheng | Simulated Annealing Algorithm for Scheduling Problem in Daily Nursing Cares[END_REF] modeled the daily nursing care scheduling problems and proposed an efficient scheduling method based on simulated annealing algorithm. [START_REF] Olivares | Structural estimation of the newsvendor model: An application to reserving operating room time[END_REF] applied the newsvendor model to a hospital that tried to balance the costs of reserving too much or too little operating room capacity to cardiac surgery cases. Results have shown that the hospital placed more emphasis on the tangible costs of having idle capacity than on the costs of schedule overrun and long working hours for the staff.

The efficient radiotherapy patient scheduling, within oncology departments, was addressed in [START_REF] Conforti | Optimization models for radiotherapy patient scheduling. 4or-a[END_REF]. Novel optimization models have been proposed with the objective of minimizing patients' waiting time and maximizing the equipment utilization. Experimental results have shown that the proposed methods perform better than the human experts (i.e., the number of patients that begin the radiotherapy treatment is maximized). [START_REF] Conforti | Non-block scheduling with priority for radiotherapy treatments[END_REF] proposed an approach based on a well tailored integer linear optimization program, modeling a non-block scheduling strategy in order to minimize the mean waiting time or maximize the number of new scheduled patients. An integer programming formulation was proposed in [START_REF] Gunes | Health network mergers and hospital re-planning[END_REF] for the hospital re-planning problem which arose after hospital network mergers. The model has found the best re-allocation of resources among hospitals, the assignment of patients to hospitals and the service portfolio to minimize the system costs subject to quality and capacity constraints.

An MDP method was proposed in [START_REF] Thompson | Efficient Short-Term Allocation and Reallocation of Patients to Floors of a Hospital During Demand Surges[END_REF] to allocate and reallocate patients to different floors of a hospital during demand surges. Decisions such as patient assignment and reactive or proactive patient transfers have been considered. [START_REF] Min | An elective surgery scheduling problem considering patient priority[END_REF] addressed a scheduling problem where patients with different priorities were scheduled for elective surgery in a surgical facility with a limited capacity. A stochastic dynamic programming model was formulated to schedule the patients. A structural analysis of the proposed model has been conducted to understand the properties of an optimal schedule policy. Based on the structural analysis, bounds on feasible actions have been incorporated into a value iteration algorithm, and a brief computation experiment has shown the improvement in computational efficiency.

Except for mathematical method, there are some other methods used in this field. [START_REF] Ho | Evaluating the impact of operating conditions on the performance of appointment scheduling rules in service systems[END_REF] used simulation to evaluate the impact on appointment schedules of the environmental factors, including probability of no-show, the coefficient of variation of service times, and the number of customers per service session. [START_REF] Jun | Application of discrete-event simulation in health care clinics: A survey[END_REF] surveyed the application of discrete-event simulation modeling to health care systems. [START_REF] Vissers | Patient Flow based Allocation of Hospital Resources[END_REF] developed an approach to allocate resources to specialties according to demand. The balanced utilization of the resources was considered. The proposed approach has utilized a set of models to support hospital managerial decision making on resource allocation issues. The allocation of inpatient resources was considered in [START_REF] Vissers | Patient flow-based allocation of inpatient resources: A case study[END_REF] within a hospital setting in the form of case study. An allocation procedure has been described that takes patient flows as its starting point and enables an evaluation of combined influences on the different resources concerned. [START_REF] Bharadwaj | Scheduling cardiac procedures: A knowledge-Reference based approach[END_REF] proposed a knowledge-based approach for solving the scheduling problem in a large cardiac center. System architecture has been derived that integrates Chapter 2 Literature review principles of opportunistic planning and reason maintenance. The former allows for incremental schedule construction, while the latter makes sure that the system records the reasons for scheduling decisions and revises the schedule whenever conflicts or new opportunities for schedule improvement arise.

Related problems in other fields

Allocating service capacity among competing customer classes has been studied in diverse applications including airlines seat management [START_REF] Belobaba | Application of a probabilistic decision model to airline seat inventory control[END_REF], [START_REF] Barut | Design and evaluation of a dynamic capacity apportionment procedure[END_REF], [START_REF] Haerian | Modeling revenue yield of reservation systems that use nested capacity protection strategies[END_REF]), hotels management [START_REF] Liberman | Hotel Overbooking Problem -Inventory System with Stochastic Cancellations[END_REF], [START_REF] Bitran | Managing hotel reservations with uncertain arrival[END_REF]), car rental [START_REF] Carroll | Evolutionary change in product management experiences in the car rental industry[END_REF], [START_REF] Geraghty | Revenue management saves national car rental[END_REF]), telecommunications [START_REF] Ross | The Stochastic Knapsack-Problem[END_REF], [START_REF] Altman | On optimal call admission control in a resource-sharing system[END_REF], [START_REF] Ormeci | Admission policies for a two class loss system with general interarrival times[END_REF]), and call center management [START_REF] Perros | Call admission control schemes: A review[END_REF], [START_REF] Gans | Telephone call centers: Tutorial, review, and research prospects[END_REF] ). The capacity allocation in the last two research streams is often modeled as a dynamic priority queuing control problem. The service in some of the business environment, for example, hotel management, call center, etc., cannot be delayed. However, the service for patients can be delayed with some penalties.

Capacity protection is one of the most popular methods to deal with the capacity allocation problem with multiple priorities of demands. A dynamic capacity allocation problem was considered in Erdelyi and Topaloglu (2009), where jobs of different priorities arrived randomly over time and a decision was required on which jobs should be scheduled on which days. The authors have identified a class of policies defined by a set of protection levels, which protects a portion of the capacity from the lower priority jobs so as to make it available for the future higher priority jobs. A stochastic approximation method has been developed to find a good set of protection levels. [START_REF] Shumsky | Dynamic Capacity Management with Substitution[END_REF] examined a multi-period capacity allocation model with upgrading. In this reference, multiple product types and multiple classes of demand were considered. The optimal allocation policy is a simple two-step algorithm: First, use any available capacity to satisfy same-class demand, and then upgrade customers until capacity reaches a protection limit, so that in the second step the higher-level capacity is rationed.

Conclusion

This thesis differs from the previous studies on diagnostic facility management by investigating the problem from a totally different perspective and explores solutions from the client side, i.e. from the neurovascular department side. The use of contract gives a long term view of diagnostic capacity available and the neurovascular department can better manage the priority of the stroke patients and reduce waiting time for MRI examination. From the perspective of the imaging department, although the use of contract potentially leads to unused time slots, it also gives the imaging department stable and known demands which can be used to improve staff scheduling and MRI facility scheduling. From a methodological point of view, our approach seems related to capacity allocation such as staffing in call center management [START_REF] Gans | Telephone call centers: Tutorial, review, and research prospects[END_REF]). Capacity allocation in this context also has to take into account random demands. The major difference with our problem is the acceptable waiting time. In the call center case, the acceptable waiting time is fairly short and, as a result, customers overflowing from one capacity planning time slot to another one can be neglected. In our case, the waiting of several days for MRI examinations is common and the planning of contract decisions has to take into account patients untreated overflowing from one day to the next. This makes the contract decisions closely linked to CTS waiting queue control.

Note that this thesis is an extension of our preliminary work, [START_REF] Xie | Redesigning the neurovascular unit of a health care complex[END_REF], which analyzed the contract design problem by discrete event simulation and experimental design. This thesis provides an in-depth mathematical analysis of the optimal control and proposes efficient contract optimization approaches.

Introduction

Based on the observations in the hospital under study, we propose a new contract-based reservation process: the neurovascular department reserves each day some CTS to ensure the quick examination for stroke patients. RTS is still possible in case of arrival surges of stroke patients. The efficiency of the new reservation process greatly depends on two closely related decisions:

1) The contract planning decisions, i.e. the number of CTS and its distribution over time, which is related to capacity planning and allocation. The contract is characterized by an integer vector of 7-entries, each corresponding to the number of CTS for a weekday or weekend and the same contract is applied for different weeks;

2) The patient assignment policy for assigning incoming patients to either CTS or RTS, which is a decision to be made at the real time level, i.e. each day.

Chapter 3 Contract planning and patient assignment control policy This problem is difficult as it involves simultaneously two decisions at different levels, the contract at the tactical level with decisions in discrete integer space and the optimal control policy at the real-time level. A stochastic programming model is proposed to solve this problem. In order to solve this model, the optimal control policy is firstly identified for any given contract. Then Monte Carlo approximation and local search are used to determine the contract decisions. Finally, an improved implementation method is proposed in order to avoid the "unlucky" patients who are assigned to RTS with long waiting times.

The rest of this chapter is organized as follows. The problem formulation is described in Section 3.2. Section 3.3 proposes an average cost MDP model for exploring the structure properties of the optimal control policy for any given contract. Contract optimization is addressed in Section 3.4. Section 3.5 presents computational results to show the efficiency of the proposed approach and the impact of different problem parameters on the contract decisions and the control policy. Implementation issues are discussed in Section 3.6.

Conclusions and perspectives are given in Section 3.7.

Problem formulation

A contract-based MRI examination reservation process is proposed to reduce the stroke patient waiting times. This approach is characterized with the contract decision, i.e., the number and the distribution of CTS, and patient assignment control policy which assigns patient to either CTS or RTS. The contract decisions and the control policy are related to each other. The optimal control policy depends on the contract decisions, while the control policy has an impact in the determination of CTS. An integrated decision model is proposed to determine these decisions based on the assumption 1-assumption 4.

The MRI examination reservation problem is defined by the following notation: + a tn ty t }of remaining patients will wait for CTS in the subsequent days.

Indices

Remark 3-1:

The waiting time of the stroke patients served by RTS is approximated by a contract-independent constant T R . The use of a constant T R is reasonable because (i) MRI facility is shared by all medical units of the hospital and (ii) the sensitivity analysis performed in Section 3.5 shows that the optimal contract is quite insensitive to the change of T R .

Remark 3-2:

No constraint on the number of CTS is made in this thesis. The contract determined this way best reflects the demands of the neurovascular department. Nevertheless, all results of this paper still hold under constraints about the maximum number of CTS for each week and each day.

Under Assumption 4, the control policy will be proved stationary over weeks, i.e. f t+7 (.) = f t (.), in the next section.

Under the above assumptions, the MRI examination reservation problem can be formally stated by the following stochastic programming model:

Chapter 3 Contract planning and patient assignment control policy Model 3-1:

( ) ( ) 1 , 1 1 E lim T R t t t t t T f t MIN T y x c n x a T + - →∞ = ⎡ ⎤ + + - - ⎢ ⎥ ⎣ ⎦ ∑ n (3.1)
Subject to:

( )

1 1 t t t t t t y f x a x a - - = + ≤ + (3.2)
( )

1 t t t t t x x a y n + - = + -- (3.3) ( ) 7 1 2 7
, ,..., , : .

t n n n IN f IN IN ∈ → (3.4)
where ( )

if 0 0 else ξ ξ ξ + ≥ ⎧ = ⎨ ⎩ .
In this formulation, the criteria contain three terms: the first two terms are respectively the average delays of patients using RTS and CTS, and the last term corresponds to the average penalty cost of unused CTS. Constraint (3.2) defines the control policy for use of RTS. Constraint (3.3) updates the number of patients in CTS queue. This model is quite difficult to solve because it contains some unknown f t (x t-1 + a t ). To identify this function, the optimal control policy f must be established. In the following, we first investigate the structure properties of the optimal control policy and then proposed an optimization method for determining the contract decisions.

Structure properties of the optimal control policy

This section considers the optimal patient assignment policy for the average cost MDP under any given contract n. The structure properties of the average cost MDP are established via discounted cost MDP. Let z t = x t-1 + a t denote the state variable, which is the CTS queue length after patient arrivals. History-dependent policies are considered in this chapter. Let h t = (z i , x i , …, z t-1 , x t-1 , z t ) be the full history by stating from initial state z i at the beginning of day i. For ease of notation, we equivalently choose the CTS queue length at the end of each day as the control variable. The patient assignment policy is denoted as π={π 1 ,π 2 ,...} where the CTS queue length at the end of day

+ + ⎡ ⎤ = - + + - - ⎢ ⎥ ⎣ ⎦ (3.6)
In the following, when no confusion is possible, g d(t) (.) and ( )

d t
n are written as g t (.) and t n for convenience.

Theorem 3-1:

There exists an optimal average cost policy such that t x x ≤ for all t > 0 with

( ) * R x T c n ⎡ ⎤ = + ⎢
⎥ where n* = MAX {n 1 , …, n 7 } and X ⎡ ⎤ ⎢ ⎥ is the least integer greater or equal to X.

Proof: Without loss of generality, assume that the system starts from state z in day i = 1. Let (x t , ∀t=1, 2,…) be an optimal control policy. By optimality of (x t ), ( )

' t
x is also optimal and the Theorem holds if

( ) ( ) ( ) ( ) ( )
( ) ( ) 1 1 Q T R T j j G T T T = Φ = - ∑ (3.8)
where Q(T) is the total number of marked patients by day T and G j (T) is the cost incurred by j-th marked patient till day T including waiting time in the marked patient queue plus eventually a cost of T R if is served by RTS or the cost of -c if it is served by CTS.

From (3.8),

( ) ( ) ( ) ( ) ( ) ( ) 1 1 R Q T T R R R T j j G T T Q T Q T T T T - = ⎛ ⎞ ⎜ ⎟ Φ ≥ - - - - ⎜ ⎟ ⎝ ⎠ ∑ By definition Q(T) -Q(T-T R
) is upper bounded by the number of patients arrived in the last T R days and is hence finite. As a result, (Q(T) -Q(T-T R ))/T tends to 0 as T increases. As a result, relation (3.7) holds and the proof is completed if G j (T) -T R ≥ 0 for all j ≤ Q(T-T R ).

Three cases are possible. Case 1: marked patient j is not yet served till day T and hence has been waiting for at least T R days, which implies G j (T) -T R ≥ 0. Case 2: marked patient j has been assigned to RTS and by definition, G j (T) -T R ≥ 0. Case 3: marked patient j has been served by a CTS. Note that marked patient j arrives in a day t such that ' t x x = and will be served by a CTS in day τ such that ' 0 x τ = . As a result, marked patient j waits at least / * x n days. Hence, ( )

/ * 0 R R j G T T x n c T - ≥ -- ≥ .
Q.E.D

Due to Theorem 3-1, we can make the following assumption without loss of generality.

Assumption 3-A1: t x x ≤ for all t > 0.

Discounted cost problem

According to relation (3.5), the corresponding α-discounted cost MDP is defined as follows:

( ) ( ) , ( ) , lim , T t i d t t t i T t i J i z E g z x z z α π α - →∞ = ⎡ ⎤ = = ⎢ ⎥ ⎣ ⎦ ∑ (3.9)
for any given initial state z i = z with i = 1, …7 with discount factor α such that 0 < α < 1.

Consider the following optimal cost function

( ) ( ) , , , V i z MIN J i z α α π π =
In the remaining, for simplicity, the notation α is omitted in this subsection where only discounted cost problem with a given α is considered. Theorem 6.10.4 in Puterman (1994) is used to establish the optimality equation. It will be shown in the following Remark 3-3 that all conditions needed for application of Theorem 6.10.4 are satisfied. Since the set of states (i, z) is countable and the control constraint set is finite as x t ≤ z t for each z t , Theorem 6.10.4 in [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF] implies that the optimal cost function is the unique solution of the following optimality equation:

( ) ( ) ( ) ( ) ( ) ( ) 0 1, , min , 1,..., 7 1, i R i i x z n x i a a c n z x T z n x V i z i P V i x a α + + + ≤ ≤ - ∧ + ⎧ ⎫ - + + -- ⎪ ⎪ = ∀ = ⎨ ⎬ + + + ⎪ ⎪ ⎩ ⎭ ∑ (3.10)
where min( , ) x y

x y ∧ =

. The optimal control policy is given by the argument x that reaches the minimum in (3.10) and the optimal cost function is the limiting function of the following value iteration:

( ) ( ) ( ) ( ) ( ) ( ) 1 1, 0 min t t t t R t t t t t t t t t a t x z n x a V z c n z x T z n x P V x a α + + + + + ≤ ≤ - ∧ ⎧ ⎫ = - + + -- + + ⎨ ⎬ ⎩ ⎭ ∑ (3.11) ( ) 0 0 V z = (3.12) for t = 0, -1, - 2
, lim

n i n V i z V z -+ →∞ = (3.13)
Relation (3.11) can be rewritten as

( ) ( ) ( ) ( ) ( ) ( ) ( ) { } 1 0 min 1 t t t t R t R t t t t t t t x z n x V z c n z T z n U x T x + + + + ≤ ≤ - ∧ = - + - + - - (3.14)
where ( ) ( )

1 1 1, t t t t a t a U x P V x a α + + + = + ∑ (3.15)
Similarly, optimality equation (3.10) can be put in similar form.

( ) ( ) ( ) ( ) ( ) ( ) ( ) { } 0 , min 1, 1 , 1,..., 7 i R R i i x z n x V i z c n z T z n U i x T x i + + + ≤ ≤ - ∧ = - + - + + - - ∀ = (3.16) where ( ) ( ) 1, 1, 1, i a a U i x P V i x a α + + = + + ∑ (3.17)
Chapter 3 Contract planning and patient assignment control policy Remark 3-3: From Theorem 6.10.4 of [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF], the optimality equations (3.10) actually has a unique solution as Assumption 6.10. 1 and condition (6.10.11) of [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF]

hold with g t (z t , x t ) ≤ w(z t ) ≡ cn* + T R z t and ( ) [ ] ( ) 1, 1 * * * * R R R R R i a t t t t t a

P w x a cn T x T E a cn T z T a w z T a

+ + + ≤ + + ≤ + + = + ∑ where n* = MAX{n 1 , …, n 7 }, a* = MAX{E[a 1 ], …, E[a 7 ]}.
Property 3-1: In the value iteration by (3.11) or equivalently by (3.14), the optimal x t is nondecreasing in z t .

Proof: Denote 1 t x and 2 t x as the optimal x t for ( )

1 t t V z + and ( ) t t V z . From relation (3.14), ( ) ( ) 1 0 ( 1 ) ( ) 1 t t t t t x z n x z n x + + ≤ ≤ + - ∧ ≤ - + ∧ ( ) 2 0 ( ) t t t x z n x + ≤ ≤ - ∧ Therefore, 1 t x is equal to either 2 t x or ( ) 1 t t z n + - + and hence 1 2 t t
x x ≥ . This completes the proof.

Property 3-2:

In the value iteration by (3.11) or equivalently by (3.14), -c≤V t (z t +1)-V t (z t )≤T R , for any t z and t.

Proof:

The proof is made by induction. First the property is clearly true for t = 0. Assume that the property holds for t+1 and we prove that it also holds for t. Let 1 t x and 2 t x as the optimal t

x for ( )

1 t t V z + and ( ) t t V z .
From Property 3-1, 1

( ) ( ) ( ) ( ) ( ) 2 2 12 1 1 1 t R t t t t t t t t t V z c n z x T z n x U x + + + + ≤ --+ + + - - + By definition, ( ) ( ) ( ) ( ) ( ) 2 2 12 t R t t t t t t t t t V z c n z x T z n x U x + + + = - + + - - +
Combining the two relations,

( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 t t R R R t t t t t t t t t t V z V z c n z c n z T z n T z n T + + + + + - ≤ --- - + + - - - ≤
Three cases are considered for the proof of the first inequality of this Property.

Case: 1 0 From (3.14), there is no unused CTS for both ( ) 1 1

t t z n + -≤ . In this case, 1 2 0 t t x x = = . As a result, ( ) ( ) ( ) 1 1 1 0 t t t t t V z c n z U + + = --+ ( ) ( ) ( ) 1 0 t t t t t V z c n z U + = -+ ( ) ( ) 1 t t t t V z V z c + - =- Case: 1 0 t t z n + -> and ( ) 1 0 1 t t t x z n x < < + -∧ .
1 t t V z + and ( ) t t V z and 2 1 t t x x = . Hence, ( ) ( ) ( ) ( ) 1 1 11 1 1 t R t t t t t t t V z x T z n x U x + + = + + -- + ( ) ( ) ( ) ( ) 1 1 11 t R t t t t t t t V z x T z n x U x + = + -- + ( ) ( ) 1 t t R t t V z V z T c + - = ≥- Case: 1 0 t t z n + -> and
t t t
x z n = + -. From (3.14), there is no unused CTS for both ( )

1 t t V z + and ( ) t t V z . Hence, ( ) ( ) 1 1 1 1 t t t t t V z x U x + + = + Take 1 1 t
xas the feasible control policy for ( )

t t V z , ( ) ( ) 1 1 1 1 1 t t t t t V z x U x + ≤ -+ -
Combining the two relations with (3.15),

( ) ( ) ( ) ( ) ( ) 1 1 1 1 1, 1 1 1 t t t t t t t a t t a V z V z P V x a V x a α + + + + - ≥ + + - + -

∑

By induction assumption, ( ) ( )

1 1 1 1 1 t t t t V x a V x a c + + + - + -≥-and hence, ( ) ( ) 1 1 t t t t V z V z c c α + - ≥ -≥-. Definition: A function φ(x) : → Z R is said convex if φ(x+1) -φ(x) ≥ φ(x) -φ(x-1), for all
x.

Property 3-3: In the value iteration by (3.11) or equivalently by (3.14), ( )

t t V z is convex in t z . As a result, ( )
1 t t U x + is convex in t x .
Proof: First, the property holds for t = 0 as ( )

t t V z = 0. Assume that ( ) 1 1 t t V z + +
is convex and we prove the property for t. From (3.15), the convexity of ( )

1 1 t t V z + +
implies the convexity of ( )

1 t t U x + . Hence, ( ) ( ) 1 1 t R t t U x T x + - - is also convex. Let
Chapter 3 Contract planning and patient assignment control policy

( ) ( ) ( ) ( ) ( ) 1 0 arg min 1 t t t t R t t t x z n x L U x T x + + ≤ ≤ - ∧ = - - Equation (3.14) can be written as ( ) ( ) ( ) 1 1 1 (0) if ( ) if ( ) if t t t t t t t t t t t t t t t t R t t t t t t t t t c n z U z n V z z n U z n n z L n L T z n L U L z L n + + + ⎧ -+ ≤ ⎪ ⎪ = -+ - ≤ ≤ + ⎨ ⎪ + -- + ≥ + ⎪ ⎩ (3.18) where ( ) ( ) ( ) 1 0 arg min 1 t t R t t t x L U x T x + ≥ = - -
By convexity of ( )

1 t t U x + , ( ) t t V z is convex in t z in the following internal [0, n t ), (n t , L t +n t ),
and (L t +n t , +∞). We still need to prove the convexity of ( )

t t
V z for z t = n t and z t = L t +n t .

The convexity of ( )

t t V z at z t = n t holds as, by Property 3-2, ( ) ( ) ( ) ( ) 1 1 t t t t t t t t V z V z c V z V z + - ≥ -= - -.
The convexity of ( )

t t V z at z t = L t +n t holds as, by Property 3-2, ( ) ( ) ( ) ( ) 1 1 t t R t t t t t t V z V z T V z V z - -≤ = + - .
By induction, this completes the proof.

Theorem 3-2: The value functions V(i, z) and U(i, x) are convex functions respectively in z and x for all i = 1, …7. Further in the optimal patient assignment control policy, 1) the optimal number of patients assigned to CTS queue is

0 if 0 * if 0 if i i i i i i i z n x z n z n L L z n L -≤ ⎧ ⎪ = - ≤ -≤ ⎨ ⎪ -≥ ⎩ (3.19) where ( ) ( ) ( ) 0 arg min 1, 1 i R i i i x L U i x T x ≥ = + - - .
2) The optimal number of patients assigned to RTS is ( ) ( )

* i i y z n L + + = - - .
Proof: The theorem is a direct consequence of relations (3.13), (3.16)-(3.17) and Property 3-3. Q.E.D

Average cost problem

In this subsection the optimality equation and the form of the optimal control policy will be established via the α-discounted problem.

Even through x t is bounded from Assumption 3-A1, z t = x t-1 + a t can be unbounded. For the sake of readability, we first consider the case of bounded z t and then establish properties of optimal control for the unbounded case.

Bounded patient arrival

( ) ( ) max max 0 , * R R t t t t t g z x cn T z n cn T z ≤ ≤ + - ≤ + .
Property 3-4: Under Assumption 4, Assumption 3-A1, and 3-A2, there exists Γ > 0 such that ( ) ( )

, 7,0 V i z V α α - ≤Γ, for all i = 1, …, 7
and for all z.

Proof: From Property 3-2, ( ) ( )

1 t t R c V z V z T α α -≤ + - ≤
which, together with 0 ≤ z ≤ z max implies, for all z and z',

( ) ( ) max max ' t t R cz V z V z T z α α - ≤ - ≤
Combining with (3.13),

( ) ( ) max max , , ' Cz V i z V i z Cz α α - ≤ - ≤ (3.20) Where max( , ) R C T c =
This establish the property for i = 7. Consider now the case i = 1, …6. From the optimality equations (3.10) and let π be the optimal control policy,

( ) ( ) ( ) ( ) 1, , ( , ) 1, , 1,.
.., 7 i i a a V i z g z z P V i z a i α α π α π + = + + + ∀ = ∑ where ( ) ( ) ( , ) R i i i g z x c n z x T z n x + + = - + + -- .
From the words following Assumption 3-A2,, ( , )

i g z x B ≤ with max * R B cn T z = + . As a result, ( ) ( ) ( ) 1, , 1, , 1,.
.., 7 i a a V i z B P V i z a i α α π + ≤ + + + ∀ = ∑ 32
Chapter 3 Contract planning and patient assignment control policy Repeat the above relations for t subsequent days leads to:

( ) ( ) ( , ),( , ') ' , ,' i z t i z z V i z tB Q V t i z π α α + ≤ + + ∑ (3.21)
where ( , ),( , ')

i z t i z Q π +
is the probability of reaching state z' at the beginning of day t+i by starting from state z at day i under policy π. Combining (3.20) and(3.21) with t+i= 7, ( ) ( ) ( )

( , ),(7, ') max ' , 6 7, ' 6 7, 0 i z z z V i z B Q V z B V Cz π α α α ≤ + ≤ + + ∑ Similarly, ( ) ( ) ( ) (7,0),(7 , ') max ' 7, 0 6 , ' 6 , i z z V B Q V i z B V i z Cz π α α α + ≤ + ≤ + + ∑
The above two properties concludes the proof.

Theorem 3-3. Under Assumption 4, Assumptions 3-A1, and 3-A2, there exists an optimal stationary control policy, the same with that in Theorem 3-2, for the average cost model (3.5). Further the optimal average cost is independent of the initial state (i, z).

Proof. From Proposition 4.2.6 in [START_REF] Bertsekas | Dynamic Programming And Optimal Control[END_REF] and Property 3-4, the optimal average cost per day exists and has the same value λ for all initial states, and λ satisfies ( ) ( )

1 lim 1 , V i z α α λ α → = - (3.22)
The differential cost functions

( ) ( ) ( ) ( ) 1 , lim , 0,0 i z V i z V α α α ψ → = - (3.23)
satisfy the following optimality equations:

( ) ( ) ( ) ( ) ( ) ( ) { } 0 ( ) , min 1, 1 , 1,..., 7 i R R i i x z n x i z c n z T z n H i x T x i λ ψ + + + ≤ ≤ - ∧ + = - + - + + - - ∀ = (3.24) ( ) ( ) , , , i a a H i x P i x a α ψ = + ∑ (3.25)
Further, the optimal control policy is defined by the argument x that reaches the minimum in (3.24)- (3.25). From Property 3-3, equations (3.13) and (3.23),

ψ(i, z) is convex in z and H(i,
x) is convex in x for all i = 1, …, 7. This implies that the optimal control policy for the average cost problem is of the form (3.19).

Q.E.D.

Unbounded patient arrival

In this subsection, assumption 3-A2 is relaxed.

Theorem 3-4. Under Assumptions 4 and 3-A1, (a) there exists a constant λ satisfying (3.22) for all (i, z), a matrix ψ (i, z) satisfying (3.24)-(3.25), (b) the optimal control policy is defined by the argument x that reaches the minimum in (3.24)-(3.25), (c) there exists an optimal stationary control policy of the form of equation (3.19) for the average cost model (3.5).

Proof:

The proof is based on Theorem 8.10.7 of [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF] and the conditions that need to be checked are the following ones:

C1: For each state (i, z), the stage cost is such that -∞ < R ≤ g i (z, x i ) < ∞.
C2: For each (i, z) and α < 1, ( ) Let us now prove conditions C1-C4.

, V i z α < ∞ . C3: There exists ϕ > -∞ such that, for each (i, z), ( ) ( ) ( ) , , 7, 0 , 1. i z V i z V α α α ψ ϕ α ≡ - ≥ ∀ < C4: There exists a non-negative function W(i, z) such that a) W(i, z) < ∞; b) for each (i, z), ( ) ( ) , , , 1 i z W i z α ψ α ≤ ∀ < ; and c) for each (i, z) and x i , ( ) 1, 1, .
Condition C1 clearly holds as g i (z, x i ) ≥ 0.

Condition C2 holds as well as

(i) by Assumption 3-A1, 1 t x x -≤ and 1 t t t t z x a x a - ≤ + ≤ + ; (ii) ( ) , * , R i i i g z x cn T z ≤ + ( ) ( ) , * * * R R t t t t E g z x E cn T z cn T x a ⎡ ⎤ ≤ + ≤ + + ⎡ ⎤ ⎣ ⎦ ⎣ ⎦ ; (iii) ( ) ( ) ( ) , * * * . 1 R R V i z cn T z cn T x a α α α ≤ + + + + -

Condition C3 holds as

Chapter 3 Contract planning and patient assignment control policy (i) by

, ( ) ( ) , 1 , R c V i z V i z T α α -≤ + - ≤ ;
(ii) by Assumption 3-A1 and Theorem 3-2, the control threshold i L x ≤ .

(iii) by relations (3.18) and (3.13), ( )

, V i z α is increasing for z ≥ L i + n i ; (iv) By (i)-(iii), ( ) ( ) ( ) * * , , ' R C T n n V i z V i z α α - + ≤ - with C = max(c, T R ); (v) ( ) [ ] ( ) 1 (7,0),(7 , ') 1 1 ' 7, 0 * , ' i s R i z s z V i c n T E a Q V i z π α τ α τ - + = = ≤ + + ∑∑ ∑ where ( , ),( , ') i z t i z Q π +
is the probability of reaching state z' at the beginning of day t+i by starting from state z at day i under policy π.

(vi) Combining with (iv), ( )

( ) ( ) ( ) 2 7, 0 * * * , * * R R V i c n T i a ia V i z C T n n α α ≤ + + + + + which proves C3.
Condition C4 holds as (i) By starting from state (i, z), the average stage cost of any period t is bounded from above by

[ ] ( ) 1 * * * t R R i cn T z E a cn T z ta τ τ + = ⎛ ⎞ + + ≤ + + ⎜ ⎟ ⎝ ⎠ ∑ . (ii) From (i), ( ) ( ) ( ) ( ) 1
( , ),( , ') 0 ' , * * , '; t R i z i t z z V i z cn T z a Q V i t z π α α τ τ - + = ≤ + + + + ∑ ∑ . (iii) Combing (ii) with i+t = 7 and Property 3-2, ( ) ( ) [ ] 7 , 6 * 6 36 * 7,0 R R R V i z cn T z T a V T E z α α ≤ + + + + ; (iv) Combining (iii) with [ ] [ ] 7 7 6 * i E z z E a z a τ τ = ≤ + ≤ + ∑ leads to ( ) ( ) , , i z W i z α ψ ≤ with ( ) , 7 6 * 42 * R R W i z T z cn T a ≤ + +
. Condition C4.a-C4.c clearly holds. This proves C4.

Q.E.D.

In the following, we will restrict us to threshold policies and denote each policy by its threshold vector L.

Assumption 3-A3: For each day i = 1, …7, the probability of no patient arrival is non null, i.e. P i0 ≥ δ, for some δ > 0.

Remark 3-4: Assumption 3-A3 is not restrictive in this chapter. If number of patient arrivals of a day i is at least one, i.e. a i ≥1, there will be at least one CTS for day i in the optimal contract n, i.e. n i ≥1. Further, the contract n' with n' i = n i -1 and n' j = n j , for all j ≠i is the optimal contract for patient arrivals a' with a' i = a i -1 and a' j = a j . The reverse is also true.

Property 3-5: Under Assumption 4, Assumptions 3-A1, and 3-A3, for any stationary control policy L, i.e. L(t) = L(t+7), the underlying stochastic process (d(t), z t ) and (d(t), x t ) are Markov chains with a unique positive recurrent class including all states (i, 0) for i = 1, …, 7.

Proof: Under the assumptions of the Property, it is clear that (d(t), x t ) is a finite state Markov chain and (d(t), z t ) is a Markov chain. This property obviously holds for the case n = 0 and we assume n ≠ 0, i.e. n* > 0, in the following. Starting from any initial state (i, x),

for any control policy L, any state (d(t), x t ) = (i, 0) can be reached in at most 7 6

R T + days with probability 7 6 R T δ + as x x
≤ . As a result, (d(t), x t ) is a finite state Markov chain with a unique positive recurrent class including all states (i, 0). Since z t = x t-1 + a t , Assumption 3-A1 and the property of a t imply that (d(t), z t ) is a Markov chain with a unique positive recurrent class including all states (i, 0).

Computation and implementation of the optimal control policy

From Theorems 3-3 and 3-4, the average-cost MDP problem has the same optimal control policy with the discounted-cost MDP. Further, the optimal control policy for a given contract n can be determined by solving optimality equations (3.24)- (3.25). This can be either done either by value iteration or the linear program [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF]). The linear program (LP) model is as follows:

Model 3-2:

F n =Maximize λ subject to ( ) ( ) ( ) ( ) ( ) ( ) , , 1 , , , , 1,
..., 7

R i i i a a i i z c n z x T z n x P i x a z x z n x i λ ψ α ψ + + + + ≤ - + + -- + + + ∀ ∀ ≤ - ∧ ∀ = ∑
F n is the optimal average cost and, for each state (i, z), the optimal control is given by x reaching equality in the above relations. Further, the optimal control policy is characterized Chapter 3 Contract planning and patient assignment control policy by a control threshold vector L with one threshold for each day. From relation

( ) ( ) min , i i x L z n + = -
, L can be easily determined.

The existence of optimal threshold control makes the implementation easy. According to the relation (3.19), the implementation of the L control policy can be divided into three cases, as shown in Fig. 3.1-3.3:

Case 1: If z t , CTS queue after new patients' arrival, is smaller than n t , the number of CTS in the same day, then there exists the number n t -z t of unused CTS and there are no patients waiting for the future examinations.

FIG.

Contract optimization

In this Section, we propose a two-step approach for optimization of the contract n. First a Monte Carlo approximation approach is used to identify an initial contract. This contract is further improved with a local optimization.

Monte Carlo approximation

The contract optimization problem stated in (3.1)- (3.4) is still difficult to solve as it involves integer variables and random demands. The structure properties of the optimal control policies of Theorems 3-2 and 3-3 lead to the following equivalent reformulation of Model 3-1, i.e., relation (3.1)-(3.4):

Model 3-3: (3.26) subject to:

( ) ( ) * , 1 , 1 1 E lim T R t t t t d t T t F MIN F T y x c n x a T + - →∞ = ⎡ ⎤ ⎛ ⎞ ≡ ≡ + + - - ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ ∑ n L n L
( ) ( ) ( )
i i n = > Π ∑ with [ ] 7 1 R i i T c E a c = + Π = ∑ cannot be optimal.
Proof: First, for the contract n with n i = 0, all patients are sent to RTS and hence:

[ ] 7 1 0,0 7 i R i E a F T = = ∑ . For any other contract n, [ ] 7 7 1 1 , 7 i i i i n E a F c = = - ≥ ∑ ∑ n L
The combination of the above two relations completes the proof.

Q.E.D.

To simplify the problem, we convert the Model 3-3, i.e., equation (3.26)-( 3.29) into a deterministic optimization problem by using a single given but long enough patient arrival sample path a = (a 1 , a 2 ,…, a T ). This together with Theorem 3-1 and 3-5 leads to the following Monte Carlo approximation:

( ) ( ) ( ) ( ) ( ) , , ( ) 1 , 1 ;
/ T R T T t t d t t t T t F MIN F T y x c n x a K x T + - = ⎛ ⎞ ≡ ≡ + + - - + ⎜ ⎟ ⎝ ⎠ ∑ n L n L a a n (3.30) subject to: (3.27)-(3.29), n i ≤ Π, L i ≤ (T R +c)Π where K(.)
is the total waiting time of patients in the CTS queue remaining at the end of the horizon T.

Theorem 3-6: With probability 1, F T (a) converges to F* when T goes to infinity.

Proof: From Theorem 3-1 and Theorem 3-5, conditions n i ≤ Π and L i ≤ (T R +c)Π do not exclude any optimal contract and optimal control policy. For the contract n = 0,

( ) ( ) ,0, ,0, T T F F ≥ L 0 a a , F 0L ≥ F 00 and ( ) ( ) [ ] 7 ,0,0 0,0 1 1 lim lim / / 7 T R R T t i T T t i F Ta T TEa F →∞ →∞ = = ⎛ ⎞ = = = ⎜ ⎟ ⎝ ⎠ ∑ ∑ a
As a result, we only need to show the convergence of ( ) , T F n,L a for each (n, L) with n ≠ 0.

From Property 3-5, (d(t), x t ) forms a finite state Markov chain with unique positive recurrent class including [START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF]0) which implies that (d(t), x t ) is a regenerative process with (7, 0) as a regeneration point. Hence, ( ) ( )

( ) 1 , 1 lim / T R t t d t t t T t T y x c n x a T F + - →∞ = + + - - = ∑ n L , with probability 1. Since L i ≤(T R +c)Π, x T ≤(T R +c)Π. Since n ≠ 0, ( ) ( ) ( ) ( ) ( ) 1 ; 7 7 1 / 2 7 1 / 2 T R R T T T j x K x j x x T c T c = ≤ = + ≤ + Π + Π + ∑ n which implies ( ) , T
F n,L a converges to F n,L as T goes to infinity. Q.E.D.

The above Monte Carlo optimization problem is still difficult to solve due to the non linear constraint (3.27) related to the control policy. We further omit this constraint and consider the following relaxed Monte Carlo optimization problem: Model 3-4:

1 1 1 ( ) min / T TD T R t t t t t t LB T y x c u T + = = = ⎛ ⎞ = + + ⎜ ⎟ ⎝ ⎠ ∑ ∑ ∑ a (3.31) subject to ( ) 1 ( ) 1,..., t t t t u n a x t T + - = -+ ∀ = (3.32) 1 ( ) 1,..., t t t t t t x x a y n u t T - = + --- ∀ = (3.33) ( ) 1 1,..., t t t u n x t T T D + - = - ∀ = + + (3.34) 1 ( ) 1,..., t t t t x x n u t T T D - = -- ∀ = + + (3.35) x t , y t , u t , n t ∈IN, ∀t = 1, …, T+D (3.36)
where t u denotes the number of unused CTS used in day t, D is the extra days introduced to determine the waiting times of patients remaining at the end of time horizon T. As x T ≤(T R +c)Π for any optimal control policy, we can set D = 7(T R +c)Π.

This formulation provides a lower bound of the Monte Carlo optimization problem (3.30) as any feasible solution of problem (3.30) corresponds to a feasible solution of the above problem. Further the decision variable y t is determined with the full knowledge of the demand, both past demand and future demand. This contradicts the requirement of the socalled non-anticipativeness of any feasible control policy. However, we expect that the contract determined by this relaxed Monte Carlo approximation is a good contract. This statement will be confirmed by our numerous numerical experiments. From Theorem 3-6, LB(a) becomes a lower bound of the optimal average cost when the sample path a is longer enough.

The two nonlinear constraints (3.32) As a result, Model 3-4 can be equivalently defined as follows.

Model 3-5:

1 1 1 ( ) min / T TD T R t t t t t t LB T y x c u T + = = = ⎛ ⎞ = + + ⎜ ⎟ ⎝ ⎠ ∑ ∑ ∑ a Subject to
D x x u n t T T D - - - - + ≥ - ∀ = - + -= - ∀ = + ≥ ∀ = + + - -= - ∀ = + + x t , y t , u t , n t ∈IN, ∀t = 1, …, T+D
We further show that integrity constraints of variables x t , y t , u t can be relaxed. This greatly reduces the computation effort for solving LB(a) which contains only seven integer variables for contract n.

Property 3-6 (Ghouila-Houri (1962)

). An m*n matrix A is total unimodular if and only if for every {1,..., }

C n ⊆ there exists a partition (C 1 , C 2 ) of C such that 1 2 1 ij ij j C j C a a ∈ ∈ - ≤ ∑ ∑ for i=1,….m.
Theorem 3-7. The constraint matrix of the left hand side terms of the constraints of Model 3-5 is total unimodular. As a result, the integrity constraints of variables x t , y t , u t can be relaxed.

Proof: From Property 3-6, it is enough to prove that, for any subset C of variables x t , y t , u t , the condition of Property 3-6 holds. This is established by the following partition. All variables x t ∈C belong to set C 1 . For every t, variables y t , u t ∈C are partitioned as follows:

• y t ∈C 1 , if x t-1 ∈C, u t ∉C • y t , u t ∈C 2 , if x t-1 ∈C, u t ∈C • y t ∈C 2 , if x t-1 ∉C, u t ∉C • y t , u t ∈ C 1 , if x t-1 ∉C, u t ∈C. Q.E.D.

Improvement of the contract by local search

Starting from the contract obtained from the solution of Model 3-5, this subsection presents a local search approach to further improve the contract.

The following notation is needed:

• F n : optimal average cost under contract n, i.e.

,

F MIN F ≡ n n L L
. F n and the related optimal control policy L(n) can be determined by solving Model 3-2;

• F n,L (a): average cost of policy L under contract n and sample path a estimated by relation (3.30). Note that compared with relation (3.30), index T is omitted for simplicity;

• e i : a seven dimension vector with i-th entry equal to 1 and all other entries equal to 0. By definition, LB(a) ≤ F n,L (a).

The local search starts from the contract n determined by the Monte Carlo approximation. It then iteratively improves this contract. At each iteration, it determines the best neighbor solution among the set of contracts: n + e k (add one time slot in day k), ne k (remove one time slot in day k), ne k + e j (move one time slot from day k to day j). This process repeats until no improvement can be found.

The overall algorithm for the contract optimization is summarized as follows:

Algorithm 1 (Contract optimization)

1. Generate a long enough sample path a of patient arrivals; 2. Solve Model 3-5, the relaxed Monte Carlo approximation problem to determine LB(a)

and an initial contract n0;

3. Determine the optimal control policy L(n0) and the optimal average cost F n0 under contract n0 by solving Model 3-2; 8. The final contract is n* and the final control policy is L(n * ).

For high demand case with high patient arrival rate, the state space is large and solving the optimality relations (3.24)-(3.25) for determining F n is time consuming. In order to reduce the computation burden, F n,L(n*) (a) where a is the sample path of Step 1 can be used to replace F n in step 5. This leads to Algorithm 2. Note that the contract n' selected in each iteration is still evaluated exactly in Algorithm 2.

To summarize, the solution strategies for contract optimization are summarized as follows:

1) Generating a long enough sample path a of patient arrivals, the relaxed Monte Carlo approximation model (Model 3-5) is solved to determine LB(a) and an initial contract n0;

2) Based on this n0, local optimization 1 or 2 is used to improve the contracts (n * is the final contract), determine the final control policy L(n*), and obtain the exact average cost F n* .

To evaluate the performance of this solution strategy, the global optimal contract and control policies can also be determined by exhaustive search by comparing F n for all n in a certain range containing the optimal solution. The global optimal solution is recorded as F* = MIN{F n : ∀n}. This is possible when the demand is low but too time consuming to obtain when the demand is high.

Remark 3-6: Although the Monte Carlo approximation and relaxations are used for determination of the contract decisions, all our algorithms use MDP to find the exact criterion value of the resulting contracts. Further, both Algorithms 1 and 2 start with the same contract provided by the solution of the same model, i.e., Model 3-5.

Computational results

This section presents numerical experiments performed to evaluate the performance of the solution strategies and to investigate how the contract and control policies depend on problem parameters. The performance of the solution strategies is given by comparing with the exact optimum F* obtained by exhaustive search for small-size problems and with F best for large-size problems, where F best is the best solution of all independent runs of Algorithms 1 and 2 for the same problem instance. We then perform sensitivity analysis to show how the optimal contract depends on different factors such as average RTS delay T R and unused CTS penalty c, patient arrival patterns and patient arrival rates. All numerical results are performed on a Pentium® 4 PC running at 3.21 GHz with 1.0 GB RAM. LP models are solved by the CPLEX 11 solver.

Numerical experiments

We first describe the base case corresponding to our real case study. From the data collected from the neurovascular department under study, the average numbers of patient arrivals during the week are as follows: {1, 0.89, 0.95, 1.16, 1.53, 0.16, 0.05}. The number of patients arrived each day is assumed to follow a Poisson distribution. The average waiting time for RTS is in the range of 30~40 days with an average of T R = 35 days. The weight, c, is set to 15. These data define the base case shown in Table 3 The above base case is then modified to investigate the impact of parameters average RTS delay T R and unused CTS penalty c, patient arrival pattern and patient arrival rate. More precisely, the following numerical experiments are considered:

• Case 1: base case but with different weighing factor c ∈ {1, 5, 10, 15, 20} (impact of unused CTS penalty, c);

• Case 2: base case but with different delay for RTS T R ∈ {25, 30, 35, 40, 45} (impact of average RTS delay, T R );

• Case 3: base case but with different patient arrival patterns (impact of patient arrival pattern). The peak demand of the base case occurs on Friday. To see the impact of the patient arrival patterns on the contract and control policy, we interchange the demand in Friday and the demand of another weekday. We also consider the case of stationary demand for all weekdays.

• Case 4: base case but with different patient arrival rate (impact of patient arrival rate).

The base case is considered as low demand case. Two other case termed medium and high demand instances are derived from the base case by multiplying the patient arrival rate by 5 and 10 respectively.

The For every problem instance, 10 independent patient arrival sample paths a are generated, Algorithms 1-2 are run using each sample path to investigate the performance of these two algorithms.

Performances of the proposed algorithms and impact of average RTS delay T R and unused CTS penalty c

This subsection considers Cases 1-2 to investigate the performances of Algorithms 1-2 and to show the impact of average RTS delay T R and unused CTS penalty c. The patient arrival rate is very low and exhaustive search of optimal contract can be done in acceptable time.

The exhaustive search is performed for all contract n with n i ∈{0, 1, 2, 3}. The range was selected based on observation of different contracts provided by the proposed two-step approaches Algorithms 1-2. The optimal control policy and the average cost F n of each contract are determined by solving the Model 3-2. The cost of the resulting optimal contract is denoted as F*.

Table 3.2 summarizes optimal solutions given by exhaustive search. First note that the exhaustive search takes more the 2.5 hour for each instance. The total number of CTS decreases and the criterion value increases when the weight factor c of unused CTS increases. The contracts and control policy are sensitive to the change of c. With the increase of T R , the objective criterion F* increases and the control threshold L i increases, but contracts do not change. This means that the optimal contract is insensitive to change of T R . 2 1 2 2 2 1 0 22 22 22 21 21 21 22 35 5 2.484 9249 1 1 1 2 2 1 0 13 14 14 13 13 12 13 35 10 3.589 9225 1 1 1 1 3 0 Table 3.3 shows the impact of T R and c on average delay (Delay), percentages of unused CTS (Unused CTS Ratio) and percentages of patients using RTS (RTS Perc.) with the optimal contracts and control policies. When c decreases, the corresponding waiting time decreases while the unused CTS ratio increases. Therefore, the choice of c allows balancing between the average waiting time and the unused CTS ratio. There is no obvious trend in the change of RTS percentage. However, as the contract is insensitive to the change of T R , these performance measures are also insensitive to the change of T R . 35 15 [4.501,4.501,4.501] [4.501,4.557,5.056] [0,0,0] [0, 1.11,10.98] [0,0.7,1] [0, 1.3,3] 191 27

T R c F* CPU Time (s) n 1 n 2 n 3 n 4 n 5 n 6 n 7 L 1 L 2 L 3 L 4 L 5 L 6 L 7 35 1 0.945 9257
35 20 [5.410,5.410,5.410] [5.410,5.430,5.450

] [0,0,0] [0,0.37,0.73] [1,1,1] [0,1,2] 230 15
25 15 [4.471,4.471,4.471] [4.471,4.540,4.608

] [0,0,0] [0,1.48, 2.96] [1,1,1] [0,1,2] 205 13
30 15 [4.489,4.489,4.489] [4.489,4.594,4. We now analyze the quality of the sample path lower bound LB(a). (a). As it can be seen, the quality of the lower bound becomes worse when the weighting factor c increases but it becomes tighter when T R increases.

Even though the sample path lower bound LB(a) is loose, the contract of the Monte Carlo approximation is actually close to the optimal contract and is at most two local moves away from the optimal contract in all our numerical experiments. In order to check whether Assumption 4 requiring stable weekly contract is strong, we apply Algorithm 1 to optimize bi-week contract and the related optimal control policy, i.e. for contract n and control L defined over 14 days. Numerical experiments are performed for Cases 1 and 2. The resulting bi-week contracts and the optimal criterion values remain the same as weekly contracts of Table 3.2. This implies that Assumption 4 is not really strong in these cases.

Impact of patient arrival pattern

This subsection considers Case 3 to show the impact of patient arrival pattern. Table 3.5 summarizes the optimal solutions obtained by exhaustive search for different patient arrival patterns. The row "Mon." corresponds to patient arrival pattern derived from the base case by exchanging the patient arrival rate of Monday with that of Friday (actual peak arrival).

The next four rows are defined similarly. The row "Ave." corresponds to the case of stationary arrival with the same arrival rate for all workday with the same weekly patient arrival rate. From this table, the total number of CTS of the optimal contract decisions does not change with respect to the patient arrival patterns. However, one CTS moves from Friday to the day of peak arrival and there are still 2 CTS for Friday in order to serve patient arrival during the week. In the case of stationary weekday arrival, one CTS moves from Friday to Wednesday. The control policy seems to be insensitive to the patient arrival patterns.

F n1 F n2 Gap1(%) Gap2(%) Move1 Move2 RT1(s) RT2(s)
Mon. [4.506,4.506,4.506] [4.506,4.624,5.080] [0,0,0] [0, 2.33,11.30] [0,0.9,1] [0, 1.3,2] 211 25

Tues. [4.496,4.496,4.496] [4.496,4.504,4.555] [0,0,0] [0,0.17,1.30] [0,1,2] [0, 1.6,2] 222 28

Wed. [4.487,4.487,4.487] [4.487,4.491,4.522] [0,0,0] [0,0.08,0.77] [0,1.2,2] [0, 1.7,3] 246 34

Thurs. [4.476,4.476,4.476] [4.476,4.536,5.075] [0,0,0] [0, 1.18,11.79] [0,0.7,1] [0, 1.2,2] 192 27

Fri. [4.501,4.501,4.501] [4.501,4.557,5.056] [0,0,0] [0, 1.11,10.98] [0,0.7,1] [0, 1.3,3] 191 27

Ave. [4.517,4.517,4.517] [4.517,4.567,4.999] [0,0,0] [0,1.01,9.64] [1,1,1] [0,2.1,3] 220 28 TAB 3.7 Performance of solution strategies for different patient arrival patterns

Impact of patient arrival rate

As the patient arrival rate increases, the optimal solution is hard to obtain by exhaustive search because it needs too long time to search within a large solution space. We limit ourselves to Algorithms 1 and 2 in this experiment.

Tables 3.8 and 3.9 summarize best contracts and corresponding control policies and the performances of the two algorithms for different patient arrival rates where three scenarios are considered "Low" (base case), "Medium" (patient arrival rates 5 times larger), "High" (patient arrival rates 10 times larger). "Gap1" and "Gap2" in this case are the deviation gap of F nk from F best , i.e. Gapk = (F nk -F best )/F nk where F best is the best solution of 20 solutions of the ten runs of Algorithms 1 and 2.

From these tables, Algorithm 1 is always able to find the best solutions given in Table 3.8 whatever the sample path used while the quality of the contract decisions obtained by Algorithm 2 is more sensitive to the sample path used. Move1 shows that the contract decisions obtained by Monte Carlo approximation is very close to the best contract and is at most two local moves from the best contract. This highlights the quality of contract decisions given by the Monte Carlo Approximation as 61 CTS (resp. 31 and 7 CTS) are needed for high (resp. medium and low) demand instance. Finally, Algorithm 1 becomes too slow for high demand instance while Algorithm 2 is much faster and is able to provide a good solution with a reasonable CPU time.

Implementation issues

As noticed in Section 3.5, patients directed to RTS will face significantly longer regular reservation time than patients waiting for CTS. Although the new MRI examination reservation process leads to shorter average waiting time, these "unlucky" patients directed to RTS still face long waiting time.

In order to have better waiting time distribution, this subsection proposes an improved method. The new method still makes use of contracts and patient assignment control policy. However, the patient assignment policy is replaced by an RTS reservation policy. When the CTS queue length exceeds the threshold L i , additional time slots are reserved according to the regular reservation process. However patients are not directly assigned to RTS at the same day. CTS and RTS time slots are grouped according to their day of availability and filled by patients. All patients are scheduled to both CTS and RTS in the First in First out (FIFO) order. This method is expected to reduce the longest waiting time of stroke patients and to avoid unlucky patients.

In the following of this subsection, we call the reservation process with patient assignment policy the old reservation process and the one with RTS reservation policy the new reservation process.

Arrival rate

F n1 F n2 Gap1(%) Gap2(%) Move1 Move2 RT1(s) RT2(s)
Low [4.50,4.50,4.50] [4.50,4.55,5.06] [0,0,0] [0, 1.11,10.98][0,0.7,1] [0, 1.3,3] 191 27

Medium [9.83,9.83,9.83] [9.83,9.90,10.40] [0,0,0] [0,0.64,5.50] [1,1.1,2] [0, 1.7,3] 2006 99 High [13.94,13.94,13.94] [13.94,14.00,14.10] [0,0,0] [0,0.43,1.14] [1,1.9,2] [0,2.3,4] 9913 771

Comparison of control policies

For the old reservation process, the optimal patient assignment policy for any given contract can be determined by solving Model 3-2. Further it was shown that, for a given contract n, the optimal patient assignment policy is a threshold policy and there exists a threshold L i for day i such that new incoming patients are directed to RTS when the ending CTS queue length reaches L i . The old MRI examination reservation process is as follows. During each day t is as follows, first, the queue length x t-1 of patients waiting for CTS at the end of day

T old R t t t T t J c u x T y T →∞ = ⎡ ⎤ = + + ⎣ ⎦ ∑
For the new reservation process, the structure of the optimal RTS reservation policy is unclear. Instead, we use the optimal patient assignment policy to make RTS reservation.

Both CTS and RTS time slots are grouped together and assigned to patients in a FIFO order. More specifically, during each day t, we keep track of an artificial CTS queue length x t-1 under patient assignment policy and use it to determine the number y t of RTS time slots to reserve in day t, i.e. y t = (x t-1 +a tn t -L t ) + and x t = (x t-1 +a tn ty t ) + . The real patient queue length, the number of patients waiting for a time slot, at the end of day t-1 is denoted as

- = = = = + - - - ∑ ∑ ∑ ( ) 0 1 1 R t t new new new t s s s s T s s x x a n y u - = = = + - + -

∑ ∑

As y t = 0 for all t ≤0, subtracting the two relations leads to: Remark 3-10: Condition of Property 3-11 basically assumes that patients in CTS queue of the old reservation process wait no longer than T R and a patient in the CTS queue will not be directed to RTS. The last condition holds for any optimal control policy. By relaxing the first condition, it is still possible to show that the maximal waiting time of the new reservation process does not exceed that of the old reservation process.

Proof: Consider the last patient arriving in day t in the new reservation process, i.e. the new t

x -th patient in the patient queue. Assume by contradiction that its waiting time exceeds T R . As patients are served in FIFO order in the new reservation process,

→∞ →∞ = = = ⋅ ∑ ∑ 1 1 1 1 lim lim T T new new t t T T t t x D a T T →∞ →∞ = = = ⋅ ∑ ∑
which, together with Property 3-8, concludes the proof. Q.E.D.

This property shows that, the new reservation process not only reduces the maximum waiting time by avoiding "unlucky" patients directed to longer regular reservation but also reduces the average waiting time.

Experimental results

The data are the same with Section 3.5. For each case, two scheduling methods are considered: (i) old MRI examination reservation process, denoted "Old"; (ii) new MRI examination reservation process, denoted "New". The contract is provided in the following and the optimal patient assignment policies of the old reservation process are determined by solving the LP model in Remark 3-4. The new reservation is defined with the same contract n and the same set of control thresholds L. Each reservation process is then evaluated by Monte Carlo simulation over a time horizon of 1 million weeks.

Waiting time distribution

We consider first the base case. The average weekly demand is 5.74 MRI time slots. The contract for 6 CTS is: n = (1, 1, 1, 1, 2, 0, 0). For this contract, the optimal patient assignment policy is as follows L = [START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF].

Fig. 3.6 compares the probability distribution of patient waiting times of two scheduling methods for the base case. From this figure, the waiting time in old method is distributed over the range of 0~7 days plus a high probability spike of 5% at 35 days corresponding to "unlucky" patients directed to RTS. In the new method, the distribution of patients' waiting time is much more smoothed on a range from 0 to about 20 days without "unlucky" patients having to wait for much longer time than patients arriving around the same time. The new method greatly reduces the maximal waiting time. Probability distributions of waiting time in all other cases are similar. In the following sensitivity analysis are performed with respect to different performance criteria including the average criterion value, the average delays, the variance of waiting times, and the maximal waiting times.

Impact of parameters

We now perform the sensitivity analysis with respect to cost c of unused time slots by varying c in {1, 5, 10, 15, 20}. The contract is n = (1, 1, 1, 1, 2, 0, 0). The optimal patient assignment policies are: L = [START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | A Monte Carlo optimization and dynamic programming approach for managing MRI examinations of stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF], [START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | A Monte Carlo optimization and dynamic programming approach for managing MRI examinations of stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF], [START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF], [START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF], [START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF].

Table 3.11 compares the performance of both scheduling methods. "OBJ" is the long run average criterion value, i.e. J new or J old . "Ave", "Dev" and "Max" are the average waiting time, standard deviation and maximum of the waiting times, respectively. "Gap" = (J old -J new ) / J old is the relative deviation of the criterion value of new method with respect to that of the old method. Compared with those in the old method, the performance indices in new method greatly decreases, which means that the new method improves the performances of contract-based reservation process. With the increase of c, OBJ, Ave, Dev, and Max increase. This means the value of unused CTS cost greatly affects patients' waiting time. Gap decreases from 12.3% to 3.74%, and the average delay increases from 4.04 to 4.54.

Maximal waiting time keeps nearly the same, about 26~27 days.

It seems that the new method improves more when more patients are directed to RTS. Indeed, for small c, the CTS queue length L is smaller and the improvement of the new reservation process is greater. We now perform the sensitivity analysis with respect to the average delay of regular reservation by varying T R in {25, 30, 35, 40, 45}. The contract is n = (1, 1, 1, 1, 2, 0, 0). The optimal patient assignment policies are: L = [START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | A Monte Carlo optimization and dynamic programming approach for managing MRI examinations of stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF], [START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF], [START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF], [START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF], [START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF].

Table 3.12 compares the performance of both reservation processes. The impact of T R on the performance is nearly the same with the impact of c, except the Max and Gap. As shown in Table 3.12, Max increases from 21 to 30 days, and Gap increases from 4.5% to 5.4% with the increase of T R . This means the new method is more important for longer T R .

We now perform the sensitivity analysis with respect to the patient arrival pattern. The arrival pattern has no obvious impact on the performances of the reservation processes. We now perform the sensitivity analysis with respect to the patient arrival rate. Three scenarios are considered "Low" (base case), "Medium" (patient arrival rates 5 times larger), "High" (patient arrival rates 10 times larger). The contract is n = (1, 1, 1, 1, 2, 0, 0) for the base case, five times larger for medium demand case, and ten times larger for high demand case. The optimal patient assignment policy is as follows: L = [START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF], (17, 16, 16, 17, 14, 15, 17), (27, 27, 26, 28, 22, 25, 27).

From Table 3.15, compared with old method, nearly all performance criteria decrease in the new method. With the increase of arrival rate, OBJ greatly increases, whereas Ave, Dev, and Max greatly decrease. Further, it seems that the new reservation process improves more for low demand case.

Conclusion

This chapter proposes a contract-based reservation process of MRI examinations for stroke patients in order to reduce the average waiting time of patients without degrading the utilization ratio of MRI facilities. The new method requires the determination of the number of contracted time slots and the optimal patient assignment control policy for assigning patients to either CTS or RTS. This results a stochastic combinatorial problem that combines combinatorial planning decision variables and dynamic control policies. This chapter first explores the structure properties of the optimal control policies under a given contract and then proposed a two-step approach to obtain efficient contracts. A single sample-path Monte Carlo approximation is used to determine an initial contract which is further improved through local search. Numerical results show that the deviation gap from the optimal solution is rather small which means that the contract and the corresponding control policy are very close to the optimal ones. This chapter also proposes new strategy to avoid the "unlucky patients" who are assigned to RTS. The new strategy differs from the existing one by reserving regular time slots for the neurovascular department instead for particular patients. This allows us to avoid "unlucky" patients having to wait for much longer time than other patients arriving at the same time.

Numerical results show that the new method can greatly reduce the criterion values and better the waiting time distribution.

Future research can be pursued in several directions. To reduce the unused CTS and improve the utilization ratio of MRI, one immediate extension is the development of real time control strategies for advanced cancellation of CTS in case of short CTS queue. There are several other research directions, for example, the determination of the optimal contract with non stationary patient arrival and the combination of multiple classes of patients and several examinations.

Chapter 4 Contract planning and one-day advance cancellation of contracted time slots

Introduction

Chapter 3 has proposed a contract-based MRI examination reservation process for stroke patients. The reservation process reduces stroke patients' waiting time but it also leads to unused time slots. To improve the utilization of MRI scanner, we explore the possibility of avoiding unused CTS by canceling CTS in advance when the CTS queue is short. In this way, the possible unused CTS can be released from the contract in advance and the imaging department can arrange other patients to have the examinations on these release time slots. Of course, the earlier a contracted time slot is released, the better the imaging department can make use of it. In this chapter, we limit ourselves to cancellation one day before. More specifically, the contract includes three decisions:

Contract decision, i.e., the number and distribution of CTS;

Patient assignment control policy, i.e., the control policy which assigns patient to either CTS or RTS;

One-day advance cancellation control policy. The neurovascular department can cancel part of CTS in the next day in order to reduce unused CTS when the CTS queue length at the end of some day is too short.

This chapter proposes an MDP approach to simultaneously identify the forms of the optimal patient assignment and one-day advance cancellation policies for each given contract. Then, local search is used to improve the contract decision.

The rest of this chapter is organized as follows: Section 4.2 provides a formal problem setting. Structure properties of the optimal control policies are established via discounted cost MDP in Section 4.3. Section 4.4 proposes local optimization algorithm. Section 4.5 analyzes results of computational experiments. Conclusions and perspectives are given in Section 4.6.

Problem setting

This section presents an MDP formulation to determine the optimal patient assignment policy and one-day advance CTS cancellation policy. Assumptions 1 to 4 presented in Chapter 1 are made. Further, the following assumption is made throughout the chapter:

( ) ( ) ( ) 1 1 , lim , , T i t t t i d t T t i J i z E g z x w z z T μπ + - →∞ = ⎡ ⎤ = = ⎢ ⎥ ⎣ ⎦ ∑ (4.1)
for any given initial state z i =z with i = 1, …7 where

( ) ( ) ( ) ( ) ( ) ( )

Theorem 4-1:

There exists an optimal average cost policy such that t x x ≤ for all t > 0 with

( ) * R x T c n ⎡ ⎤ = + ⎢ ⎥ where n* = MAX{n 1 , …, n 7 }.
Proof: This proof is similar with Theorem 3-1. Q.E.D.

Thanks to Theorem 4-1, we can make without loss of generality the following assumption:

Assumption 4-A2: t x x ≤ for all t > 0.

Properties of optimal control policies 4.3.1 Discounted cost problem

According to relation (4.1), the corresponding discounted cost MDP is as follows:

( ) ( ) , , lim , , T t i t t t t i T t i J i z E g z x w z z α μπ α - →∞ = ⎡ ⎤ = = ⎢ ⎥ ⎣ ⎦ ∑ (4.2)
for any given initial state z i =z with i = 1, …7 with discount factor α such that 0 < α < 1.

Consider the following optimal cost function

( ) ( ) , , , U i z MIN J i z α α μ π μπ = (4.3)
In the remaining, for simplicity, the notation α is omitted in this subsection where only discounted cost problem with a given α is considered. Theorem 6.10.4 in [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF] is used to established the optimality equation. It will be shown in Remark 4-1 that all conditions needed for application of Theorem 6.10.4 are satisfied. Since the set of states (i, z) is countable and the control constraint set is finite as x t ≤ z t and w t ≤ n t+1 for each z t , Theorem 6.10.4 in [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF] implies that the optimal cost function is the unique solution of the following optimality equation:

( ) ( ) ( ) ( ) 1 , , , min , , 1, , 1,
..., 7

i i i i i i i i d i a x w a U i z g z x w P U i x w a i α + ⎧ ⎫ = + + + + ∀= ⎨ ⎬ ⎩ ⎭ ∑ (4.4)
where the optimal control policy is stationary deterministic and is given by the argument w and x that reach the minimum in (4.4)

+ + + = - + - + - - ∀ ≤ ≤ - , relation (4.5) can be rewritten as ( ) ( ) ( ) ( ) ( ) ( ) { } 0, min 1 t t t t R t R t t t t t t t x z n x U z c n z T z n V x T x + + + ⎡ ⎤ ∈ - ∧ ⎢ ⎥ ⎣ ⎦ = - + - + - - (4.8) ( ) ( ) ( ) 1 1 1
+ + + + ⎡ ⎤ ∈ - ⎢ ⎥ ⎣ ⎦ ⎧ ⎫ = + + + ⎨ ⎬ ⎩ ⎭ ∑ (4.9)
U t (z t ) is used to explore the optimal patient assignment policy depending on state variable z t , whereas V t (x t ) is used to establish the optimal one-day advance CTS cancellation control policy depending on state variable x t .

Similarly, relation (4.4) can be rewritten as

( ) ( ) ( ) ( ) ( ) ( ) { } 0, , m i n , 1 i R R i i x z n x U i z c n z T z n V i x T x + + + ⎡ ⎤ ∈ - ∧ ⎢ ⎥ ⎣ ⎦ = - + - + - - (4.10) ( ) ( ) ( ) 1 1, 0, , min 1 , i i a w n x a V i x bw P U i x w a α + + + ⎡ ⎤ ∈ - ⎢ ⎥ ⎣ ⎦ ⎧ ⎫ = + + + + ⎨ ⎬ ⎩ ⎭ ∑ (4.11)
By relation (4.7) and the uniqueness of the optimal value function, ( ) ( )

7

, lim

n i n V i x V x -+ →∞ = ( 4
1 t t R t t c U z U z T -≤ - -≤ .
Proof: The proof is done by induction on t. The property trivially holds for t=0. Assume that it holds for some t+1≤0 and consider day t. Let (

+ ⎡ ⎤ ∈ - ∧ ⎣ ⎦ , ( ) 2 0, 1 t t t x z n x + ⎡ ⎤ ∈ -- ∧ ⎣ ⎦ . Taking ( ) ( ) 2 2
, ,

t t t t
x w x w = as the feasible control for ( )

t t
U z leads to ( ) ( )

1 t t R t t U z U z T - -≤
and proves the right relation of the property.

To prove the left side, the relation trivially holds if (z t -n t ) + =0 as U t (z t ) -U t (z t -1)= -c. Otherwise, two cases are possible.

Case 1:

( )

1 0 t t t x z n + ≤ < - , taking ( ) ( ) 1 1
, ,

t t t t
x w x w = as the feasible control for ( )

1 t t U z - gives ( ) ( ) 1 t t R t t U z U z T - -≥
Case 2:

( )

1 0 t t t x z n + = - > , taking ( ) ( ) 1 1
, 1 ,

t t t t
x w x w = as the feasible control for ( )

1 t t U z -, then ( ) ( ) ( ) ( )
( ) ( ) ( )

1 1 1 1 1 1 1, 1 1
1 1 t t t t U z U z c c α - -≥ -≥-.
Q.E.D.

Property 4-2:

In the value iteration by (4.8)-(4.9), ( ) ( )

1 t t R t t b V x V x T -≤ - -≤ for any x t .
Proof: The proof is done by induction on t. Since ( ) = + as the feasible control for ( )

0 0 U z = , ( ) 1 t V x - =0
1 t t V x -, ( ) ( ) 1 t t t t V x V x b - -≥-.
Case 2:

( )

1 1 1 1 1 1 1 1 1 1 1 t t t t t t t t U x a U x a V x V x b + + + + + + + - -+ ≥ + - -≥ -.
We now prove the right hand relation. Two cases are considered:

Case 1:

1 0 1 ( ) ( )

1 t t t t V x V x b - -≤-.
Case 2: 2 0 t w = . Taking 0 t w = for ( )

t t
V x and combining with Property 4-1 lead to

( ) ( ) ( ) ( ) ( ) 1 1 1, 1 1 t t t t R t t t a t t a V x V x P U x a U x a T α α + + + - -= + - + -≤ ∑
This completes the proof. Q.E.D.

Property 4-3:

In the value iteration by (4.5) or equivalently (4.8)-(4.9), U t (z t ) is convex in z t and V t (x t ) is convex in x t .

Proof: This proof is made by induction on t. First U 0 (z) = 0 and is hence convex in z.

Assume that U t+1 (z) is convex in z.

We first prove that V t (x t ) is convex in x t and show the form of the optimal CTS cancellation policy. Let us rewrite relation (4.9) as follows:

( ) ( ) ( ) ( )

( ) ( )
1 1 1 1 1 1 t t t t t V S b S R S + + + -= - -+ -. Hence ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 t t t t t t t t V S V S b R S R S b + + + + - -=-+ - -<-
which contradicts Property 4-2 and prove S t+1 ≤ n t+1 .

Since S t+1 ≤ n t+1 , ( ) ( ) ( )

1 1 1 , , t t t t t t t t t t t t bx R S x S V x bx R x x S + + + ⎧-+ ∀ ≤ ⎪ = ⎨ -+ ∀ > ⎪ ⎩
which can be easily shown to be convex in x t . The optimal CTS cancellation is characterized by a single threshold S t+1 . If the ending CTS queue length in day t is below this threshold, then cancel enough CTS in order for x t +w t to reach this threshold. Otherwise, no CTS is cancelled.

We then prove that U t (z t ) is convex in z t and show the form of the optimal patient assignment policy. First ( ) ( )

1 t R t t V x T x - - is also convex. Let ( ) ( ) ( ) ( ) ( ) 0 arg min 1 t t t t R t t t x z n x L V x T x + ≤ ≤ - ∧ = - - (
c n z V z n U z z n V z n n z L n L T z n L V L z L n ⎧ -+ ≤ ⎪ = -+ - < ≤ + ⎨ ⎪ + -- + > + ⎩
The optimal patient assignment policy is as follows. No patient is sent to RTS if the resulting CTS queue length at the end of day is below the threshold L t . Otherwise, some patients are sent to RTS to keep the CTS queue length at L t .

Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 67 U t (z t ) is convex in z t in the following internal [0, n t ), (n t , L t +n t ), and (L t +n t , +∞) . We still need to prove the convexity of U t (z t ) for z t = n t and z t =L t +n t . The convexity of U t (z t ) in z t holds when z t = n t , because U t (z t ) -U t (z t -1) = -c and from Property 4-1, U t (z t ) -U t (z t -1)≥-c.

The convexity of U t (z t ) in z t holds when z t = L t +n t , because U t (z t )-U t (z t -1)=T R and from

Property 4-1, U t (z t ) -U t (z t -1)≤T R . Therefore, U t (z t ) is convex in z t . Q.E.D.
Theorem 4-2: The optimal value functions U(i, z) and V(i, x) in relation (4.10) and (4.11) are convex in z and x respectively. Further, the optimal control policy for problem (4.3) is of the following form:

1) The optimal CTS queue length at the end of day i is:

* 0 if 0 if 0 if i i i i i i i i i i i i z n x z n z n L L z n L -≤ ⎧ ⎪ = - ≤ -≤ ⎨ ⎪ -≥ ⎩ (4.15) where ( ) ( ) ( ) 0 arg min , 1 R i x x L V ix T x ≤ ≤ = - - .
The optimal number of patients assigned to RTS at the end of day i is:

( ) * * i i i i y z n x + = --
2) The optimal number of CTS cancelled at the end of day i is:

1 1 * 1 if 0 if i i i i i i i S x x S w x S + + + - ≤ ⎧ = ⎨ ≥ ⎩ (4.16)
where ( )

1 1 , 0 arg min 1, i i a y a S b y P U i y a α + + ≥ = + + + ∑ .
Proof: The convexity of U(i, z) and V(i, x) is a direct consequence of relations (4.7), (4.12), and Property 4-3. Note that, as a result of relations (4.7) and (4.12), Properties 4-1, 4-2 also hold for U(i, z) and V(i, x). The form of the optimal control policy can be proved as in the proof of Property 4-3. Q.E.D.

Average cost problem 4.3.2.1 Bounded demand case

The following assumption is also made for the average cost problem case.

Assumption 4-A3.

There exists a finite number A such that a t ≤A, for all t.

Remark 4-2:

The assumption is not restrictive in practice as A can be chosen large enough.

( ) ( ) , 7,0 U i z U M α α - ≤ , for all i = 1, …,7 and
for all x and z.

Proof: From Property 4-1, ( ) ( )

1 t t R t t c U z U z T α α -≤ - -≤
which, together with the finiteness of the state space, ( ) ( ) Theorem 4-3. There exists an optimal stationary control policy, the same with those in Theorem 4-2, for the average cost model (4.1). Further the optimal average cost is independent of the initial state (i, z).

' t t t t Cz U z U z Cz α α -≤ - ≤ for all z t , z' t with C = Max(T R , c). Combining with relation (4.7), ( ) ( ) , , ' Cz U i z U i z Cz α α -≤ - ≤ (
Proof. From Proposition 4.2.6 in [START_REF] Bertsekas | Dynamic Programming And Optimal Control[END_REF], the optimal average cost per day exists and has the same value λ for all initial states, and λ satisfies ( ) ( )

1 lim 1 , U i z α α λ α → = - (4.24)
The differential cost functions

( ) ( ) ( ) ( ) 1 , lim , 7,0 H i z U i z U α α α → = - (4.25)
satisfy the following optimality equations:

( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( ) { } , min , , 1,..., 7 i R i i x z n x H i z c n z x T z n x F i x i + + + ≤ - ∧ = - + + -- + ∀= (4.27) ( ) ( ) ( ) 1 1, , min 1,
( ) ( ) ( ) ( ) 1 , lim , 7,0 F i x V i x U α α α → = - (4.29)
Further, the optimal control policy is stationary deterministic and is defined by the argument that reaches the minimum in (4.26) or equivalently (4.27)-(4.28). From Theorem 4-2 and (4.25) and ( 4.29), H(i, z) is convex in z and F(i, x) is convex in x for all i = 1, …, 7. The optimal control policy is the same with that of Theorem 4-2. Q.E.D.

Unbounded demand case

This subsection relaxes assumption 4-A3.

Property 4-5: For any z ≥ z'≥0, ( ) ( )

' t t R m U z U z m T z α α -≤ - ≤ + with ( ) R m c b T x = + + .
Proof: The property trivially holds for t = 0. Consider the case t < 0. Since the "min" term in equation (4.8) is decreasing in z t , subtracting equation (4.8) with z t = z by equation (4.8) z t = z' leads to:

t t R R t t t t t t R x z n x t t R x z n x U z U z c n z T z n c n z T z n V x V x T x x cn V x V x T x x α α α α α α + + + + + + ⎡ ⎤ ∈ - ∧ ⎢ ⎥ ⎣ ⎦ ⎡ ⎤ ∈ - ∧ ⎢ ⎥ ⎣ ⎦ - = - + - - - - - + - - - - ≥ - + - - - - (4.31) For any x > x', from Property 4-2, ( ) ( ) ( )( ) ' 1 ' t t R R V x V x T x x bx T x α α - - - - ≥-- (4.32) For any x ≤ x', from Property 4-2, ( ) ( ) ( )( ) ' 1 ' t t R V x V x T x x α α - ≤ - - (4.33)
Combining relations (4.31)-( 4.32) leads to:

( ) ( ) ' * ( ) t t R R U z U z cn bx T x c b T x α α - ≥- -- ≥-+ + .
Q.E.D.

Property 4-6:

There exist M>0 and r > 0 such that ( ) ( )

, 7,0 M U i z U M rz α α -≤ - ≤ +
, for all i = 1, …,7 and for all z.

Proof: From Property 4-5,

( ) ( ) ' , ' t t R m U z U z m T z z z α α -≤ - ≤ + ∀ ≥ .
Combining with relation (4.7),

( ) ( ) , , ' , ' t t R m U i z U i z m T z z z α α -≤ - ≤ + ∀ ≥
This establish the property for i = 7. Further

( ) ( ) , ,', ,' t R t U i z m T z U i z z z α α ≤ + + ∀ ( 4
R R R R R U i z m T a T z m T z a U m T a T z U i α α α ≤ + + + + + + ≤ + + + ∀ = (4.38) Similarly, ( ) [ ] ( ) ( ) ( ) ( ) 7 7 7, 0 7 , 6 * 8 55 * , i R R R U m T E z U iz m T a m T a U iz

Proof:

The proof is based on Theorem 8.10.7 of [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF] and the conditions that need to be checked are the following ones:

C1: For each state (i, z), the stage cost is such that -∞ < R ≤ g i (z, x i ) < ∞.
C2: For each (i, z) and α < 1, ( ) 4-3, equations (9), H(i, z) is convex in z and (c) of the Theorem can be proved as for Theorem 4-2.

, U i z α < ∞ . C3: There exists K > -∞ such that, for each (i, z), ( ) ( ) ( ) , , 7, 0 , 1. H i z U i z U K α α α α ≡ - ≥ ∀ < C4: There exists a non-negative function W(i, z) such that a) W(i, z) < ∞; b) for each (i, z), ( ) ( ) , , , 1
H i z W i z α α ≤ ∀ < ;
Let us now prove conditions C1-C4. Condition C1 clearly holds as g i (z, x i ) ≥ 0. Condition C2 holds as well as (iv) as in Property 4-6, ( )

0 , , R t t t t t g z x w m T z ≤ ≤ + (v) ( ) ( ) , , * R R t t t t t E g z x w E m T z m T x a ⎡ ⎤ ≤ + ≤ + + ⎡ ⎤ ⎣ ⎦ ⎣ ⎦ ; (vi) ( ) ( ) ( ) ( ) , * * . 1 R R V i z c b n T z m T x a α α α ≤ + + + + + - Condition C3 is guaranteed by Property 4-6 with K = -M. Condition C4 is a consequence of Property 4-6 with W(i, z) = M + rz. Q.E.D.

Computation and implementation of the optimal control policies

For any given contract n, as proved in Theorem 4-3 and 4-4, there exit the same optimal control policies for average-cost MDP and discounted-cost MDP. The related optimal control policies π(n) and μ(n) can be determined by solving the following LP model:

( ) maximize J λ ≡ n Subject to ( ) ( ) ( ) ( ) , , , 1,..., 7 R i i i i i i i i H i z c n z x T z n x F i x i + + ≤ - + + -- + ∀ = ( ) ( ) 1, , 1, , 1,..., 7 i i i a i i a F i x bw P H i x w a i λ + + ≤ + + + + ∀ = ∑ ( ) ( ) 1 , , 1,..., 7 i i i i i i x z n x w n x i + + + ∀ ≤ - ∧ ∀ ≤ - ∀ =
Where J(n) is the optimal average cost for problem (4.1) under contract n. The optimal controls are respectively given by x and w reaching equality in the above relations. Further, Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 73 the optimal control is characterized by two control threshold vectors L and S for patient assignment and CTS cancellation. From relations x i =min(L i ,(z i -n i ) + ), and w i =max ((S i+1x i ) + ,0), the optimal control thresholds L and S can be easily determined.

The existence of optimal control policies makes the implementation easy. For day t, the implementation of the optimal patient assignment policy depends on state variable z t , while that of the optimal one-day advance cancellation policy depends on x t , the CTS queue length at the end of day t. Therefore, patient assignment is first made, then CTS is cancelled for next day.

The implementation of the optimal patient assignment control policy can be divided into three cases:

Case 1: As shown in Fig. 4.1, if state variable z t is smaller than n t , then there exists the number n t -z t of unused CTS, and no patients waiting for the incoming time slots. The implementation of the optimal one-day advance cancellation control policy depends on the ending CTS queue at the end of the same day, which can be divided into two cases:

Case 1: As shown in Fig. Remark 3-5 can be applied to here. The implementation of this contract-based MRI reservation process can be directly applied to the hospital combined with some patient scheduling policy. However, to improve its performance, more work should be done about patients scheduling in order to reduce the variance of patients waiting times.

Local Optimization

Starting from a given initial contract, this section presents a local search for improving the contract decisions by taking into account both patient assignment and one-day advance CTS cancellation policies. This local search relies on the structure properties of the previous section especially the LP model in Section 4.3.3 for contract evaluation.

The local search starts from an initial contract n 0 . It then iteratively improves this contract.

At each iteration, it determines the best neighbor solution among the set of contracts: n + e k (increasing one time slot in day k), ne k (reducing one time slot in day k), ne k + e j (move one time slot from day k to day j). This process repeats until no improvement can be found.

The overall algorithm for the contract optimization is summarized as follows:

Algorithm (Local optimization)

1. Select an initial contract n 0 , determine the optimal control policy π(n 0 ), μ(n 0 ) and the optimal average cost J(n 0 ) under contract n 0 by solving LP model; In the numerical experiments of the next section, the initial contract decisions are obtained by the method proposed in our previous chapter for optimizing the contract decisions without CTS cancellation.

Computational Results

This section presents numerical results to show the benefit of CTS cancellation control policy and local improvement. In the following, the impact of CTS cancellation is analyzed with respect to the cancellation cost b, unused CTS cost c, average delay T R of regular reservation, patient arrival pattern, and the patient arrival rate.

For each case, three solutions are considered: (i) the solution with only patient assignment policy considered for the initial contract n 0 . This solution will be denoted "NoCancel"; (ii) the solution considering both CTS cancellation and patient assignment policies for the contract n 0 . This solution will be denoted "Cancel"; (iii) the solution after local optimization starting from n 0 , where both policies are considered. This solution will be denoted "LocalOpt".

The three solutions are further compared with respect to different performance criteria including the average delay, the unused CTS ratio, the percentage of patients using RTS, and the percentage of CTS cancelled.

The CPU time for local optimization is less than 6 minutes except for medium and high demand cases considered in Section 4.5.3.

Impact of CTS cancellation and CTS cancellation cost

This subsection considers the impact of CTS cancellation by varying the cancellation cost b from 0.1c to 0.9c. Fig. 4.6 compares the criterion values of the three solutions "NoCancel", "Cancel", "LocalOpt". From this figure, the cancellation cost b greatly impacts on the benefit of CTS cancellation. The gain of CTS cancellation with respect to the contract "NoCancel" is 31.76% for b=0.1c, 14.86% when b=0.4c, and 0% when b=0.9c. Similar, the local optimization further improves both the contract and the control policies. The gain of Local optimization with respect to the solution "Cancel" is 33.77% for b= 0.1c, 5.38% for b=0.4c and 0 for b=0.9c. The total improvement of cancellation and local optimization with respect to the solution "NoCancel" is 54.8% for b = 0.1c, 19.4% for b = 0.4c and 0 for b = 0.9c. 4.2 summarizes the contracts, the optimal patient assignment policies and the optimal CTS cancellation policies for different cancellation cost b. The optimal contract the optimal control policy for the "NoCancel" solution strategy is n = (1, 1, 1, 1, 3, 0, 0), L = (11, 11, 11, Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 79 11, 9, 10, 10) which are identical to the control for "Cancel" strategy with b = 0.9c. The optimal patient assignment policy of "Cancel" strategy is somewhat counter-intuitive. One would expect that, with CTS cancellation, a longer waiting queue is needed. However, the opposite happens. The optimal CTS queue threshold L is actually smaller than the one for "NoCancel" strategy. More CTS are cancelled when b is small. For example, when b is smaller than 0.6c, all CTS except one for Friday that cannot be used by patients in CTS queue are cancelled. For the optimal contract of "LocalOpt" strategy, more CTS are planned when b is small. Further, thanks to the possibility of CTS cancellation, CTS are now planned for Weekend. Further, when b is small, large CTS queue are used because of more CTS introduced so as to avoid assignment to RTS. 9, 9, 10, 8, 8, 9}. L ={18, 18, 18, 19, 18, 17 9, 10, 10, 8, 9, 9}. L ={14, 14, 14, 14, 14, 13, 12}.

b "Cancel" "LocalOpt" n={1, 1, 1, 1, 3, 0, 0}; 7CTS n ={0, 1, 2, 1, 2, 2, 1}; 9CTS 0.1c S={1, 1, 1, 1, 2, 0, 0}; S ={0, 1, 2, 1, 2, 2, 1}; L={9,
, 17}. n={1, 1, 1, 1, 3, 0, 0};7CTS n ={0, 1, 1, 1, 2, 2, 1};8CTS 0.2c S={1, 1, 1, 1, 2, 0, 0}; S ={0, 1, 1, 1, 2, 2, 1}; L={9,
n={1, 1, 1, 1, 3, 0, 0};7CTS n ={0, 1, 1, 1, 2, 2, 1};8CTS 0.3c S={1, 1, 1, 1, 2, 0, 0}; S ={0, 1, 1, 1, 2, 2,
1}; L={10, 10, 10, 10, 8, 9, 9}.

L ={14, 14, 15, 15, 14, 13, 13}. n={1, 1, 1, 1, 3, 0, 0};7CTS n={0,

1};8CTS 0.4c S={1, 1, 1, 1, 2, 0, 0}; S ={0, 1, 1, 1, 2, 2, 1}; L={10, 10, 10, 10, 9, 9, 10}.

L ={14, 15, 15, 15, 15, 13, 13}. n={1, 1, 1, 1, 3, 0, 0};7CTS n ={0, 1,1, 1, 2, 2, 0};7CTS 0.5c S={1, 1, 1, 1, 2, 0, 0}; S ={0, 1, 1, 1, 1, 2, 0}; L={10, 10, 10, 11, 9, 9, 10}.

L ={10, 10, 10, 11, 10, 8, 9}. n={1, 1, 1, 1, 3, 0, 0};7CTS n ={0, 1, 1, 2, 1, 2, 0};7CTS 0.6c S={0, 1, 1, 1, 1, 0, 0}; S ={0, 1, 1, 1, 0, 2, 0}; L={10, 10, 10, 11, 9, 9, 10}. L ={10, 11, 11, 10, 10, 9, 9}. n={1, 1, 1, 1, 3, 0, 0};7CTS n ={1, 1, 1, 1, 1, 2, 0};7CTS 0.7c S={0, 0, 0, 0, 1, 0, 0}; S ={0, 0, 0, 0, 0, 2, 0}; L={10, 11, 11, 11, 9, 10, 10}.

L ={10, 10, 10, 11, 11, 9, 10}. n={1, 1, 1, 1, 3, 0, 0};7CTS n ={1, 1, 1, 1, 2, 1, 0};7CTS 0.8c S={0, 0, 0, 0, 1, 0, 0}; S ={0, 0, 0, 0, 0, 1, 0}; L={11, 11, 11, 11, 9, 10, 10}. L ={10, 10, 11, 11, 10, 10, 10}. n={1, 1, 1, 1, 3, 0, 0};7CTS n ={1, 1, 1, 1, 3, 0, 0};7CTS 0.9c S={0, 0, 0, 0, 0, 0, 0}; S ={0, 0, 0, 0, 0, 0, 0}; L={11, 11, 11, 11, 9, 10, 10}. L ={11, 11, 11, 11, 9, 10, 10}. TAB. 4.2 Contracts and control policies vs cancellation costs b

Impact of CTS cancellation and unused CTS cost

This subsection considers the relation between the impact of CTS cancellation and the unused CTS cost c by varying c for the base case with b = 0.5c. Table 4.3 summarizes the performance measures of different solution strategies. When c increases, CTS cancellation significantly reduces the unused CTS ratios with slightly longer delay. There is no obvious trend of CTS cancellation ratio when c increases. The "LocalOpt" strategy further improves the "Cancel" strategy by reducing the unused CTS ratio, the average delay with increased CTS cancellation.

Table 4.4 summarizes the contract, patient assignment and CTS cancellation policies. For all solution strategies, the number of CTS decreases when c increases. "Cancel" strategy has slightly shorter CTS queue than "NoCancel" strategy. The major difference of the "LocalOpt" strategy with the two other strategies is the CTS planned for the weekend even for the case of large unused CTS cost. "LocalOpt" also allows more CTS cancellation than "Cancel" strategy. S={0, 0, 0, 0, 0, 1, 0}; S ={0, 0, 0, 0, 0, 1, 1}; L={22, 22, 22, 21, 21, 21, 22} L={22, 22, 22, 21, 21, 21, 22} L={22, 21, 22, 22, 22, 21

, 21} n={1, 1, 1, 2, 2, 1, 0}; 8CTS n={1, 1, 1, 2, 2, 1, 0}; 8CTS n={1, 1, 1, 1, 2, 2, 0}; 8CTS 5
S={0, 0, 0, 1, 0, 1, 0}; S ={0, 0, 0, 0, 1, 2, 0}; L={13, 14, 14, 13, 13, 12, 13} L={13, 14, 14, 13, 13, 12, 13} L={13, 13, 13, 14, 13, 12

, 13} n={1, 1, 1, 1, 3, 0, 0}; 7CTS n={1, 1, 1, 1, 3, 0, 0}; 7CTS n={0, 1, 1, 2, 2, 1, 1}; 8CTS 10 S={0, 0, 0, 0, 1, 0, 0}; S ={0, 1 , 1, 1, 1, 1,
1}; L={10, 10, 10, 10, 8, 9, 9} L={10, 10, 10, 10, 8, 9, 9} L={14, 15, 15, 14, 14, 13, 13} n={1, 1, 1, 1, 3, 0, 0}; 7CTS n={1, 1, 1, 1, 3, 0, 0}; 7CTS n={0, 1, 1, 1, 2, 2, 0}; 7CTS 15 S={1, 1, 1, 1, 2, 0, 0}; S ={0, 1, 1, 1, 1, 2, 0}; L={11, 11, 11, 11, 9, 10,10} L={10, 10, 10, 11, 9, 9,10}. L={10, 10, 10, 11, 10, 8, 9} n={1, 1, 1, 1, 3, 0, 0}; 7CTS n={1, 1, 1, 1, 3, 0, 0}; 7CTS n={ 0, 1, 1, 1, 2, 2, 0}; 7CTS 20 S={1, 1, 1, 1, 2, 0, 0}; S ={ 0, 1, 1, 1, 1, 2, 0}; L={11, 12,12,12,10,11,11} L={11,11,11,11,[START_REF] Geng | Stochastic-programming-based capacity planning for wafer fabrication[END_REF]10,10} L={11,11,11,11,10,[START_REF] Geng | Stochastic-programming-based capacity planning for wafer fabrication[END_REF]9} TAB. 4.4 Contracts and control policies vs unused CTS costs c

Impact of CTS cancellation and other data

This subsection investigates the relationship between the impact of CTS cancellation and other problem parameters including (i) the average RTS delay T R , (ii) the patient arrival pattern, and (iii) the patient arrival rate. With respect to the average RTS delay T R , numerical experiments are performed for the base case by varying T R from 25 to 45. For all three solution strategies, the criterion values, the performance measures, the contract and the control strategies given in the Table 4 With respect to the patient arrival rate, three instances are considered: (i) the base case that is termed "low demand" instance; (ii) the base case but with patient arrival rate 5 times larger and termed "medium demand" instance; and (iii) the base case with patient arrival rate multiplied by 10 and termed "high demand" instance. Fig. 4.8 compared the criterion values of different solution strategies. CTS cancellation brings 9.3% improvement over "NoCancel" strategy for low demand instance, 5% for medium demand and 6.8% for high demand instance. Local optimization further brings 4.8%, 5.8% and 3.7% improvement over "Cancel" strategy and leads to a combined improvement of 13.6%, 10.5% and 10.2% for the three instances. These results show that the CTS cancellation is useful for both low demand and high demand instances. 4.9 summarizes the performance measures of different solution strategies. In all solution strategies, increasing the patient arrival rate leads to shorter delay. For "NoCancel", unused CTS ratio becomes smaller. For "Cancel" and "LocalOpt" strategies, CTS cancellation ratio decreases significantly, the percentage of patients assigned to RTS decreases while CTS unused ratio fluctuates but remains small.

CPU time for local optimization is less than 6 minutes for all the low demand instances, 2407s for medium demand instance and 6324s for the high demand instance. The resulting contract and control policies are given in the n={5,5,5,6,9,1,0};31CTS n={5,5,5,6,9,1,0};31CTS n={3,5,5,6,8,4

Conclusions and perspectives

This chapter proposed an MRI examination reservation process between the neurovascular department and the imaging department combining (i) contracted time slots reserved by the imaging department for the neurovascular department, (ii) one-day advance cancellation of contracted time slots, and (iii) patient assignment control policy. An average cost MDP model is proposed to simultaneously determine the optimal patient assignment and CTS cancellation control policies. Structure properties are established via discounted cost problem. A local optimization is used to improve a given initial contract. Numerical results show that the consideration of CTS cancellation can greatly reduce the unused CTS ratio with a little increase in average delay. Local optimization can further decrease the contract and the control policies.

Future research can be pursued in several directions. One immediate extension is to allow CTS cancellation several days before. One research direction is the extension of this work to multiple classes of patients and multiple imaging examinations. Another very challenging issue is the optimization of the operation of the imaging department by considering the quality requirements of medical units.

Chapter 5

Contract planning and two-day advance cancellation of contracted time slots

This chapter exploits the use of two-day advance CTS cancellation to further improve contract for MRI examinations between a neurovascular department treating stroke patients and an imaging department. The contract is composed of four parts: contract decisions, oneday advance CTS cancellation policy, two-day advance CTS cancellation policy, and patient assignment policy. The problem of CTS cancellations and patient assignment are formally formulated as an average cost Markov Decision Process in order to compromise among the patients' waiting time, unused CTS penalty, and CTS cancellation penalty. Structure properties of the optimal control policies are established via the discounted cost problem and some advanced convexity concepts. Local search algorithm is proposed to improve the contract decisions. Numerical results show that advance CTS cancellation and local optimization significantly reduces the criterion value and the ratio of unused CTS.

Introduction

Chapter 3 and Chapter 4 propose a contract-based MRI examination reservation process in order to reduce the stroke patients' waiting time for MRI examination. The contract decisions and patient assignment control policy are jointly solved in Chapter 3. Chapter 4 proposes an MDP formulation to determine the patient assignment and one-day advance CTS cancellation control policies at the same time in order to further reduce the unused CTS. This new reservation process seems perfect with shorter delay and lower unused CTS ratio. However, for the imaging department side, it would be hard to arrange other patients for the time slots released from contract with short notice of only one day. Therefore, this chapter exploits the possibility of earlier CTS cancellation.

The contract now includes the following four decisions: 1) contract decisions; 2) patient assignment control policy; 3) one-day advance CTS cancellation control policy; and 4) twoday advance CTS cancellation control policy. This chapter tries to simultaneously explore the structure properties of three control policies and then improve the contract by using local search algorithm. The rest of this chapter is organized as follows: Section 5.2 provides a formal problem setting. Structure properties of the optimal control policies are established via discounted cost MDP in Section 5.3 and 5.4.

Local optimization of the contract is proposed in Section 5.5. Section 5.6 analyzes results of computational experiments. Conclusions and perspectives are given in Section 5.7.

Problem setting

This section presents an MDP formulation of the problem of patient assignment and one-day and two-day advance CTS cancellation. Assumptions 1 to 4 presented in Chapter 1 are considered. Further, the following assumption is made throughout the chapter:

Assumption 5-A1 CTS of day t can be cancelled in advance of one and two days, i.e., at end of day t-2 or at the end of day t-1.

Based on the above assumptions, the problem of patient assignment and advance CTS cancellation can be characterized by the following notations: Indices:

t: index of days, t=1,…,T;

i: index of days in one week, i=1,…,7, i.e., Monday, …, Sunday; note that the day i±j is the weekday of j days after or before day i in one week; a t : number of patients arrived in day t. By assumption 3, daily arrivals a t for t ∈ IN are mutually independent random variables and weekly arrivals (a 7j+1 , a 7j+2 , …, a 7j+7 ) are identically distributed for all j = 0, 1, …. As a result, the arrival process is characterized by probability matrix P = [P ij ] for i = 1, …, 7 and for all j ≥0 with P ij denoting the probability of j arrivals in day i; n t : number of CTS in day t;

Decision variables:

Chapter 5 Contract planning and two-day advance cancellation of contracted time slots 89

x t : number of patients waiting for CTS at the end of day t, which is also called CTS queue, 0

x is a given constant. Note that x t does not include patients that are directed to RTS.

+ + + + →∞ = ⎡ ⎤ = = = ⎢ ⎥ ⎣ ⎦ ∑ (5.1)
for any given initial state ( )

, Theorem 5-1: There exists an optimal average cost policy such that t x x ≤ for all t > 0 with

i i z z w w + = = with i = 1, …7 where
( ) ( ) ( ) ( ) ( ) ( ) 2
( ) * R x T c n ⎡ ⎤ = + ⎢ ⎥ where n* = MAX{n 1 , …, n 7 }.
Proof. The proof can use the same method with that for Theorem 3-1. Q.E.D.

Thanks to Theorem 5-1, we can make without loss of generality the following assumption:

Assumption 5-A2: t x x ≤ for all t > 0.

Properties of optimal control policies for discounted cost problem

According to relation (5.1), the corresponding α-discounted cost MDP is as follows:

( ) ( )

1 2 2 1 2 2 1 1 2 1 , , , lim , , , , , T t i t t t t t t i i T t i J i z w E g z w x w w z z w w α μ μ π α - + + + + →∞ = ⎡ ⎤ = = = ⎢ ⎥ ⎣ ⎦ ∑ (5.2)
for any given initial state In the remaining, for simplicity, the notation α is omitted in this subsection where only discounted cost problem with a given α is considered. Theorem 6.10.4 in Puterman (1994) is used to establish the optimality equation. It will be shown in Remark 5-1 that all conditions needed for application of Theorem 6.10.4 are satisfied. Since the set of states (i, z, w) is countable and the control constraint set is finite as

x t ≤ z t and 1 ≤ for each z t , Theorem 6.10.4 in [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF] implies that the optimal cost function is the unique solution of the following optimality equation:

( ) ( ) ( ) ( ) 1 2 1 2 2 1 2 1 1 2 2 1 2 , , 1 1 2 1 , , , , , , , min , 1,
..., 7 1, ,

i i i i i i i i i x w w i i i i d i a a g z w x w w U i z w i P U i x w w a w α + + + + + + + + + ⎧ ⎫ ⎪ ⎪ = ∀ = ⎨ ⎬ + + + + + ⎪ ⎪ ⎩ ⎭ ∑ (5.4)
The optimal control policy is stationary deterministic and is given by the argument w 1 , w 2 and x that reach the minimum in (5.4) and the optimal cost function is the limiting function of the following value iteration:

( ) ( ) ( ) 1 2 1 2 2 2 1 2 1 1 2 2 1 1 1 2 1 , 1 1 2 , , , min , , , , , t t
⎧ ⎫ = + + + + ⎨ ⎬ ⎩ ⎭ ∑ (5.5) ( ) 0 0 U z = (5.6)
for t = 0, -1, -2, … where ( ) ( )

0 t t t x z n x + ≤ ≤ - ∧ ,
( )

⎧ ≥ ⎪ = ⎨ + - ≤ ⎪ ⎩ (5.20)
As a result, relation (5.18) can be rewritten as

( ) ( ) ( ) ( ) ( ) , 1 , t R R t t t U z w c n z T z n T w F z w + + = - + - + - + (
f x y f x y f x f y ∨ + ∧ ≥ +
where ( ) max ( , ) x y x y ∨ = .

(

t t t t U z w U z w U z w U z w + + + ≥ + + + + (5.24) ) ( ) ( ) ( ) , 1 2, 1, 1 1,
From relation (5.21), to prove relation (5.23), we only need to prove the following relation:

( ) ( ) ( ) ( ) 1, , 2 1, 1
( )

( ) ( )
1 t t R H w H w c T + - ≥ -+ . From Property 5-1, ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 t t t t R R R t t t t H u H u V u V u T b T c T + - = + - - -≥ --+ ≥ -+ . )
In this case,

( ) ( ) ( ) ( ) ( ) 1 1 t t t t R H w H w H w H w c T + - = + - ≥ -+
, which concludes relation (5.24). Q.E.D.

Property 5-6.

( )

, t U z w is convex in z and convex in w if ( ) t t W y is convex in y t ,.
Proof. This property is a direct result from properties 5-3 and 5-5. Q.E.D.

The superconvexity of ( ) , t U z w implies the superconvexity of ( )

, t G y w . ( ) ( ) ( ) ( ) 1, , 2 1, 1
+ + - - ≤ ≤ ∧ ≤ ≤ ∧ ⎡ ⎤ = = + + ⎣ ⎦
Combining with property 5-7,

( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 ' 1 ' 1 m i n m a x 1 , , ' t t t t t t t t w L n w L n w w w W y W y G y w G y w + + - - - - ≤ ∧ ≤ ∧ + ≥ ≥ + - = + -
To prove the convexity of W t-1 (y), we only need to prove

( ) ( ) ( ) ( ) ( ) ( ) 1
+ + + + - - ≤ ∧ ≤ ∧ + ≥ ≥ - - ≤ ∧ ≤ ∧ + ≥ ≥ + - ≥ - - (
( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 t t t t t t R R R H w H w H w H w V w V w T b T c T - + = - + = - + + -≤ + ≤ +
where Property 5-1 is applied in the above. Q.E.D.

Remark 5-2: (Property 5-2) -(Property 5-7) hold because of Property 5-8.

Theorem 5-2: The optimal value function U(i, z, w) in relation (5.11) is convex in z and w. V(i, u) in relation ( 5.12) is convex in u. W(i, y) in relation (5.13) is convex in y. Further, the optimal control policies for problem (5.4) are as follows:

i) the optimal CTS queue length at the end of day i is of the following form: And the optimal number of patients assigned to RTS at the end of day i is of the following form:

* 2 2 2 0 i f 0 if 0 if i i i i i i i i i i i i i i i z n x z n z n L w L w z n L w -≤ ⎧ ⎪ = - ≤ -≤ - ⎨ ⎪ - -≥ - ⎩
( )

* * i i i i y z n x + = --
ii) the optimal one-day advance CTS cancellation policy for day i+1 is of the following form:

1 2 2 1 1* 1 1 1 1 1 2 1 1 1 if 0 if i i i i i i i i i i S x w x w S w
x w S

+ + + + + + + ⎧ -- + ≤ = ⎨ + ≥ ⎩
( 5.35) iii) the optimal two-day advance CTS cancellation policy for day i+2 is of the following form:

( ) ( )

2* 2 2 2 i i i i w y S y + + = (5.36) Where ( ) ( ) ( ) ( ) ( ) 2 2 arg min , 1 i i R i w u w z n x L Viu T u + ≤ ≤ + - ∧ = - - , { } ( ) { } 2 2 1 1 1 1 1 1 max , arg min i i i i i i i x w y x w n S Wy b y + + + + + ≤ ≤ + = + , ( ) ( ) { } 2 2 2 2 1 1 0 arg min , i i i i w n S y E b w U y a w + + + + ≤ ≤ = + + ⎡ ⎤ ⎣ ⎦ .
Proof: The convexity of U(i, z, w), V(i, x+w), and W(i, y) is a direct consequence of relations (5.7), (5.14), (5.15) and [START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Na | Implementation of MRI Examination Reservation Strategies for Stroke Patients[END_REF][START_REF] Na | Contracting MRI time slots and advance cancellation for stroke patients[END_REF][START_REF] Geng | Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity[END_REF][START_REF] Geng | A review on strategic capacity planning for semiconductor manufacturing industry[END_REF]. The theorem can be directly derived from the convexity. Q.E.D.

Properties of optimal control policies for average cost problem

Bounded demand case

The following assumption is also made for the average cost problem case.

Assumption 5-A3. There exists a finite number A such that a t ≤A, for all t.

The combination of Assumptions

( ) 2 1 2
, , 1, ,

R i i U i z w m T z E U i z w α α + + ⎡ ⎤ ≤ + + + ⎣ ⎦ (5.57)
Repeat the relations (5.57) for t subsequent days leads to:

( ) [ ] ( ) ( ) 1 2 1
, , , , , 1,..., 7 Q.E.D.

t i R t i t i i U i z w m T E z E U t i z w i α τ α τ + - + ++ = ⎡ ⎤ ≤ + + + ∀ = ⎣ ⎦ ∑ ( 5
Theorem 5-4. Under Assumptions 4, and 5-A2, (a) there exists a constant λ satisfying (5.44) for all (i, z, w), a matrix ψ(i, z, w) satisfying (5.45)-( 5.46) (b) the optimal control policy is defined by the argument that reaches the minimum in (5.46), (c) there exists an optimal stationary control policy of the form of equations ( 5.34)- (5.36) for the average cost model.

Proof:

The proof is based on Theorem 8.10.7 of [START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF] and the conditions that need to be checked are the following ones:

C1: For each state (i, z, w), the stage cost is such that -∞ < R ≤ ( )

1
+ + ≤ ≤ + + ≤ + 2) ( ) ( ) 1 2 1 2 , , , , * * R R t t t t t E g z w x w w E m T z m T x n a + + ⎡ ⎤ ⎡ ⎤ ≤ + ≤ + + + ⎣ ⎦ ⎣ ⎦ ; 3) ( ) ( ) ( ) ( ) 2 , , * * * . 1 R R U i z w c b n T z m T x n a α α α ≤ + + + + + + -

Computation and implementation of the optimal control policies

As proved in Theorem 5-3 and 5-4, there exit the same optimal control policies for averagecost MDP and discounted-cost MDP. The related optimal control policiesπ(n), μ 1 (n), and μ 2 (n) can be determined by solving the following LP model:

( ) maximize J λ ≡ n Subject to ( ) ( ) ( ) ( ) 2 1 2 1 1 , , , , , 1,
..., 7

R i i i i i z w c n z x T z n x i x w i ψ ψ + + + + ≤ - + + -- + ∀ = ( ) ( ) ( ) 1 2 2 2 1 1 1 , , , 1,
..., 7

i i i x w i y b y x w i ψ ψ + + + ≤ + -- ∀ = ( ) ( ) 2 2 2 2 2 1 , 2 , 1, , , 1
+ + + + + + ∀ ≤ - ∧ + ≤ ≤ + ≤ ≤ ∀ =
Where J(n) is optimal average cost for problem (5.1) under contract n. The optimal controls are given respectively by x y and w 2 reaching equality in the above relations. Further, optimal RTS assignment and one-day advance cancellation are characterized by two control threshold vectors L and S 1 . However, optimal two-day advance cancellation S 2 (y) is not always a simple threshold policy. From relations x i =min (L i ,-w 2 i , (z i -n i ) + ), and w 1 i+1 =max ((S 1 i+1 -x i -w 2 i+1 ) + ,0), w 2 i+2 = S 2 i+2 (y), the optimal controls L, S 1 and S 2 (y) can be easily determined.

The existence of optimal control policies makes the implementation easy. At the end of day t, the implementation of the optimal patient assignment policy first determines the CTS queue length x t which depends on state variable z t and w 2 t . The next step is to determine the number of CTS cancelled for day t+1, i.e., w 1 t+1 , which depend on w 2 t+1 and x t . The final step is to make the two-day advance cancellation decision. The number of CTS cancelled for day t+2 depends on state variable y t = x t + w 1 t+1 + w 2 t+1 .

Step 1: The implementation of the optimal patient assignment control policy can be divided into three cases:

Case 1: As shown in Fig. 5.1, if state variable z t is smaller than n t , then there exists the number n t -z t of unused CTS, and no patients waiting for the incoming time slots. Step 3: The implementation of two-day advance cancellation depends on state variable y t = x t + w 1 t+1 + w 2 t+1 which becomes known now. So the number of CTS cancelled for day t+2 is S 2 (y).

As stated in Section 3.3.3 and 4.3.3, the implementation of the contract-based MRI examination reservation process needs the aids of patients scheduling policy. To reduce the variance of patients' waiting times, more work is needed about patients scheduling.

Local Optimization of Contract

Starting from a given initial contract, this section presents a local search for improving the contract by considering patient assignment, one day advance CTS cancellation, and two-day advance CTS cancellation policies. This local search relies on the structure properties of the previous section especially the optimality equations (5.47)-( 5.49) for contract evaluation. The local search starts from an initial contract n 0 . It then iteratively improves this contract. At each iteration, it determines the best neighbor solution among the set of contracts: n + e k (increasing one time slot in day k), ne k (reducing one time slot in day k), ne k + e j (move one time slot from day k to day j). This process repeats until no improvement can be found.

The overall algorithm for the contract optimization is summarized as follows:

Algorithm (Contract optimization)

1. Select an initial contract n 0 , determine the optimal control policies π(n 0 ), μ 1 (n 0 ), μ 2 (n 0 )and the optimal average cost J(n 0 ) under contract n 0 by solving LP model;

Computational Results

This section presents numerical results to show the benefit of two-day advance CTS For each case, three solutions are considered: (i) the case with only patient assignment and one-day advance cancellation considered for the given contract n 0 . This solution will be denoted "One-day-cancel"; (ii) the case by considering one-day, two-day advance cancellation and patient assignment control policies for the given contract n 0 . This solution will be denoted "Two-day-cancel"; (iii) the contract obtained with local search starting from n 0 . This solution will be denoted "LocalOpt".

The three solutions are further compared with respect to different performance criteria including the average delay, the unused CTS ratio, the percentage of patients using RTS, the percentage of CTS cancelled.

Note that two-day advance cancellation control policy can be written in the following form for all the instances except for the high demand instance, shown in Fig. 5.5:

( ) Fig. 5.6 compares the average cost of the three solutions "One-day-cancel', "Two-daycancel", and "LocalOpt". From this figure, we note that the two-day advance cancellation cost b 2 has a great impact on the benefit of two-day advance CTS cancellation. Compared with "One-day-cancel", the gain of two-day advance cancellation decreases with the increase of b 2 , for example, the gain is 11.95% when b 2 =0.1b 1 , 3.65% when b 2 =0.5b 1 , and 0 when b 2 =0.8b 1 and b 2 =0.9b 1 . Similarly, the local optimization further improves both the contract and control policies. The gain of local optimization with respect to the solution of Chapter 5 Contract planning and two-day advance cancellation of contracted time slots 113 "Two-day-cancel" also decreases with the increase of b 2 with a gain of 30.97% when b 2 =0.1b 1 , 7.28% when b 2 =0.5b 1 , and 0 when b 2 =0.8b 1 and b 2 =0.9b 1 . The total improvement of the two-day advance CTS cancellation and local optimization with respect to the solution "One-day-cancel" decreases from 39.22% when b 2 =0.1b 1 to 0% when b 2 =0.9 b 1 . Table 5.1 summarizes the performance measures for the three different solution strategies.

2 2 2 2 2 2 2 2 2 if if , 1,..., 7 0 e l s e i i i i i i i i i i i i X y Y S y X Y y Y y X Y i + + + + + + + + ≤ ⎧ ⎪ = + - ≤ ≤ + ∀ = ⎨ ⎪ ⎩
In the table, "Delay", "Unused", "RTS", and "Cancel" separately denote the average delay, unused CTS ratio, the percentage of patients assigned to RTS, and the percentage of CTS cancelled. With respect to the strategy "One-day-cancel", the two-day advance cancellation policy slightly increases RTS percentage and decreases CTS Cancellation ratio with more unused CTS and longer delay for most instances. It is interesting that the CTS cancellation ratio does not increase under the contract obtained from Chapter 4. The contract "LocalOpt" further takes advantage of two-day advance cancellation. With respect to the solution of

Impact of other parameters

This subsection considers the relationship between the influence of two-day advance cancellation control and other parameters including (i) the average RTS delay, T R ; (ii) the patient arrival pattern, and (iii) the patient arrival rate.

To investigate the impact of the average RTS delay T R , numerical experiments are performed for the base case by varying T R from 25 to 45. For all the strategies, the average cost (see Fig. 5.9), the performance measures (see Table 5.7), and the contracts and the control policies (see Table 5.8) are fairly insensitive to the change of T R , except that RTS threshold increases with the increase of T R for all the solutions. S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,0,1,1,2} 25 X={0,0,1,1,1,2,0} X ={0,0,1,1,1,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={8, 8, 8, 9, 8, 7, 7}. L ={8,8,8,9,8,6,7} L ={11,11,11,12,11,11

,10} n={ 0, 1, 1, 1, 2, 2, 0};7CTS n={0,1,1,1,2,2,0}7CTS n={0,1,1,1,2,1,2}8CTS S={ 0, 1, 1, 1, 1, 2, 0}; S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,0,1,1,2} 30 X={0,0,1,1,1,2,0} X ={0,0,1,1,1,1,2} Y={0
,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={9, 9, 9, 10, 9, 7, 8}. L ={9,9,9,10,9,7,8} L ={13,13,13,14,13,13,11} n={0, 1,1, 1, 2, 2, 0};7CTS n={0,1,1,1,2,2,0};7CTS n={0,1,1,1,2,1,2}8CTS S={0, 1, 1, 1, 1, 2, 0}; S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,0,1,1,2} 35 X={0,0,1,1,1,2,0} X ={0,0,1,1,1,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1}

0, 1, 1, 2, 1, 2, 0};7CTS n={0,1,1,2,1,2,0}7CTS n={0,1,1,1,2,1,2}8CTS S={ 0, 1, 1, 1, 0, 2, 0}; S 1 ={0,0,0,1,0,2,0} S 1 ={0,0,0,0,1,1,2} 45 X={0,0,1,1,0,1,0} X ={0,0,1,1,1,1,2} Y={0
,0,0,1,0,0,0} Y ={0,0,0,0,1,1,1} Table 5.12 summarizes the contracts and control policies for different rates. One additional CTS is planned for "LocalOpt" and more CTS are planned in Sunday. Therefore, more CTS cancellation and higher RTS assignment are expected. Fig. 5.12 and 5.13 show the two-day advance cancellation control policy for "Two-daycancel" and "LocalOpt" solutions. These figures show the reason why these policies cannot write in the form of relation (5.62), i.e., the control policies for Wednesday and Friday in "Two-day-cancel" solution and for Thursday and Friday in "LocalOpt" solution. However, it can be approximated as the policy in the form of (5.62), as shown in Table 5.13. In this table, "obj_appr" and "obj" are separately the criterion value with the approximated policy and the real optimal policy. "Gap" is (1-obj/obj_appr)*100%. From this table, we can see that the Gap is very small, no greater than 0.25%, which means that the approximated control policies perform well.

Chapter 5 Contract planning and two-day advance cancellation of contracted time slots 125 S 2 (4)={0,0,0,0,0,1,1} S 2 (4)={0,0,0,1,1,1,4} S 2 (5)={0,0,0,0,0,0,1} S 2 (5)={0,0,0,0,0,0,3} S 2 (6)={0,0,0,0,0,0,1} S 2 (6)={0,0,0,0,0,0,2} S 2 (7)={0,0,0,0,0,0,0} S 2 (7)={0,0,0,0,0,0,1} S 2 (8)={0,0,0,0,0,0,0} S 2 (8)={0,0,0,0,0,0,0} TAB. 5.12 Contracts and control policies vs patient arrival rates CPU time for local search is less than 11 minutes for all the low demand instances, 5227s for medium demand instance, and 25057s for high demand instance.

Conclusion

This chapter proposes an average cost MDP formulation to establish the structure properties of patient assignment, one-day advance cancellation, and two-day advance cancellation control policies. Local optimization is used to improve a given initial contract. Numerical results show that the two-day advance cancellation and local optimization can greatly reduce the criterion values and the unused CTS ratio. Future research can be pursued in several directions. An extension research is needed by assuming that CTS can be cancelled in advance of arbitrary days. Multiple priorities patients and several imaging examinations are the other possible directions.

Chapter 6 Conclusion

Stroke patients need quick diagnosis. However, significant delays are observed as many key examinations depend on expensive and heavily used imaging facilities such as MRI scanners. The objective of this thesis aims to reduce the waiting time of stroke patients for MRI examination without degrading the utilization of MRI scanner.

Based on the field observation of stable weekly patient arrivals, we have proposed a new contract-based MRI examination reservation process for stroke patients, i.e., neurovascular department reserves a certain number of contracted time slots for stroke patients every week.

Except for these contracted ones, the time slots by regular request are still possible for stroke patients. To implement this new reservation process, three decisions need to be determined: Contract decisions, i.e. the number of CTS and its distribution over time. Patient assignment control policy, i.e., the real time control for assigning the incoming patients to CTS or RTS.

Advance CTS cancellation control policy, i.e., the real time control for cancelling the CTS in advance. To determine the above decisions, we make the following contributions: Chapter 3 proposes an integrated stochastic programming model to simultaneously determine the optimal contract and the optimal patient assignment control policy. This problem is difficult as it involves simultaneously two decisions at different levels, the contract at the tactical level and the optimal control policy at the real-time level. In order to solve this model, we first consider the optimal control problem for a given contract. An average cost MDP approach is used to establish structure properties of the optimal control policy. In particular, we show that there exists a threshold L i for each day i of the week, 1) if the ending CTS queue is shorter than L i , the optimal control consists in keeping all the remaining patients waiting for CTS; 2) if the ending CTS queue is longer than L i , the optimal control consists in sending patients to RTS by keeping the number L i of patients in the CTS queue. The contract optimization problem is solved by a two-step approach. First, the long term average cost is approximated by the average cost over a finite horizon and according to a given sample path of patient arrivals. This Monte Carlo approximation of the contract optimization problem is further simplified by relaxing the non-anticipativeness of the feasible control policy. The relaxed Monte Carlo approximation problem is equivalently transformed into a linear program with seven integer-valued variables corresponding to the contract, which can be efficiently solved by any LP solver. The resulting contract is further improved by some local search procedures. Numerical results show that the proposed approach is very efficient and provides solutions very close to real optimum. Sensitivity analysis is performed to show the impact of different problem data on the contract and control policy. Numerical results also show that the relaxed Monte Carlo approximation always leads to a contract which is at most two local moves away from the best contract identified by exhaustive search for small size problems and by multiple runs of our approach for large size problems. Further, except for one instance, the best contract is reached if the exact criterion values of local solutions are used in local search. Experimental results also show that this contract-based MRI examination reservation process can greatly reduce the average delay of stroke patients, but it also leads to some unused CTS and there still exists some "unlucky" patients, who are assigned to RTS and have to wait much longer time than the other stroke patients.

To avoid "unlucky" patients, this chapter also proposes a new reservation process which still makes use of the contract and L-policy. Here, L-policy is used to reserve some RTS for the neurovascular department, rather than some particular patients. Experiments show that this new method can better the distribution of stroke patients' waiting times.

Chapter 4 considers the possibility of one-day advance CTS cancellation in order to reduce the unused CTS ratio. For each given contract, an average-cost MDP approach is proposed to simultaneously optimize patient assignment and CTS cancellation policies. The structure properties of the optimal control policies are established via discounted cost problem. The implementation of the control policies are as follows: First, we show that there exists a threshold L i for each day i of the week, and 1) if the ending CTS queue is shorter than L i , the optimal control consists in keeping all the remaining patients waiting for CTS; 2) if the ending CTS queue is longer than L i , the optimal control consists in sending patients to RTS by keeping the number L i of patients in the CTS queue. Second, there exists another threshold S i+1 for each day i of the week, and 1) when CTS queue is below S i+1 , the optimal CTS cancellation control consists in making the number of CTS cancelled for day i+1 plus CTS queue length of day i at the threshold S i+1 ; 2) otherwise, no CTS is cancelled.

Based on the optimal control policies, a local search algorithm is proposed to improve the contract. Numerical results show that the proposed approach is very efficient and advance CTS cancellation allows significant reduction of unused CTS ratio with slight increase of waiting time. Sensitivity analysis is performed to show the impact of different problem data on the contract and control policies. Chapter 5 explores the possibility of two-day advance CTS cancellation to help the imaging department better the arrangement of other patients to the time slots released from contract. An average cost MDP is formulated to simultaneously explore the nature of patient Chapter 6 Conclusion 129 assignment, one-day advance cancellation, and the two-day advance CTS cancellation control policies. In particular, we show that the implementation of control policies for day i are as follows: 1) Patient assignment control policy: there exists a threshold L i for each day i of the week and the optimal patient assignment control consists in sending patients to RTS by keeping the CTS queue length plus the two-day advance CTS cancellation for day i the same with L i ; otherwise no patients are assigned to RTS.

2) One-day advance CTS cancellation control policy: there exists a threshold S i+1 and the optimal one-day advance CTS cancellation control consists in making the number of oneday advance CTS cancellation for day i+1 plus the number of two-day advance CTS cancellation for day i+1 plus CTS queue length for day i the same with the threshold S i+1 if the number of two-day advance CTS cancellation for day i+1 plus CTS queue for day i is below S i+1 . Otherwise no CTS is cancelled.

3) There exists a pair of parameters (X i+2 , Y i+2 ) for an approximated two-day advance control. When y, i.e., the number of CTS queue length for day i plus one-day advance CTS cancellation for day i+1 plus two-day advance CTS cancellation for day i+1, is smaller than a certain value Y i+2 , the two-day advance cancellation control for day i+2 is the same, i.e., X i+2 ; When y is greater than Y i+2 , and less than X i+2 + Y i+2 , the two-day advance cancellation control for day i+2 consisting in making y plus the number of two-day advance cancellation for day i+2 the same with X i+2 + Y i+2 ; when y is greater, the two-day advance cancellation is zero.

Local search is proposed to improve the contract decision. Numerical experiments are performed to compare the performance of one-day advance CTS cancellation, two-day advance CTS cancellation, and local optimization. Results show that two-day advance CTS cancellation and Local optimization can reduce the objective criteria and improve the performance.

Starting from the perspectives of neurovascular department, this thesis proposes a contractbased MRI examination reservation process for stroke patients. Contracts and control policies are determined in this thesis. The use of contract gives a long term view of diagnostic capacity available and the neurovascular department can better manage the priority of its stroke patients and reduce the waiting times for examinations. From the perspective of the imaging department, although the use of contract potentially leads to unused time slots, it also gives the imaging department stable demands which can be used to improve staff scheduling and diagnostic facility scheduling. Another advantage of contractbased approach is the possibility for the neurovascular department to better match different diagnosis examinations of the same patient and available contracted CTS for different facilities. The control policies can help in reducing patients' average delay without degrading the utilization of MRI scanners.

This method can be directly applied to the hospital with the existing patient scheduling method, such as FIFO. However, there are still a lot of works to do if we want to better the distribution of patients' waiting times and reduce the variances. In addition, we do not recommend the contract-based approach for all departments but only for critical diagnostic facilities and for some major consumers with stable demands. Results of this paper can be directly used to design separately the contract for each department for each critical facility.

If this leads to the over-usage of diagnosis facility, the contract of each department can be refined by limiting the number of time slots to contract each day and all results of this thesis still hold. The relation between different medical departments is not addressed in this thesis but is crucial for implementing the contract-based approach in a hospital. The joint design of contract-based solutions of several departments raises some fundamental questions such as (i) how many time slots of a diagnostic facility to contract and (ii) how to share these time slots among different departments. Results about the optimal control policies of this paper can be extended to evaluate a contract solution. However new approaches are needed to coordinate the contracts for different departments.

In addition, the form of the optimal contract is still an open issue even for purely stationary demand. It is unclear how to determine the optimal contract if Assumption 4 is relaxed.

Extension to non stationary patient arrival case is one interesting research avenue. Another immediate extension is the development of real time control strategies for advance cancellation of CTS in case of short CTS queue. Management of multiple classes of patients and multiple imaging examinations is a natural but challenging research direction.

From the service provider perspective, how to optimize the operational efficiency of the imaging department by taking into account different quality requirements of medical units is a rich research area. This research is motivated by our collaborations with a large French university teaching hospital in order to reduce the Length of Stay (LoS) of stroke patients treated in the neurovascular department. Quick diagnosis is critical for stroke patients but relies on expensive and heavily used imaging facilities such as MRI (Magnetic Resonance Imaging) scanners. Therefore, it is very important for the neurovascular department to reduce the patient LoS by reducing their waiting time of imaging examinations.

From the neurovascular department perspective, this thesis proposes a new MRI examinations reservation process in order to reduce patient waiting times without degrading the utilization of MRI. The service provider, i.e., the imaging department, reserves each week a certain number of appropriately distributed contracted time slots (CTS) for the neurovascular department to ensure quick MRI examination of stroke patients. In addition to CTS, it is still possible for stroke patients to get MRI time slots through regular reservation (RTS).

This thesis first proposes a stochastic programming model to simultaneously determine the contract decision, i.e., the number of CTS and its distribution, and the patient assignment policy to assign patients to either CTS or RTS. To solve this problem, structure properties of the optimal patient assignment policy for a given contract are proved by an average cost Markov decision process (MDP) approach. The contract is determined by a Monte Carlo approximation approach and then improved by local search. Computational experiments show that the proposed algorithms can efficiently solve the model. The new reservation process greatly reduces the average waiting time of stroke patients. At the same time, some CTS cannot be used for the lack of patients.

To reduce the unused CTS, we further explore the possibility of the advance cancellation of CTS. Structure properties of optimal control policies for one-day and two-day advance cancellation are established separately via an average-cost MDP approach with appropriate modeling and advanced convexity concepts used in control of queueing systems. Computational experiments show that appropriate advance cancellations of CTS greatly reduce the unused CTS with nearly the same waiting times. Afin de réduire le nombre de CTS inutilisé, nous explorons ensuite la possibilité d'annuler des créneaux CTS un ou deux jours en avance. Une approche de processus de décision markovien est de nouveau utilisée pour prouver les propriétés et la forme de la politique optimale d'annulation. Les expérimentations numériques montrent que l'annulation avancée des créneaux CTS permet de réduire de manière importante les créneaux CTS inutilisés avec une augmentation légère des délais d'attente.

FIG. 1 . 1

 11 FIG. 1.1 Photos for ischemic and hemorrhagic stroke ............................................................. FIG. 1.2 The photo for MRI scanner ........................................................................................ FIG. 1.3 Pathway of stroke patients ......................................................................................... FIG. 1.4 Historical data collected from the neurovascular department.................................... FIG. 3.1 The optimal control if z t <=n t ................................................................................... FIG. 3.2 The optimal control if n t =<z t <= L t +n t ................................................................... FIG. 3.3 The optimal control if z t >= L t +n t ............................................................................ FIG. 3.4 Gap of LB(a) for different c.....................................................................................

  FIG. 3.5 Gap of LB(a) for different T R ................................................................................... FIG. 3.6 Waiting time distribution of the base case ............................................................... FIG. 4.1 The optimal patient assignment control if z t <=n t .................................................... FIG. 4.2 The optimal patient assignment control if n t =<z t <= L t +n t ..................................... FIG. 4.3 The optimal patient assignment control if z t >= L t +n t ............................................. FIG. 4.4 The optimal one-day advance CTS cancellation control if x t <= S t+1 ...................... FIG. 4.5 The optimal one-day advance CTS cancellation control if x t <= S t+1 ...................... FIG. 4.6 Criterion values vs cancellation costs b ................................................................... FIG. 4.7 Criterion values vs unused CTS costs c ................................................................... FIG. 4.8 Criterion values vs patient arrival rates.................................................................... FIG. 5.1 The optimal patient assignment control if z t <=n t .................................................. FIG. 5.2 The optimal patient assignment control if n t =< z t <= L t + n t -w 2 t .......................... FIG. 5.3 The optimal patient assignment control if z t >= L t + n t -w 2 t ................................... FIG. 5.4 The optimal one-day advance CTS cancellation control if x t + w 2 t+1 <= S 1 t+1 ....... FIG. 5.5 Approximated two-day advance CTS cancellation control policy ........................ FIG. 5.6 Average costs vs two-day advance cancellation costs b 2 ....................................... FIG. 5.7 Average costs vs different two-day advance cancellation costs b 1 ........................ FIG. 5.8 Average costs vs different unused CTS costs c ..................................................... FIG. 5.9 Average costs vs different RTS delays T R ............................................................. FIG. 5.10 Average costs vs different patient arrival patterns...............................................

FIG. 1 . 1

 11 FIG. 1.1 Photos for ischemic and hemorrhagic strokePhotos from (http://www.strokegenomics.org/index.php?page=about-stroke-genetics).

FIG. 1 . 2

 12 FIG. 1.2 The photo for MRI scannerPhoto from http://www.magnet.fsu.edu/education/tutorials/magnetacademy/mri/.

  , … where n t = n d(t) and P t+1,a = P d(t+1),a are shorthand notation with d(t) denoting the corresponding weekday or weekend with d(0) = 7, d(-1) = 6, … As a result, (

  8.10.7 of Puterman (1994), as the control constraint set for each state (i, z) is finite as a result of Assumption 3-A1, (a) and (b) of the Theorem hold. Further ψ(i, z) z). From equations (3.13) and(3.23), ψ (i, z) is convex in z and (c) of the Theorem can be proved as for

4 . 6 .

 46 Let n* = n0; F n* = F n0 ; 5. Determine the neighbor solution n' with the smallest average cost as follows: Determine the optimal control policy L(n') and the optimal average cost F n' as inStep 3 if necessary;7. If F n' < F n* , set n* = n' and go to step 5.

  12 13 13 11 12 12 TAB 3.2 Optimal solutions of Cases 1-2 by exhaustive search

Fig. 3 .

 3 4 and Fig. 3.5 shows the deviation gap between LB(a) and F n*,L(n*) (a) where n* is the optimal contract obtained by exhaustive search, i.e. (F n*,L(n*) (a) -LB(a))/F n*,L(n*)

  FIG. 3.4 Gap of LB(a) for different c

6

 6 FIG. 3.6 Waiting time distribution of the base case

Theorem 4 - 4 .

 44 Under Assumptions 4, and 4-A2, (a) there exists a constant λ satisfying (4.24) for all (i, z), a matrix H(i, z) satisfying (4.25)-(4.26), (b) the optimal control policy is defined by the argument that reaches the minimum in (4.26), (c) there exists an optimal stationary control policy of the form of equations (4.15)-(4.16)for the average cost model.

2 .

 2 Let n* = n 0 ; J(n * ) = J(n 0 ); 3. Determine the neighbor solution n' with the smallest average cost as follows: J (n ' ) < J (n * ), set n* = n' and go to step 3; 5. The final contract is n* and the final control policy is π(n * ) and μ(n*).

  All numerical experiments are performed on a Intel(R) Core (TM)2 Duo CPU T7250 based PC running at 2.00 GHz with 3.0 GB of Memory. The optimal control policies for the MDP formulation (4.1) are obtained by solving LP model with CPLEX 11 solver. The numerical experiments are all derived from the base case corresponding to our real case study. From the data collected from the neurovascular department of our study, the average Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 77 numbers of patient arrivals during the week are as follows: {1, 0.89, 0.95,1.16, 1.53, 0.16, 0.05}. The number of patients arrived each day is assumed to follow a Poisson distribution truncated at A = 20 which is large enough such that the probability of a i > A can be neglected. The waiting time for RTS varies from 30 to 40 days with an average of T R = 35 days. The weighting factor of unused CTS is set to c = 15. CTS cancellation cost is taken as half of c, i.e. b = 7.5.

Fig. 4 . 7

 47 Fig.4.7 compares the criterion values of different solution strategies for different unused CTS cost c. It is clear that the unused CTS cost has great impact on the contract and the control policies in all solution strategies. When c is very small and close to 1, CTS cancellation only provides marginal improvement. CTS cancellation brings larger improvement when c is large with 9.3% improvement of "Cancel" over "NoCancel" for c = 15 and 15.3% improvement for c = 20. Local Optimization further improves the contract and the control policies. The combined improvement over the "NoCancel" strategy reaches 19.2% for c = 20.

  FIG. 4.8 Criterion values vs patient arrival rates

  d(t): day in the week of day t with d(t)∈{1, …,7}; Data: T R : average number of waiting days for a patient to have his/her MRI examination through regular reservation with T R > 1; c: penalty factor of an unused CTS. It serves as a weighting factor in order to balance the average waiting time and unused MRI time slots; b 1 : penalty factor of canceling one CTS in advance of one day with b 1 < c; b 2 : penalty factor of canceling one CTS in advance of two days with b 2 < b 1 ;

Chapter 5

 5 Contract planning and two-day advance cancellation of contracted time slots 91

  planning and two-day advance cancellation of contracted time slots 101

  Condition C3 is guaranteed by Property 5-11 with K = -M. Condition C4 is a consequence of Property 5-11 with W(i, z, w) = M + rz. Q.E.D.

Chapter 5

 5 Contract planning and two-day advance cancellation of contracted time slots 111

2 .

 2 Let n* = n 0 ; J(n * ) = J(n 0 ); 3. Determine the neighbor solution n' with the smallest average cost as follows: J (n ' ) < J (n * ), set n* = n' and go to step 3; 5. The final contract is n* and the final control policy is π(n * ) and μ(n*).

  FIG. 5.5 Approximated two-day advance CTS cancellation control policy

  FIG. 5.12 Two-day advance CTS cancellation policy for "Two-day-cancel" solution

  Geng and Zhibin Jiang, The capacity planning for wafer fabrication based on an improved stochastic-programming, Journal of Shanghai Jiao Tong University, 41(5), 2007: 825-829. (EI No.: 072710691929) (In Chinese); 11. Na Geng and Zhibin Jiang, Capacity planning for semiconductor wafer fabrication with uncertain demand and capacity, Proceedings of the 3rd Annual IEEE Conference on Automation Science and Engineering, Scottsdale, AZ, USA, Sept 22-25, 2007: P100-105; 12. Na Geng and Zhibin Jiang, A review on medium term capacity planning for semiconductor wafer fabrication, IEEE International Conference on Systems, Man and Cybernetics, Montreal, QC, Canada, 7-10 Oct. 2007: 680, MRI exams (Magnetic Resonance Imaging), Contract, Advance cancellation, Markov decision process, Stochastic programming, Optimal strategies Abstract:

École

  Planification, examens IRM, Contrat, Annulation, Processus de décision markovien, Programmation stochastique, politiques optimales Résumé : Cette thèse propose un nouveau processus de réservation d'examens IRM (Imagerie par Résonance Magnétique) afin de réduire les temps d'attente d'examens d'imagerie des patients atteint d'un AVC (Accident Vasculaire Cérébral) soignés dans une unité neurovasculaire. Le service d'imagerie réserve chaque semaine pour l'unité neurovasculaire un nombre donné de créneaux d'examens IRM appelés CTS afin d'assurer un diagnostic rapide aux patients. L'unité neurovasculaire garde la possibilité de réservations régulières appelées RTS pour pallier les variations des flux de patients. Nous donnons d'abord une formulation mathématique du problème d'optimisation pour déterminer le nombre et la répartition des créneaux CTS appelée contrat et une politique d'affectation des patients entre les créneaux CTS ou les réservations RTS. L'objectif est de trouver le meilleur compromis entre le délai d'examens et le nombre de créneaux CTS non utilisés. Pour un contrat donné, nous avons mis en évidence les propriétés et la forme des politiques d'affectation optimales à l'aide d'une approche de processus de décision markovien à coût moyen et coût actualisé. Le contrat est ensuite déterminé par une approche d'approximation Monté Carlo et amélioré par des recherches locales. Les expérimentations numériques montrent que la nouvelle méthode de réservation permet de réduire de manière importante les délais d'examens au prix des créneaux inutilisés.

  t =f t (x t-1 +a t ): IN→IN: number of patients directed to RTS at the end of day t, who will have an average delay of T R days for the MRI examination. f t (x t-1 +a t ) is the unknown function of the total number of patients after new arrival.The sequence of events during each day t is as follows. First, the CTS queue length x t-1 at the beginning of the day is known. The number a t of new incoming patients during the day becomes known. MIN{n t , x t-1 + a t } patients are served by the n t CTS of the day and MAX{0,

		c: penalty factor of an unused CTS. It serves as a weighting factor in order to balance
		the waiting time and unused MRI time slots;
		a t : number of patients arrived in day t. By assumption 3, daily arrivals a t for t ∈ IN are
		mutually independent random variables and weekly arrivals (a 7j+1 , a 7j+2 , …, a 7j+7 )
		are identically distributed for all j = 0, 1, …. As a result, the arrival process is
		characterized by probability matrix P = [P ij ] for i = 1, …, 7 and for all j ≥0 with P ij
		denoting the probability of j arrivals in day i;
	Decision variables:
		n t : number of CTS of day t;
		x t : number of patients waiting for CTS at the end of day t, which is also called CTS
		queue, 0 x is a given constant. Note that x t does not include patients that are directed to
		RTS.
	n t -x t-1 -a t } CTS cannot be filled. y t = f t (x t-1 + a t ) patients are directed to RTS and will
	have the MRI examination after an average delay of T R days. The number x t =MAX{0, x t-1
	:
	t:	the index of days, t=1,…,T;
	i: the index of days in one week, i=1,…,7, denoting Monday, …, Sunday; note that
		the day i±j is the day in one week of j days after or before day i. For example, 1+1
		is 2, i.e., Tuesday, and 1-1 is 7, i.e., Sunday.
	d(t): the day in the week corresponding to day t with d(t)∈{1, …,7};
	Data:
	T R : average number of days for a patient to have his/her MRI examination through
	regular reservation process with T R > 1;

y

  t is x t = π t (h t ) with 0≤x t ≤

		The objective is to minimize over all history-dependent policies π={π 1 ,π 2 ,...} the following
		long-run average cost
								( ) , J i z π	=	lim T →∞	1 T	E	⎧ ⎨ ⎩	T i t i + = ∑	g	( ) d t	(	) z x z z , t t i =	⎫ ⎬ ⎭	(3.5)
		for any given initial state z i = z with i = 1, …7 where	g	( ) d t	(	) z x is the cost incurred in day , t t
		t with
					g	( ) d t	(	, z x t t	) ( c n d t ( )		t z	)	t x T	R	(	( ) d t z n t	)	t x
	(	t z n t -	)	+	. This definition of control policy is equivalent to that of relation (3.2) as a result
	of relations (3.2)-(3.3).

  The number of patients arriving in any day is bounded from above by M, i.e. a t ≤M for some given positive integer M.

	Assumptions 3-A1 and 3-A2 imply that t z is bounded from above by max z	R M T n = +	*	.
	Therefore,	( g z x , t t t	)	is	bounded	from	above	and

Assumption 3-A2:

  Case 3: If z t is greater than the values of n t + L t , then the number L t of patients are kept in the CTS queue and the remaining patients are assigned to RTS.

	If z t >=L t +n t
	CTS queue after
	new arrival z t	New arrival a t	CTS Nb. n t
	CTS queue x t-1	y t : nb of RTS assignment
			L t : CTS queue length
	CTS queue x t-1 New arrival a t CTS queue after new arrival z t	CTS Nb. n t x time Day t
			time
		Day t

3.1 The optimal control if z t <=n t Case 2: If z t is between the values of n t and n t + L t , then all the number z t -n t of remaining patients are kept in the CTS queue and no patients are assigned to RTS. t : CTS queue length If n t =<z t <=L t +n t No patients will be assigned to RTS. FIG. 3.2 The optimal control if n t =<z t <= L t +n t FIG. 3.3 The optimal control if z t >= L t +n t

Remark 3-5:

The implementation of contract-based MRI examination reservation process needs both the control policy and patients scheduling methods. The control policy is used to reduce the average criterion value, while patients scheduling is used to reduce the variance of patients waiting time. This part of research does not consider patients scheduling. More work is needed to explore the scheduling method which can better the distribution of patients' waiting times.

  and (3.34) can be made linear. Note that reducing variables u t leads to the reduction of both x t and y t , which results in the reduction of the criterion value. Thus, constraints(3.32) and(3.34) can be replaced by the following equivalent constraints:

	( u n a x t t t t ≥ -+	1 -	) and	t u	≥	0	t ∀ =	1,...,	T	(3.37)
	t u n x t t ≥ -	1 and -	t u	0 ≥ ∀ = + t T	1,...,	T D +	(3.38)

  .1.

	Average number of patients arrived Mon. Tues. Wed. Thurs. Fri. Sat.	Sun.	T R	C
	1	0.89	0.95	1.16	1.53 0.16 0.05	35	15
				TAB 3.1 Base case data

  sample path a needed for the Monte Carlo optimization is generated on a time horizon of 1000 weeks, i.e. T=7000 days, nearly 20 years. The number of patients arrival t a for t=1, …, 7000 is generated according to a Poisson distribution truncated at 20, 40, and 60 for respectively low, medium, and high demand instances. D = 100 extra days are used in the Monte Carlo approximation to determine waiting time of patients in the queue at the end of the planning horizon. Model 3-2 is solved by restricting the queue length x t to a given parameter LL set by trial-and-error. LL = 30, 40, and 40 for low, medium, and high demand instances. We also use very long-time simulation for the evaluation of different performance measures of final contracts and control policies determined by exhaustive search for low demand instances and by optimization algorithms for medium and high demand instances.

Table 3 .

 3 4 summarizes results of Algorithms 1 and 2 for the same cases. For each problem instance, each algorithm is applied 10 times with 10 different sample paths. Let n1 and n2 be the contract provided by respectively Algorithms 1 and 2. Columns "F nk " give the minimum, average, and maximum of the exact criterion values of contract nk of 10 different runs of Algorithm k, where k=1, 2. Columns "Gapk" show the minimum, average, and maximum of the average deviations of F nk from F*, i.e. (F nk -F*)/F nk . Columns "Movek" are the minimum, average, and maximum of local search moves in Algorithms k. RT1 and RT2 are the average CPU time. The optimal contract is always found by Algorithm 1 except for the instance c = 1 for which the 10 criterion values of Algorithm 1 are all within 1% of the optimum. Results in column "Move1" show that the contract of the Monte Carlo approximation is close to the optimum as the optimal contract can be obtained with less than 2 local moves. Recall that, from Remark 3-6, Algorithms 1 and 2 actually start from the same Monte Carlo solution for each of the 10 sample paths. Results of Algorithm 2 are good with average deviation from the optimum of less than 2.2% and with a deviation of about 11% for one run of c = 15. However the CPU time of Algorithm 2 is much smaller than that of Algorithm 1. From Table3.4, Algorithm 2 is at least six times faster than Algorithm 1. The quality of the best solution of six independent runs of Algorithm 2 is fairly close to that of Algorithm 1 of one run.

	T R c	F n1	F n2	Gap1(%)	Gap2(%)	Move1 Move2 RT1(s) RT2(s)
	35 1 [0.945,0.947,0.948] [0.945,0.951,0.982] [0,0.20,0.32] [0,0.53,3.70] [0,0.1,1] [0,0,0]	126	7
	35 5 [2.484,2.484,2.484] [2.484,2.504,2.671]	[0,0,0]	[0,0.77,7.02] [0,0.7,2] [0,0.3,2] 190	13
	35 10 [3.589,3.589,3.589] [3.589,3.592,3.604]	[0,0,0]	[0,0.08,0.43] [0,0.3,1] [0,0.1,1] 140	11

Table 3 .

 3 6 summarizes average delay time, unused CTS ratios, and RTS percentages for different arrival patterns. These performance measures seem to be insensitive to the change of patient arrival pattern. Table3.7 presents results of Algorithms 1 and 2 for the same cases. The same observations can be made as in Section 3.5.2. CPU Time (s) n 1 n 2 n 3 n 4 n 5 n 6 n 7 L 1 L 2 L 3 L 4 L 5 L 6 L 7

	Peak arrival	F*
	Mon.	4.506	9274	2 1 1 1 2 0 0 10 10 11 11 10 10 11
	Tues.	4.496	9277	1 2 1 1 2 0 0 11 10 10 11 10 10 11
	Wed.	4.487	9332	1 1 2 1 2 0 0 11 11 10 11 9 10 11
	Thurs.	4.476	9283	1 1 1 2 2 0 0 11 11 11 10 9 10 10
	Fri.	4.501	9189	1 1 1 1 3 0 0 11 11 11 11 9 10 10
	Ave.	4.517	9246	1 1 2 1 2 0 0 11 11 10 11 10 10 11
	TAB 3.5 Optimal solutions of different patient arrival patterns by exhaustive search
		Peak arrival Delay(days) Unused CTS Ratio (%)	RTS Perc.(%)
		Mon.		2.16	18.19	0.24
		Tues.		2.16	18.20	0.26
		Wed.		2.16	18.18	0.28
		Thurs.		2.13	18.20	0.27
		Fri.		2.16	18.22	0.26
		Ave.		2.13	18.59	0.22
	TAB 3.6 Performances of contract-based reservation process for different patient arrival patterns

Table 3 .

 3 10 summarizes average delay, unused CTS ratios, RTS percentages for different patient arrival rates with the best contract decisions obtained. All the performance measures decrease when the arrival rate increases.

	Arrival rates	Delay(days)	Unused CTS Ratio (%)	RTS Perc. (%)
	Low	2.16	18.22	0.26
	Medium	1.16	7.68	0.24
	High	0.74	6.01	0.11

TAB 3.10 Performances of contract-based reservation process for different patient arrival rates

  t-1 is known. The number of CTS for day t is n t . The number of new arrival patients in day t is a t . The state variable z t = x t-1 + a t is known. MIN{n t , x t-1 + a t } patients are served by the CTS of the day and u t = (n tz t ) + CTS of day t cannot be filled and are unused. y t = (z tn t -L t ) + new incoming patients with L t = L d(t) are directed to RTS. x t = (z tn ty t ) + remaining patients will wait for CTS in the subsequent days. Patients in CTS queue are served in FIFO order. The average cost of the old reservation process is as follows:

1 1 lim

  The number of time slots available in day t including both CTS and RTS is Chapter 3 Contract planning and patient assignment control policy In order to compare the two control policies, the following notation is needed: : number of patients waiting for a time slot in the old reservation process including both those in the CTS queue and those sending to the RTS but not yet served.

			old t u Property 3-9: t u = : number of unused CTS in old reservation process 1 1 1 1 lim lim T T old new t t T T t t u u T T →∞ →∞ = = = ∑ ∑ .
			R y : number of patients sending to RTS t old t t s s t T x x y = -t Proof: By definition, 1 s = + ∑ old t 0 old t x x	a	s	1 R tT s	y	old s	s	t	1	(	s n u	old s	)
			new t y : number of RTS reserved
	Property 3-7:	old t y	=	new t y	, y t t = ∀ .
	old t y	=	new t y	0, = ∀ ≤ . By patient assignment policy, 0 t	, x L t t t ≤ ∀ >	0	and hence
	t y	=	(	t x	1 -	t a n L t t + --	)	+	≤	t L	1 -	, a t t + ∀ > is a finite random variable. As a result, 1
														J	old	=	lim T →∞	1 T	1 = T ∑ t	⎡ ⎣	old t c u	+	old t x	⎤ ⎦
	Property 3-8:	old t x	≥	new t x	,	0 ∀ ≥ . t
	and	1 new t x -x -+ a t } patients have their MRI exam by CTS time slots . The number new incoming patients during day t is a t . MIN{ new { } 1 , t t t MIN n x a -+ t n , 1 new t y -patients by RTS time slots. Hence, with 0 0 new x x = . R new t t t T n n y -= + R old t T
					patients are served by the CTS and RTS of the day and of day t cannot be filled. The remaining ( 1 new new t t x x -= + -new t u t a n = new ( n t new ) t + { } { 1 1 , R old old old t t t t t t t T x x a MIN n x a y --= + -+ --} 1 1 1 , R R old old old old t t t t t t T t T MAX x a n y x x y -----= + ----	( patients will wait in the ) ) 1 new t t x a + --+ time slots
	patient queue. Patients are served in FIFO order. The average cost of the new reservation For the new reservation process,
					process is as follows:	new t x	=	{ MAX x t new 1 -	R new t T a n y t t -+ --	} , 0
	1 = T ∑ t Combining with Property 3-7, the induction assumption and the fact of 1 1 lim new new new t t T J c u x T →∞ ⎡ ⎤ = + ⎣ ⎦ old t x -	≥	t x	1 -	+	old t T y -	R	,
	Both new and old reservation processes are characterized by a contract n and a set of control the above two relations lead to old new t t x x ≥ which completes the proof. Q.E.D.
					thresholds L.

Proof: Trivial and follows from the definition. Q.E.D.

For simplicity, let us assume that there is no pending RTS reservation initially, i.e.

Proof: This property is proved by induction. The property clearly holds for t = 0. Assume that it holds for t-1. We now prove it for t. First, for the old reservation process and for day t, a t new patients arrive.

  The maximum waiting time of the new reservation process is smaller or equal to T R if the thresholds L t are such that

						old t x	-	new t x	=	1 = t ∑ s	u	old s	-	1 = t ∑ s	u	new s
	which proves the property if both old t x and new t x are finite numbers. The finiteness of old t x is
	true as t x L t ≤ ,	t y L t ≤	1 -	t a + and	old t x	t x = +	t s t T = -∑	R	y	s	≤	(	T	R	+	) 1 * L	+	R ∑ . The finiteness of t s s t T a = -
	new
	t
	Property 3-10: old J	≥	J	new	.
	Remark 3-8: From the proof of Property 3-8, more patients can be served by CTS time slots
	in the new reservation process and hence old t x when n 1 new t x > 1 0 t t old new s s s s u u = = -≥ ∑ ∑ . The new reservation process has less time slot cancellation even
	though the average cancellation rate is the same.
	Property 3-11: 1 R t T t s t L + = + ≤ ∑ and s n	t L n t -	1 +	≤	t L	1 +	.

x follows from Property 3-8. Q.E.D.

Proof: Direct consequence of Properties 3-9 and 3-10. Q.E.D. t > x t-1 + a t . In this case, in the old reservation process, CTS queue does not contain enough patients to fill all CTS time slots and patients directed to RTS cannot be redirected. In the new reservation process, as no patients are directed RTS, these extra CTS time slots can be filled by patients that were directed to RTS in the old reservation process.

Remark 3-9:

From the proof of Property 3-8 and the proof of

  and D new correspond to average patient waiting times in old and new contract-based reservation process.

						R new t T x +	1 R = + t T s t + > ∑	a	s
	Further, for the old reservation process, as	old t x	R = + ∑ and x t ≤ L t , the conditions of t t s s t T x y = -
	the property ensure that all patients in old
						old t T x +	R	1 R = + t T s t + ≤ ∑	a	s
	Property 3-12: old D where D Proof: Since both policies face the same patient arrival rate and both old new D ≥ t x and new t x are
	finite, by Little's law,
	lim T	1 T	t	T	1	old t x		D	old	lim T	1 T	t	T	1	t a

t x have been served by time t + T R . As a result, which contradicts Property 3-8 and concludes the proof. Q.E.D. old

  Contract planning and one-day advance cancellation of contracted time slots 61 characterized by probability matrix P = [P ij ] for i = 1, …, 7 and for all j ≥0 with P ij denoting the probability of j arrivals in day i; n t : number of CTS in day t;

	Chapter 4 Decision variables are:
	x t : number of patients waiting for CTS at the end of day t, which is also called CTS
	queue, 0 x is a given constant. Note that x t does not include patients that are directed to
	RTS.
	w t : number of CTS for day t+1 cancelled at the end of day t; w 0 is known;
	State variable:
	z t = w t-1 + x t-1 + a t z n t
	c: penalty factor of an unused CTS. It serves as a weighting factor in order to balance
	average waiting time and unused MRI time slots;
	b: penalty factor of canceling one CTS with b < c;
	a t : number of patients arrived in day t. By assumption 3, daily arrivals a t for t ∈ IN are
	mutually independent random variables and weekly arrivals (a 7j+1 , a 7j+2 , …, a 7j+7 )
	are identically distributed for all j = 0, 1, …. As a result, the arrival process is

Assumption 4-A1: CTS of day t can be cancelled in advance of one day, i.e., at the end of day t-1.

Based on the above assumptions, the problem of patient assignment and advance CTS cancellation can be characterized by the following notation: Indices: t: index of days, t=1,…,T; i: index of days in one week, i=1,…,7, i.e., Monday, …, Sunday; note that the day i±j is the weekday of j days after or before day i in one week; d(t): the day in the week corresponding to day t with d(t)=t(mod)7+1∈{1, …,7}; Data:

T R : average number of days for a patient to have his/her MRI examination through regular reservation with T R > 1; t : number of CTS to be consumed in day t.

The sequence of events during each day t is as follows. First, the queue length x t-1 for CTS is known at the end of day t-1, and the number w t-1 of CTS canceled for day t is determined. During day t, the number a t of new incoming patients during the day becomes known. The state variable z t is known. MIN{ n tw t-1 , x t-1 + a t } patients are served by the remaining CTS of the day and MAX{0, n tz t } CTS of day t cannot be filled. x t patients will wait for CTS of the subsequent days. MAX{0, z t -n tx t } remaining patients are directed to RTS and will have the MRI examination after an average of T R days.

There are two control policies in this problem: CTS cancellation and patient assignment policies. History-dependent policies are considered in this chapter. Let h t = (z i , x i , w i , …, z t-1 ,

x t-1 , w t-1 , z t ) be the full history stating from initial state z i at the beginning of day i. We denote the patient assignment policy by π={π 1 ,π 2 ,...}, where the CTS queue length at the end of day t is x t = π t (h t ) with 0≤x t ≤ ( ) + -, and the CTS cancellation policy by µ={µ 1 , µ 2 ,…}, where the number of CTS cancelled for day t+1 at the end of day t is w t = µ t (h t ) with 0≤w t ≤(n t+1 -x t ) + .

The objective is to minimize over all history-dependent policies µ={µ 1 , µ 2 ,…} and π={π 1 ,π 2 ,...} the long-run average cost

  Contract planning and one-day advance cancellation of contracted time slots is the stage cost, i.e., CTS cancellation cost plus unused CTS penalty plus waiting time for CTS and RTS. In the following, g d(t) (.) are written as g t (.) for convenience.

	62 Chapter 4
	g	d t	, , t z x w t t	=	t bw c n d t +	-	z	t	+	R x T z n t t d t + + -	-	t x	+

  [START_REF] Na | MRI Reservation for Neurovascular Patients[END_REF]

	t U z U z t t t -	-≥ +	α	∑	t a P +	U	t	+	t x w a U t + + -	t	+	t x w a t + + -	.
				a
	By induction assumption,

  68 Chapter 4 Contract planning and one-day advance cancellation of contracted time slotsThe combination of Assumptions 4-A2 and 4-A3 implies that the state variable z t is upper bounded and:

				t z z x A ≤ ≡ +	(4.17)
	as	t x w t + ≤	1 max( , ) t t x n +	x ≤ . As a result, under Assumptions 4-A2 and 4-A3, the stage cost
	function is also bounded with
				( g z x w , , t t t t	)	( B b c n T z ) * R ≤ ≡ + +	(4.18)
	Property 4-4: There exists M>0 such that

  Since z t ≤z + a i+1 + w i +…+ a t + w t-1 ≤z + a i+1 + n i+1 +…+ a t + n t , for t > i,

			Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 71
			From (4.4),
													( ) , U i z m T z E U i ( R α α ≤ + + ⎡ ⎣	+	1 ,	z	i	1 +	)	⎤ ⎦	(4.35)
			Repeat the relations (4.35) for t subsequent days leads to:
				( ) , U i z α	≤	1 + -t i i τ = ∑	(	[ ] m T E z R τ +	)	+	( E U t i z , α + ⎡ ⎣	t i +	)	⎤ ⎦	,	i ∀ =	1,..., 7	(4.36)
			Combining (4.34) and (4.36) with t+i=7,
				( ) , U i z α	≤	7 τ = ∑ i	(	[ ] m T E z R τ +	)	+	( U	α	( ) 7, 0	( m T z a 6 * , ) ) R + + +	i ∀ =	1,..., 7	(4.37)
					( ) ,			7		49	* 7	(	6 *	)	( ) 7, 0
												8		55	* 8	( ) 7, 0 ,	1,..., 7
																.34)
	Consider now the case i = 1, …, 6. First,
	0	≤	( g z x w , , t t t t	) ( c n z t = -	t	)	+		( x T z n x R t t t t + + --	)	+	+	t bw	( ≤ + b c n T z m T z ) * R R t t + ≤ +	.

  and 72 Chapter 4 Contract planning and one-day advance cancellation of contracted time slots c) for each (i, z) and x i ,

		∑	( P W i 1, i a +	+	1,	) + < ∞ . x a i
		a
	According to Theorem 8.10.7 of Puterman (1994), as the control constraint set for each state
	(i, z) is finite, (a) and (b) of the Theorem hold. Further H(i, z) is the limit of a sequence
	( ) , H i z m α	such that α m converges to 1 and	( ) , H i z m

α converges for all (i, z). From Property

  4.4, if the ending CTS queue at day t is smaller than S t+1 , then the number of CTS cancelled for day t+1 is w t = S t+1 -x t . The optimal one-day advance CTS cancellation control if x t <= S t+1 Case 2: As shown in Fig.4.5, if the ending CTS queue at day t is greater than S t+1 , then there is no cancellation. The optimal one-day advance CTS cancellation control if x t <= S t+1

	Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 75
	If x t <=S t+1
	CTS cancelled for day t+1:
	w t = S t+1 -x t	S t+1
	CTS queue: x t
		time
	Day t
	CTS cancellation up to the control threshold S t+1
	Day t FIG. 4.4 time If x t >=S t+1 CTS queue: x t S t+1
	No CTS cancellation
	FIG. 4.5

Table 4 .

 4 1 summarizes the performance measures for the three different solution strategies. With respect to the strategy "NoCancel", the CTS cancellation policy greatly reduces the unused CTS ratio and slightly increases the average delay by CTS cancellation, and at the same time more patients assigned to RTS. The reduction of unused CTS is drastic from 18.22% to about 2% when the cancellation cost b is small. As b increases, less CTS are cancelled and the reduction of unused CTS ratio decreases. The contract "LocalOpt" further takes advantage of CTS cancellation. When b is small, all CTS that cannot be used by patients in CTS queue are cancelled and hence there is no unused CTS. Further, enough CTS are planned and no RTS is used. Table

		5.00
	Criterion Values	1.00 2.00 3.00 4.00							No cancel Cancel LocalOpt
		0.00
		0.1c	0.2c	0.3c	0.4c	0.5c	0.6c	0.7c	0.8c	0.9c
					Cancellation Cost
		FIG. 4.6 Criterion values vs cancellation costs b

  Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 81

		"NoCancel"			"Cancel"			"LocalOpt"
	c	Delay Unused RTS Delay Unused RTS Cancel Delay Unused RTS Cancel
		(days)	(%)	(%) (days)	(%)	(%)	(%)	(days)	(%)	(%)	(%)
	1	0.41	42.60	0.00	0.47	35.38	0.00	7.22	0.52	28.44	0.00 14.17
	5	1.06	28.26	0.00	1.26	15.73	0.00 12.53	1.37	11.45	0.01 16.81
	10 2.14	18.32	0.38	2.27	13.99	0.40	4.34	1.76	3.56	0.00 24.70
	15 2.16	18.22	0.26	3.16	1.58	0.45 16.80	2.97	0.98	0.44 17.38
	20 2.17	18.16	0.18	3.16	1.57	0.39 16.75	2.98	0.98	0.38 17.34
				TAB. 4.3 Performance measures vs unused CTS costs c
	c			"NoCancel"			"Cancel"		"LocalOpt"
		n={2, 1, 2, 2, 2, 1, 0}; 10CTS n={2, 1, 2, 2, 2, 1, 0}; 10CTS n={1, 2, 1, 2, 2, 1, 1}; 10CTS
	1

  .5 and 4.6 are fairly insensitive to the change of T R .

		"NoCancel"			"Cancel"			"LocalOpt"
	T R	Delay Unused RTS Delay Unused RTS Cancel Delay Unused RTS Cancel
		(days)	(%)	(%) (days)	(%)	(%)	(%)	(days)	(%)	(%)	(%)
	25 2.08	18.46	0.56	3.05	1.61	0.92 17.15	2.87	1.01	0.94 17.77
	30 2.13	18.32	0.38	3.11	1.59	0.65 16.95	2.93	0.99	0.65 17.55
	35 2.16	18.22	0.26	3.16	1.58	0.45 16.80	2.97	0.98	0.44 17.38
	40 2.17	18.22	0.26	3.19	1.57	0.31 16.69	2.85	2.65	0.30 15.60
	45 2.20	18.11	0.13	3.21	1.56	0.23 16.63	2.87	2.64	0.21 15.53
				TAB. 4.5 Performance measures vs RTS delay T R
				TAB. 4.7 Contracts and control policies vs patient arrival patterns
			"NoCancel"		"Cancel"			"LocalOpt"
		Peak
		arrival	Delay Unused RTS Delay Unused RTS Cancel Delay Unused RTS Cancel
			(days)	(%)	(%) (days)	(%)	(%)	(%)	(days)	(%)	(%)	(%)
		Mon	2.16	18.19 0.24 3.00	3.23	0.44 15.11	2.90	2.08	0.44 16.27
		Tues	2.16	18.20 0.26 2.98	3.32	0.44 15.03	2.90	2.05	0.44 16.30
		Wed	2.16	18.18 0.28 2.97	3.27	0.44 15.04	2.85	2.41	0.44 15.90
		Thurs	2.13	18.20 0.27 2.94	3.18	0.44 15.16	2.95	1.15	0.46 17.21
		Fri	2.16	18.22 0.26 3.16	1.58	0.45 16.80	2.97	0.98	0.44 17.38
		AVE	2.13	18.59 0.22 2.95	3.58	0.38 15.13	2.80	3.09	0.37 15.62
				TAB. 4.8 Performance measures vs patient arrival patterns

Table 4 .

 4 10.

		"NoCancel"		"Cancel"			"LocalOpt"
	Arrival
	Rate	Delay Unused RTS Delay Unused RTS Cancel Delay Unused RTS Cancel
		(days)	(%)	(%) (days)	(%)	(%)	(%)	(days)	(%)	(%)	(%)
	Low	2.16	18.22 0.26 3.16	1.58	0.45 16.80	2.97	0.98	0.44 17.38
	Medium 1.16	7.68	0.24 1.38	3.36	0.34	4.40	1.14	1.61	0.06	8.78
	High	0.74	6.01	0.11 0.90	2.53	0.16	3.52	0.77	1.85	0.04	5.61
			TAB. 4.9 Performance measures vs patient arrival rates

  The sequence of events during each day t is as follows. First, the following information is known: the queue length x t-1 for CTS at the end of day t-1, the number of two-day advance + a t } patients are served by the remaining CTS of the day and MAX{0, n tz t } CTS of day t cannot be filled. MAX{0, z t -n tx t } patients are directed to RTS and will have the MRI examination after an average of T R days. The remaining x t patients will wait for CTS of the subsequent days. The number of CTS cancelled for day t+1 and day t+2 is determined. + at the beginning of day i. We denote the patient assignment policy by π={π 1 ,π 2 ,...} where the CTS queue at the end of day t is x t = π t (h t ) with 0≤ x t ≤(z t -n t ) + , and one-day advance cancellation control policy by

	90 Chapter 5 Contract planning and two-day advance cancellation of contracted time slots
	the number of CTS cancelled for day t+1 is	1 t w + = 1	μ	1 t	( ) t h	with	0	≤	1 t w + 1	≤	(	t n	1 +	2 t x w t + 1 --	)	+	,
	and the two-day advance cancellation policy by	μ	2	=	{	} , ,... 2 2 μ μ 2 1	where the number of CTS
	1 cancelled for day t+2 is w : number of CTS cancelled for day t in advance of one day, i.e., at the end of day t-1; ( ) 2 2 2 t t t w h μ + = with 2 2 2 0 t t w n + + ≤ ≤ . t 2 t The objective is to minimize over all history-dependent policies { } 1 1 1 1 2 , ,... μ μ = μ , w : number of CTS cancelled for day t in advance of two day, i.e., at the end of day t-2; State variables: { } 2 2 2 1 2 , ,... μ μ = μ and π={π 1 ,π 2 ,...} the long-run average cost
	J	2 t u x w + 1 t t = + CTS cancellation control and new patients' arrival. : number of CTS to be consumed at day t+1 without the one-day advance ( ) ( ) ( )( ) 1 2 1 2 1 2 2 1 1 2 1 , , lim , , , , , t t t t t i i d t T t i i z w E g z w x w w z z w T μ μ π w 1 T i + -
		1 t y u w t t + 1 = +	1 t x w t + 1 = +	+	2 t w + 1		: number of CTS to be consumed at day t+1 without new
		patients' arrival.
		t z y t =	1 -	1 t a x w t t + 1 + = +	+	2 t w + 1	t a + : number of CTS to be consumed at the day t.
	CTS cancellations for day t 2 t w , the number of one-day advance CTS cancellations for day t
	1 t w , and the number of two-day advance CTS cancellations for day t+1 2 t w + . Based on the 1
	above information, state variable	t y	1 -	=	t x	1 -	1 t w w t 2 + +	is also known. During day t, the
	number a t of new incoming patients during the day becomes known. The state variable z t is
	known as y t-1 + a t . MIN{ --, x t-1 There are three control decisions in this problem: one-day advance CTS cancellation, two-1 2 t t t n w w
	day advance cancellation, and patient assignment policies. The state is represented by the
	combination of two variables: (	) z w + . History-dependent policies are considered in this 2 1 , t t
	chapter. Let	t h	=	{	t h	1 -	,	(	(	2 t z w , t + 1	) ( , , t x w w 1 1 , t t 2 + +	2	)	) }	,	0 h	=	( {	2 i z w , i + 1	) ( , , i x w w 1 1 , i i 2 + +	2	) }	be the full
	history by stating from initial state (	) z w { 2 1 , i i 1 = μ	} , ,... 1 2 μ μ 1 1	where

  is the stage cost, i.e., CTS cancellation cost plus unused CTS penalty plus waiting time for CTS and RTS. In the following, g d(t) (.) are written as g t (.) for convenience.

	g	d t	1 t z w x w w 1 1 , , , , t t t t 2 + + +	2	=	1 t bw 1 + 1	+	2 t b w 2 +	2	+	d t c n	-	z	t	+	R x T z n t t d t + + -	-	t x	+

  Chapter 5 Contract planning and two-day advance cancellation of contracted time slots 107 According to Theorem 8.10.7 of[START_REF] Puterman | Markov Decision Processes -Discrete Stochastic Dynamic Programming[END_REF], as the control constraint set for each state (i, z, w) is finite, (a) and (b) of the Theorem hold. Further ψ(i, z, w) is the limit of a sequence

	ψ	α	m	(	, , i z w	)	such that α m converges to 1 and	ψ	α	m	(	, , i z w	)	converges for all (i, z, w). From
	Property 5-2, 5-6, 5-8, and equations(5.7), (5.14), and (5.15), (c) of the Theorem can be
	proved as for Theorem 5-2.
	Let us now prove conditions C1-C4. Condition C1 clearly holds as ( i g z w x w w 1 1 , , , , i i i 2 + +	2	)	0 ≥ .
	Condition C2 holds as well as
	1) as in Property 5-11,	0	( g z w x w w 1 1 , , , , t t t t 2	2	) ( ) 2 b c n T z m T z * R R t	t
															2 i g z w x w w 1 , , , , i i i + +	2	< ∞.
	C2: For each (i, z, w) and α < 1,	( U i z w , , α	)	< ∞ .
	C3: There exists K > -∞ such that, for each (i, z, w 2 ),
								ψ	α	(	) i z w U i z w U ( ) , , , , α ≡ -	α	(	7, 0, 0	)	, ≥ ∀ < K α	1.
	C4: There exists a non-negative function W(i, z, w) such that
	a) W(i, z, w) < ∞;
	b) for each (i, z, w),	ψ	α	(	) i z w W i z w ( , , , , , ) ≤	1 ∀ < ; and α
	c) for each (i, z, w) and 1 i w w 1 , i 2 + + and x i , 1
												∑	( P W i 1, i a +	+	1,	1 i x w i + 1 +	+	2 i w + 1	) + <∞ . a
												a

  ,..., 7

		λ ψ +	i i y b w ≤	+	+	∑	i a P ψ +	i	+	i y a w +	+	i ∀ =
								a
	i x	(	i z n i	)	2 i x x w ,	1	y	max	{	2 i x w n 1 , i	1	}	, 0	2 i w	2	i n	2	,	i	1,..., 7

  Case 2: As shown in Fig.5.2, if state variable z t is greater than n t but smaller than L t + n tw 2 t , then all the remaining patients are kept in the CTS queue and no patients are assigned to RTS. Chapter 5 Contract planning and two-day advance cancellation of contracted time slots 109 FIG. 5.2The optimal patient assignment control if n t =< z t <= L t + n t -w2 The optimal patient assignment control if z t >= L t + n t -w 2 t 110 Chapter 5 Contract planning and two-day advance cancellation of contracted time slotsStep 2: The implementation of one-day advance cancellation control can be divided into two cases:

	Case 1: As shown in Fig. 5.4, if the ending CTS queue at day t plus two day advance
	cancellation for day t+1, w 2	t+1 ,is smaller than S 1 t+1 , then the number of CTS cancelled for
	day t+1 is w 1	t+1 = S 1	t+1 -x t -w 2	t+1 .
			If x t +w 2	t+1 <= S 1 t+1
					CTS cancelled for day t+1: w 1 t+1
					CTS queue: x t	S 1	t+1
				CTS cancelled for day t: w 2 t+1
					Day t	time
				CTS cancellation up to the control threshold S 1 t+1
	FIG. 5.4 The optimal one-day advance CTS cancellation control if x t + w 2	t+1 <= S 1	t+1
	Case 2: If x t + w 2	t+1 >= S 1 t+1 , no CTS is cancelled for day t+1.

FIG. 5.1

The optimal patient assignment control if z t <=n t t Case 3: As shown in Fig.

5

.3, if state variable z t is greater than L t + n t -w 2 t , then the number of patients assigned to CTS is kept at L t -w 2 t , and the other remaining patients are assigned to RTS.

FIG. 5.3

  cancellation. All numerical experiments are performed on a Intel(R) Core (TM)2 Duo CPU T7250 based PC running at 2.00 GHz with 3.0 GB of Memory. The optimal control policies for the MDP formulation(5.1) are obtained by solving LP model with CPLEX 11 solver. The numerical experiments are all derived from the base case corresponding to our real case study. From the data collected from the neurovascular department of our study, the average numbers of patient arrivals during the week are as follows: {1, 0.89, 0.95, 1.16, 1.53, 0.16, 0.05}. The number of patients arrived each day is assumed to follow a Poisson distribution truncated at A = 20 which is large enough such that the probability of a i > A can be neglected. The waiting time for RTS varies from 30 to 40 days with an average of T R = 35 days. The weighting factor of unused CTS, c, is set to 15. CTS one-day advance cancellation cost, b 1 , is taken as half of c, i.e. 7.5. Two-day advance cancellation cost, b 2 , is assumed as half of b 1 , i.e. 3.75.In the following, the impact of CTS cancellation is analyzed with respect to the cancellation cost b 1 , b 2 , unused CTS cost c, delay T R of regular reservation, patient arrival pattern, and the patient arrival rate. The initial contract n 0 is obtained by the method proposed in chapter 4 for optimizing the contract without two-day advance CTS cancellation.112 Chapter 5 Contract planning and two-day advance cancellation of contracted time slots

10,10,10,10,8,9} L={14,14,15,15,15,14,13} n={

	L={10, 10, 10, 11, 10, 8, 9}. L={10,0, 1, 1, 2, 1, 2, 0};7CTS n={0,1

,1,2,1,2,0}7CTS n={0,1,1,1,2,1,2}8CTS S={

	0, 1, 1, 1, 0, 2, 0};	S 1 ={0,0,0,1,0,2,0}	S 1 ={0,0,0,0,1,1,2}
	40	X={0,0,1,1,0,1,0}	X ={0,0,1,1,1,1,2}
		Y={0,0,0,1,0,0,0}	Y ={0,0,0,0,1,1,1}
	L={11, 11, 11, 11, 11, 9, 10}.	L={11,11,11,11,11,9,10}	L={16,16,16,17,16,16,15}
	n={

  Contract planning and two-day advance cancellation of contracted time slotsWe now perform the sensitivity analysis with respect to the patient arrival patterns by exchanging the current peak arrival rate of Friday with the arrival rates of any other weekday. Another arrival pattern (Ave) with equal weekday arrival is also considered. The average cost (see Fig.5.10) and the performance measures (See Table5.9) are also insensitive to the change of patient arrival patterns. "LocalOpt" usually moves one CTS from peak arrival date to one or two days later and one CTS from Saturday to Sunday, at the same time, one CTS is added in Sunday. Therefore, more CTS cancellation and more patient assignment threshold are expected.

	1.00 2.00 3.00 4.00 10 0 2 4 6 8 12 14 Average cost 122 Chapter 5 0.00 Average cost 5.00	One-day-cancel Two-day-cancel LocalOpt High One-day-cancel Two-day-canc el LocalOpt FIG. 5.11 Average costs vs different patient arrival rates Low Medium Arrival rate
			Mon	Tues	Wedn	Thurs	Fri	AVE
					Peak arrival
		FIG. 5.10 Average costs vs different patient arrival patterns
		One-day-cancel		Two-day-cancel	LocalOpt
	Peak arrival	Delay Unused RTS Cancel Delay Unused RTS Cancel Delay Unused RTS Cancel
		(days) (%) (%) (%) (days) (%) (%) (%) (days) (%) (%) (%)
	Mon	2.90	2.08 0.44 16.27 3.07	3.94 0.48 14.43 2.40	2.66 0.01 25.58
	Tues	2.90	2.05 0.44 16.30 3.06	3.38 0.50 15.02 2.39	2.19 0.01 26.06
	Wed	2.85	2.41 0.44 15.90 3.08	3.33 0.51 15.04 2.54	1.57 0.01 26.64
	Thurs	2.95	1.15 0.46 17.21 2.89	3.73 0.46 14.62 2.29	2.90 0.01 25.33
	Fri	2.97	0.98 0.44 17.38 3.05	3.48 0.50 14.94 2.25	3.00 0.00 25.26
	AVE	2.80	3.09 0.37 15.62 3.33	2.35 0.49 16.46 2.32	2.44 0.01 26.17
		TAB. 5.9 Performance comparison for different patient arrival patterns
	Peak arrival	One-day-cancel		Two-day-cancel	LocalOpt
		L={12, 12, 12, 12, 12, 10, 11}. n={1, 1, 1, 1, 1, 2, 0};7CTS n={1,1,1,1,1,2,0}7CTS n={0,1,2,1,1,1,2}8CTS L={12,12,12,11,12,10,11} L={17,18,18,18,18,17,16}
	Mon	S={0, 1, 1, 0, 1, 2, 0}; TAB. 5.8 Contracts and control policies vs RTS delays T R S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,1,0,0,1,2} X={0,0,1,1,1,2,0} X ={0,0,2,1,1,1,2}
					Y={0,0,0,0,0,0,0}	Y ={0,0,0,1,0,1,1}
		L={10,10,10,10,10,9,9}.	L={10,10,10,10,10,9,9} L={15,15,14,15,15,14,13}

Table 5 .

 5 11 summarizes the performance measures for different arrival rates. For all the solutions, the increase of demand rate results in shorter delay, less RTS assignment and less CTS cancellation ratio. Unused CTS ratio increases for "One-day-cancel" policy but decreases for the other solution strategies.

			One-day-cancel		Two-day-cancel	LocalOpt
	Arrival rates	Delay	Unused RTS Cancel Delay Unused RTS Cancel Delay Unused RTS Cancel
		(days)	(%)	(%)	(%) (days) (%) (%) (%) (days) (%) (%) (%)
	Low	2.97	0.98	0.44	17.38 3.05 3.48 0.50 14.94 2.25 3.00 0.00 25.26
	Medium	1.14	1.61	0.06	8.78	1.30 2.06 0.08 8.35 1.11 2.07 0.01 10.99
	High	0.77	1.85	0.04	5.61	0.90 1.51 0.05 5.95 0.81 1.59 0.01 7.30
		TAB. 5.11 Performance comparison for different patient arrival rates

Acknowledgments

I would like to express my gratitude to Professor Xiaolan XIE and Professor Zhibin JIANG, my directors, for their joint guidance, support and patience. This work would not have been possible without their direction and financial support.

n={1, 1, 1, 1, 3, 0, 0};7CTS n={1, 1, 1, 1, 3, 0, 0};7CTS n={ 0, 1, 1, 1, 2, 2, 0};7CTS 25 S={1, 1, 1, 1, 2, 0, 0}; S ={ 0, 1, 1, 1, 1, 2, 0}; L={9, 9, 9, 9, 7, 8, 9}. L ={8, 8, 9, 9, 7, 8, 8}. L ={8, 8, 8, 9, 8, 7, 7}. J=4.47 J=4.03 J=3.83 n={1, 1, 1, 1, 3, 0, 0};7CTS n={1, 1, 1, 1, 3, 0, 0};7CTS n={ 0, 1, 1, 1, 2, 2, 0};7CTS 30 S={1, 1, 1, 1, 2, 0, 0}; S ={ 0, 1, 1, 1, 1, 2, 0}; L={10, 10, 10, 10, 8, 8, 10} L={9, 9, 9, 10, 8, 9, 9}. L ={9, 9, 9, 10, 9, 7, 8}. J=4.49 J=4.06 J=3.87 n={1, 1, 1, 1, 3, 0, 0};7CTS n={1, 1, 1, 1, 3, 0, 0};7CTS n={0, 1, 1, 1, 2, 2, 0};7CTS 35 S={1, 1, 1, 1, 2, 0, 0}; S ={0, 1, 1, 1, 1, 2, 0}; L={11, 11, 11, 11, 9, 10, 10}. L={10, 10, 10, 11, 9, 9, 10}. L={10, 10, 10, 11, 10, 8, 9}. J=4.50 J=4.08 J=3.89 n={1, 1, 1, 1, 3, 0, 0};7CTS n={1, 1, 1, 1, 3, 0, 0};7CTS n={ 0, 1, 1, 2, 1, 2, 0};7CTS 40 S={1, 1, 1, 1, 2, 0, 0}; S ={ 0, 1, 1, 1, 0, 2, 0}; L={11, 12, 12, 12, 10, 11, 11}. L={11, 11, 11, 12, 10, 10, 11}. L={11, 11, 11, 11, 11, 9, 10}. J=4.51 J=4.10 J=3.90 n={1, 1, 1, 1, 3, 0, 0};7CTS n={1, 1, 1, 1, 3, 0, 0};7CTS n={ 0, 1, 1, 2, 1, 2, 0};7CTS 45 S={1, 1, 1, 1, 2, 0, 0}; S ={ 0, 1, 1, 1, 0, 2, 0}; L={12, 12,13,13,11,12,12}. L={12,12,12,12,11,11,12}. L={12,12,12,12,12,10,11}. J=4.52 J=4.11 J=3.91 TAB. 4.6 Contracts and control policies vs RTS delay T R

To investigate the relation with respect to the patient arrival pattern, the peak demand of the base case occurred on Friday is interchanged with the demand other weekdays. We also consider the case of stationary demand for all weekdays. Again, the criterion values and the performance measures are insensitive to the change of patient arrival patterns. When the peak arrival changes to another weekday, one CTS time slot is move from Friday to the peak arrival day in the ""NoCancel"" strategy. Except for CTS of peak arrival day and Friday, "Cancel" strategy cancels all CTS time slots that cannot be used by patients in CTS Chapter 4 Contract planning and one-day advance cancellation of contracted time slots 83 queue. For the contract of "LocalOpt", one CTS time slot is moved from Friday to the peak arrival day. Again, one CTS time slot is left by the CTS cancellation policy for the peak arrival day. As for the other case, CTS are planned for the weekend.

Peak arrival "NoCancel" "Cancel" "LocalOpt" n={2,1,1,1,2,0,0};7CTS n={2,1,1,1,2,0,0};7CTS n={1,1,1,1,1,2 ) and W t (y t ) are separately used to identify the optimal patient assignment, one-day advance cancellation, and two-day advance cancellation control policies. Similarly, relation (5.4) can be rewritten as

By relation (5.7) and the uniqueness of the optimal value function,

From relation (5.9), its right hand side is a function of u t with

In the value iteration by (5.8) and (5.9) or equivalently by (5.16),

Proof. The proof is done by induction on t. The property trivially holds for t=0. Assume that it holds for some t+1≤0 for ( ) (  )

( )

To prove ( ) ( )

the right side, take the feasible control x 0 for ( )

To prove

1, ,

, two cases are considered:

Case 1:

( ) ( )

Now we prove ( ) ( )

Let y 0 and y 1 be arguments reaching minimum in relation (5.16) for

( )

. From the optimality condition, ( )

To prove ( ) ( )

≤ , two cases are considered:

Case 1: 0 y u > . Take the feasible control y 0 for ( )

Case 2: 0 y u = . Take the feasible control 1 u + for ( )

The first relation is from relation (5.9). The second is from relation (5.10) by applying the optimal two-day advance cancellation of ( ) t W u to ( )

The third is from the induction assumption.

To prove ( ) ( ) . Take the feasible control u for ( ) t V u and then apply the optimal two-day advance cancellation of ( )

In this case, there is no unused CTS for ( )

( )

Let x be the optimal control for ( )

Case 2: 1 1 y u > + . Take the feasible control y 1 for ( )

Proof. Let ( ) ( )

. Under the assumption of the Property, R t (y) is convex.

Let

( )

We will show 1

which contradicts Property 5-1 and proves 1

Relation (5.8) can be rewritten as:

Chapter 5 Contract planning and two-day advance cancellation of contracted time slots 95

As a result,

is a convex and non-increasing function of u.

which can also be defined as follows:

)

From the above definitions, it can be proved that a function f(x) that is Super and SuperC(i, j) is convex in i.

Property 5-3. In the value iteration by (5.8), ( )

Proof.

In order to prove the supermodularity of ( )

U z w , from relation ( 5.21), we only need to show the supermodularity of ( )

In order to prove relation (5.22), three cases are considered.

Case 1:

which together with the monotonicity of F t (z,w) in z proves relation (5.22).

Case 2:

and ' w w = . Hence (5.22) holds.

Case 3:

, ,

From [START_REF] Topkis | Equilibrium Points in Nonzero-sum n-person Submodular Games[END_REF], there exists a series of w which can reach the minimum of ( )

W y is convex in y t ,.

Proof. By contradiction, assume that ( ) ( )

. By supermodularity and optimality, there exists

As a result, ( )

G y w which contradicts the definition of ( )

The property that ( ) w y is decreasing function can be proved in the same way. Q.E.D.

Property 5-5. In the value iteration by (5.8), ( )

Proof. In order to prove the superconvexity of ( )

U z w , we need to prove the following relations:

and for all z and w.

Proof: From Property 5-1 and relation (5.8),

which, together with the finiteness of the state space,

for all z, z', w, and w'. Therefore,

Theorem 5-3. There exists an optimal stationary control policy for the average cost model (5.1). Further the optimal average cost is independent of the initial state (i, z, w).

Proof. From Proposition 4.2.6 in [START_REF] Bertsekas | Dynamic Programming And Optimal Control[END_REF], the optimal average cost per day exists and has the same value λ for all initial states, and λ satisfies ( ) ( )

The differential cost functions

satisfy the following optimality equations:

, '

Relation (5.46) can be rewritten as

Further, the optimal control policy is stationary deterministic and is defined by the argument that reaches the minimum in (5.46) or equivalently (5.47)-(5.49). From Theorem 5-2, relation (5.45), (5.50), and (5.51), ψ(i, z, w) is convex in z and convex in w, ψ 1 (i, u) is convex in u, ψ 2 (i, y) is convex in y, for all i = 1, …, 7. The optimal control policy can be shown to be of the same form as that of Theorem 5-2. Q.E.D.

Unbounded demand case

Property 5-10: For any z 1 ≥ z 2 ≥0, w 1 ≥w 2 ≥0, ( ) ( )

, ,

.

Proof: The property trivially holds for t = 0. Consider the case t < 0. Since the "min" term in equation (5.18) is decreasing in z, subtracting equation ( 5.18) with z = z 1 by equation ( 5.18) z t = z 2 leads to:

Since the "min" term in equation ( 5.18) is decreasing in w, subtracting equation ( 5.18) with w= w 1 by equation ( 5.18) w= w 2 leads to:

)

Let u' be the argument reaching minimum in (5.18) with z = z 2 , w= w 1 . As a result,

Subtracting equation (5.18) with z = z 1 , w= w 1 by equation ( 5.52) leads to:

Since u≥ u', from Property 5-1,

Combining relations (5.54)-( 5.55) leads to:

( ) ( ) ( )

Property 5-11: There exist M>0 and r > 0 such that

for all i = 1, …,7 and for all z.

Proof: From Property 5-10,

Combining with relation ( 5 "Two-day-cancel", "LocalOpt" benefits from the two-day advance cancellation by increasing the CTS cancellation ratio. The solution of "LocalOpt" also reduces RTS percentage, with a little decrease in average delay and unused CTS ratio.

Table 5.2 summarizes the contracts, patient assignment, one-day cancellation, and two-day cancellation control policies for the solution strategies of "Two-day-cancel" and "LocalOpt".

The optimal contract and the optimal control policies for "One-day-cancel" solution are n={0,1,1,1,2,2,0},L={10,10,10,11,10,8,9} S={0,1,1,1,1,2,0}, which are to the same with the control for "Two-day-cancel" and "LocalOpt" strategies with b 2 =0.8b 1 and b 2 =0.9b 1 . For the solution of "Two-day-cancel", the patient assignment control policy is nearly the same for different b 2 . With the increase of b 2 , the control policy for one-day advance cancellation increases leading to more one-day cancellation, whereas the control policy for two-day advance cancellation decreases leading to less two-day cancellation. For the optimal contract of "LocalOpt" strategy, more CTS are planned when b 2 is small. Due to the possibility of the two-day advance CTS cancellation, CTS are now planned for Sunday. When b 2 is small, larger patient assignment threshold is used because of more CTS introduced in order to avoid assigning patients to RTS.

0.1b 1 S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,1,1,1,3} X={0,0,1,1,1,2,0 } X ={1,0,1,2,2,1,3 } Y={0,0,0,0,1,0,0 } Y={3,0,0,1,1,2,1 } L={10,10,10,10,9,8,8} L ={22,23,24,24,24,23,21}

Y={0,0,0,0,0,0,0} Y ={2,0,0,1,2,1,1} L={10,10,10,10,9,8,9} L ={18,19,20,19,19,18

Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={10,10,10,10,10,8,9} L ={14,14,14,15,14,14,12}

Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={10,10,10,10,10,8,9} L ={14,14,15,15,14,14,13} 0.5 b 1 S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,0,1,1,2} X={0,0,1,1,1,2,0} X ={0,0,1,1,1,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={10,10,10,10,10,8,9} L ={14,14,15,15,15,14,13} n={0,1,1,1,2,2,0}7CTS n ={0,1,1,1,2,1,2}8CTS 0.6 b 1 S 1 ={0,0,0,0,1,2,0} S 1 ={0,0,0,0,1,1,2} X={0,0,1,1,1,1,0} X ={0,01,1,1,1,2} Y={0,0,0,0,0,1,0} Y ={0,0,0,0,1,1,1} L={10,10,10,11,10,8,9} L ={14,15,15,15,15,14,13}

X={0,0,0,0,1,0,0} X={0,0,0,0,1,0,1} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,0,0,1} L={10,10,10,11,10,8,9} L ={10,10,10,10,10,9,9}

0} 0.8 b 1 X={0,0,0,0,0,0,0} X ={0,0,0,0,0,0,0} Y={0,0,0,0,0,0,0} Y={0,0,0,0,0,0,0} L={10,10,10,11,10,8,9} L ={10,10,10,11,10,8,9}

0.9 b 1 X={0,0,0,0,0,0,0} X ={0,0,0,0,0,0,0} Y={0,0,0,0,0,0,0} Y={0,0,0,0,0,0,0} L={10,10,10,11,10,8,9} L ={10,10,10,11,10,8,9} TAB. 5.2 Contracts and control policies vs two-day advance cancellation costs b 2

Impact of one-day advance cancellation cost

This subsection considers the impact of the one-day advance cancellation cost b 1 by varying b 1 from 0.1c to 0.9c by taking b 2 equal 0.5b 1 .

Fig. 5.7 compares the average costs of the three solution strategies for different b 1 . It is clear that one-day cancellation cost leads to the reduction of average costs, although there is no obvious trends. When b 1 is smaller, two-day advance cancellation only provides little improvement. The greatest improvement of "Two-day-cancel" over "One-day-cancel" is 9.45 when b 1 =0.4c. Local optimization further improves the contract and control policies.

The combined improvement over "One-day-cancel" reaches 10.67% when b 1 =0.5c. Table 5.3 summarizes the performance measures of the three different solution strategies for different b 1 . With respect to the solution of "One-day-cancel", the "Two-day-cancel" slightly decreases the cancellation ratio when b 1 ≤0.6c, but greatly increases it when b 1 >0.6c. Correspondingly, the unused CTS ratio increases when b 1 ≤0.6c, and decreases when b 1 >0.6c. This means that the two-day advance cancellation plays more important role when b 1 >0.6c. The contract "LocalOpt" further improves the benefits of the two-day advance.

With respect to the solution of "Two-day-cancel", "LocalOpt" increases the cancellation ratio, at the same time reduces the unused CTS ratio. With the increase of b 1 , cancellation ratio decreases, whereas unused CTS ratio and average delay increase. 0.1c X={0,0,0,0,0,0,1} X ={1,0,0,1,0,0,1} Y={0,0,0,0,0,0,2} Y ={1,0,0,1,0,0,2} L={18, 18,18,19,18,17 X={0,0,0,0,0,0,1} X ={1,0,0,0,1,0,1} Y={0,0,0,0,0,0,2} Y ={1,0,0,0,1,0,2} L={14, 14,14,14,14,13 X={0,0,0,0,1,1,1} X ={0,0,0,0,0,2,2} Y={0,0,0,0,1,1,2} Y ={0,0,0,0,0,0,2}

Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={10, 10, 10, 11, 10, 8, 9}. L={10,10,10,10,10,8,9} L ={14,14,15,15,15,14,13} n={0, 1, 1, 2, 1, 2, 0};7CTS n={0,1,1,2,1,2,0};7CTS n={0,1,1,1,2,1,2}8CTS S={0, 1, 1, 1, 0, 2, 0}; S 1 ={0,0,0,1,0,2,0} S 1 ={0,0,0,0,0,1,2} 0.6c X={0,0,1,1,0,1,0} X ={0,0,1,1,1,1,2} Y={0,0,0,1,0,0,0} Y ={0,0,0,0,1,1,1} L={10, 11, 11, 10, 10, 9, S={0, 0, 0, 0, 0, 2, 0}; S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,0,0,0,2} 0.7c X={1,1,1,0,0,2,0} X ={0,0,1,0,1,0,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,0,0,0} L={10, 10, 10, 11, 11, 9, 10}. L={10,10,10,10,11,9,10} L={10,10,10,10,10,10,9} n={1,1,1,1,2,1,0};7CTS n ={1,1,1,1,2,1,0};7CTS n ={0,1,1,1,2,0,2}7CTS S={0, 0, 0, 0, 0, 1, 0}; S 1 ={0,0,0,0,0,1,0} S 1 ={0,0,0,0,0,0,2} 0.8c X={1,1,1,0,1,1,0} X ={0,0,1,0,1,0,2} Y={0,0,0,0,0,1,0 } Y ={0,0,0,0,0,0,0} L={10, 10, 11, 11, 10, 10, 10}. L={10,10,10,11,10,9,10} L={10,10,10,10,10,10,9} n={1,1,1,1,3,0,0};7CTS n ={1,1,1,1,3,0,0};7CTS n ={0,1,1,1,2,0,2}7CTS S={0, 0, 0, 0, 0, 0, 0}; S 1 ={0,0,0,0,0,0,0} S 1 ={0,0,0,0,0,0,2} 0.9c X={1,1,1,0,1,0,0} X ={0,0,0,0,1,0,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,0,0,0}

Impact of unused CTS cost

This subsection explores the impact of unused CTS cost, c, by varying c from 1 to 20 with b 1 = 0.5c and b 2 = 0.5b 1 .

Fig. 5.8 compares the average costs for different unused CTS cost c. When c is smaller than 5, two-day advance cancellation only provides marginal improvement. Larger improvement is gained when c is larger, for example, 9.48% of improvement of "Two-day-cancel" over "One-day-cancel" when c=10; 3.65% when c=15; and 5.21% when c=20. Local optimization further improves the contracts and control policies, with 7.28% of the greatest improvement over "Two-day-cancel" when c=15. S={0, 0, 0, 0, 0, 1, 1}; S 1 ={0,0,0,0,0,1,1} S 1 ={0,0,0,0,0,1,1} 1 X={0,0,0,0,0,0,0} X ={0,0,0,0,0,0,0} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,0,0,0} S={0, 0, 0, 0, 1, 2, 0}; S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,1,0,0,1,1} 5 X={0,0,0,0,1,2,0} X ={1,0,1,0,1,1,1} Y={0,0,0,0,0,0,0} Y ={1,0,0,0,0,0,1} L={13, 13,13,14,13,12 S 1 ={0,0,0,1,0,1,1} S 1 ={0,0,0,0,1,1,2} 10 X={0,0,1,1,1,1,1} X ={0,0,1,1,1,1,2} Y={0,0,0,1,1,0,1} Y ={0,0,0,0,0,1,1} L={14, 15, 15, 14, 14, 13, 13} L={14,14,15,14,13,13,13} L={14,14,14,15,14,14,12} n={0, 1,1, 1, 2, 2, 0};7CTS n={0,1,1,1,2,2,0};7CTS n={0,1,1,1,2,1,2}8CTS S={0, 1, 1, 1, 1, 2, 0}; S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,0,1,1,2} 15 X={0,0,1,1,1,2,0} X ={0,0,1,1,1,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={10, 10, 10, 11, 10, 8, S={0, 1, 1, 0, 1, 2, 0}; S 1 ={0,1,0,0,0,2,0} S 1 ={0,0,0,1,0,1,2} Tues X={0,0,0,1,1,2,0} X ={0,0,1,2,1,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={10,10,10,10,10,9,9}. L={10,10,10,10,10,8,9} L={14,15,15,14,14,14,13} n={0,1,2,1,1,2,0};7CTS n={0,1,2,1,1,2,0}7CTS n={0,0,2,1,2,1,2}8CTS S={0,1,1,0,1,2,0}; S 1 ={0,0,1,0,0,2,0} S 1 ={0,0,1,0,1,1,2} Wed X={0,0,1,0,1,2,0} X ={0,0,1,1,2,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,1,0,2,1} L={10,10,10,10,10,9,9}. L={10,10,10,10,10,8,9} L={14,15,15,15,14,14,13} n={0, 1, 1, 2, 1, 2, 0};7CTS n={0,1,1,2,1,2,0}7CTS n={0,1,1,1,2,1,2}8CTS S={0, 1,1, 1, 1, 2, 0}; S 1 ={0,0,0,1,0,2,0} S 1 ={0,0,0,0,1,1,2} Thurs X={0,0,1,1,0,1,0} X ={0,0,1,1,1,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} S 1 ={0,0,0,0,0,2,0} S 1 ={0,0,0,0,1,1,2} Fri X={0,0,1,1,1,2,0} X ={0,0,1,1,1,1,2} Y={0,0,0,0,0,0,0} Y ={0,0,0,0,1,1,1} L={10, 10, 10, 11, 10, 8, 9}. L={10,10,10,10,10,8,9} L={14,14,15,15,15,14,13} n={0, 1, 2, 1, 1, 2, 0};7CTS n={0,1,2,1,1,2,0}7CTS n={0,1,1,1,2,1,2}8CTS S={0, 1, 1, 0, 1, 2, 0}; S 1 ={0,0,1,0,0,2,0} S 1 ={0,0,0,0,1,1,2} AVE X={0,0,1,1,1,2,0} X ={0,0,1,1,2,1,2} Y={0,0,1,1,0,0,0} Y ={0,0,0,0,0,1,1} We now perform the sensitivity analysis with respect to the patient arrival rate. Three scenarios are considered "Low" (base case), "Medium" (patient arrival rates 5 times larger), "High" (patient arrival rates 10 times larger). Fig. 5.11 compares the average costs of the three solution strategies. Two-day advance cancellation brings 3.65% improvement over "One-day-cancel" strategy for low demand instance, 5.18% for medium demand, and 5.33% for high demand instance. Local optimization further brings 7.28%, 3.53%, and 3.22% improvement over "Two-day-cancel" strategy, and leads to a combined improvement of 10.67%, 8.53%, and 8.38% respectively for low, medium, high demand instances. We can see that the two-day advance cancellation work well for both high and low demand instances.

List of publications

Health care: