Hichem Kamoun

Keywords: Distributed permutation flow shop, Equity, Makespan, Robust scheduling, PSO algorithm, Monte Carlo simulation. . 4.7 Conclusion........ A Mathematical Programming Language The makespan. CT: Completion Time. DPFSP: Distributed Permutation Flow-shop Scheduling Problem. ICU: Intensive Care Unit. IT: Idle time. MILP: Mixed Integer Linear Programming Master Surgical Schedule PSO: Particle Swarm Optimization. PSP: Percentage of Scheduled Patients. SCAP: Surgical Case Assignment Problem. SS: Surgical Suite. SSPI: Post Interventional Surveillance Room

Exhaustive approaches to optimize the robustness of surgeries scheduling

Dedication

To

The memory of my mother Zaineb.

My dear fadher, Ali.

My devoted, husband Aref, my dear daughter Ghada, my lovely sons' Mohamed aymen and Mohamed adem for their patience and encouragement.

My dear uncle Nejib

My brothers and sisters.

And

All those who have faith in me. Table 2.1

List of tables

Introduction

Surgery is one of the most important functions in hospitals and it generates many precious resources; that is what ORs are one of the most expensive resources in hospitals. The underutilization or the over utilizations of ORs have unwanted influences that decrease the efficiency of operating block.

The operating cost of a surgery department is one of the largest hospital cost categories, approximately one-third of the total cost. At the same time as the surgery is the major cost center, it moreover accounts for about two-third of hospital revenues. Therefore, small improvements in efficiency could translate into significant savings and benefits to the patient by early treatment and reduce the hospitalization cost.

For these reasons, managing the surgical resources effectively in order to reduce costs and increase revenues is one of the areas that draw considerable attention from the healthcare community. The management typically needs to take into account numerous factors (e.g., personnel availability, surgical instruments, ICU and ward bed capacities, etc.) and involves the actions of different stakeholders, such as surgeons, nurses, and patients.

Continuous change, uncertain demand and intense competition with the private institute are the defining characteristics of the today's volatile OR environment. In view of these conditions, the OR schedule is a powerful tool that assists hospital-wide communication and staffing. Supervising surgeries' costs enables the hospitals to provide an overall higher quality of care by reducing the patient's wait time.

Operating room schedulers have a serious problem: scheduling a random number of surgeries, with significant uncertainty in surgeries' durations and patient's arrival time.

The objectives to reach are to obtain a robust scheduling and to balance the tasks between the different resources involved in the operation.

The problem of operating room planning has been the subject of much research these recent years, giving rise to an abundant literature on the subject. This literature shows a predominant use of deterministic approaches that abstract all kinds of uncertainty.

However, the OR is subject to many forms of contingencies, mainly emergency surgery and the variable duration of interventions that can disturb with its functions. Thus, the objectives of the OR planning are not achieved when these random events are not taken into account.

The goal of our research is to develop models and methods for planning surgical activities while taking into account uncertainty cases.

The goals are to minimize the overuse of operating resources by minimizing the idle time, which generates the minimization of the makespan average, while maximizing the OR's performance rate; for this, the authors try to develop an efficient and robust OR schedule.

The scheduling makespan is the total time that has elapsed from the beginning of a certain task to its end, denoted Cmax. A scheduling is efficient if its average makespan is minimized, whereas a scheduling is robust if it maintains its performance in the presence of uncertainties.

Robustness methods are divided into two approaches: the proactive approaches, which aim at creating robust scheduling which anticipate the disturbances and the reactive approaches that allow revising intelligently the scheduling by taking into account the disturbances that arrive.

The memory is organized as follows: chapter 1 introduces the component and the principal role of healthcare system, describes the function of the OR, mentions the different resource that it mobilizes and the different management methods used. It also

The third chapter presents a MIP model for the block operative planning; a model that incorporates the economic interest of our work by establishing a new robust and economic approach that minimize OR costs. The resolution methods and the solution of the model with results analysis are also presented in this chapter. Chapter 4 presents a solution to surgical case assignment problem (SCAP), it introduces a stochastic model for the operating block planning and scheduling; a model that incorporates a proactive robust approach and the solution of the model with results analysis.

Finally, we present a final assessment of our work and some perspectives of research to conclude this thesis. In this chapter, we present the general context of our work. We focus on the failures and the challenge of the hospital system, we describe the function of the operating room, with all interaction with the internal and external environment, the issues related to its planning and scheduling. In particular, we demonstrate the importance of considering the random event when planning the OR.

Introduction

A general problem in healthcare consists in allocating some scarce medical resource, such as medical staff or OR, to medical specialties in order to keep the queue of patients as short as possible. A main struggle comes from the fact that we have to establish such allocations several months in advance, and the patients' number for every specialty is an uncertain parameter. Furthermore, the cyclic schedules arise a, where it takes a short period to perform the allocation, e.g. a week, and then repeated afterwards.

However, the demand of OR services' usually differs from a week to another: if we know in advance the exact demand for each week, the weekly schedule can be improved consequently. That is why governments should pay a lot of attention to their healthcare systems.

Publicly funded hospitals are generally allocated annual capitals by the correspondent government based on the number of enrollees in the region. Given budget constraints, the capacity of resources is fairly distributed. These hospitals make every effort to optimize the use of their resources through continuous improvement and optimization techniques.

In many publicly funded healthcare systems, demand for surgery habitually exceeds supply consequently causing long waiting list, waiting times and impact on patient's quality of life.

Some research has been established until now to solve the problems in the public hospital system, because there is an enrollment in high number with limited staff capacity and materials.

In this chapter, we present an overview of Tunisian healthcare systems in order to focus on their strengths and weaknesses. Then we will explain hospital classification, after we interest in the OR that is the most important engine in a hospital, then we describe the importance of an efficient planning and scheduling in increasing the performance of the operating room, and finally we focus on the relationship between the OR and the other departments.

1.2 Healthcare system

Objectives and challenges

The magnitude of public expenditures in any health care system is important because it indicates the volume of attention governments are likely to pay for the system and thus the influence they bring to bear on its configuration. In spite of the government's role in the financing and regulation of health-care has grown inexorably; government plays a substantial role in healthcare.

A healthcare system includes policies and regulations, as well as related non-healthcare services, such as food safety and workplace safety, roads and reliable vehicles for the transport of medical supplies. It is more complex in its activity, its functioning circuits. It consists of two types of institutions such as public health institutions and private health facilities.

The healthcare system is an organized plan of health services. The term usually is used to refer to the system or program by which health care is made available to the population and financed by the government, private enterprise or both. In a larger sense, the elements of a health care system hold the following part.

 Personal healthcare services for individuals and families, available at hospitals, clinics, neighborhood centers, and similar agencies, in physicians' offices, and in the clients' own homes;

 The public health services needed to maintain a healthy environment, such as control of water and food supplies, regulation of drugs, and safety regulations intended to protect a given population.

 Teaching and research activities related to the prevention, detection, and treatment of disease and health insurance that covers the system services.

With the technology and the scientific revolution, there is a notable emergence of a large number of dangerous diseases, which involve very expensive costs to society in treatment monitoring and drug costs. That is why healthcare organizations appeared in almost every country of the world, these organizations have as role to improve the state of health of citizens, to manage and progress research in order to optimize citizens' health, discover new remedies…

The hospital system has a great importance in the world, it affects the health of people who build a predominant factor in development, and this system aims to achieve these different goals:

 Preserving and improving the health of the population in order to maintain the human capital.

 Providing services that meet public expectations.

 Ensuring the equity in healthcare: equality of utilization, distribution according to need, equality of access, and equality of health.

In front of continually increasing health care supply, which widely exceeds offered service, limited government support and increasing competition, hospital's managers are more and more conscious of the need to use their capital as efficiently as possible.

1.2.2

The Tunisian health care system

Overview

In 2014 and according to TMOH, the healthcare system in Tunisia is considered to be the second in Africa, Conversely, the reality is that it suffers from a rise of shortcomings, mainly encompassing matters related to the legal framework, the governance and policies, public health and medical education, and funding.

Both parties putting the national health system in trouble, the medical professionals (specifically young medical doctors who are pursuing residency training) and the TMOH, they are unable to find a compromise regarding the shortage of the human medical resource in the remote regions of the country and move issues ahead in the interest of all Tunisians.

Despite the increasing budget allocated to the healthcare system, the medical field in Tunisia is always criticized: doctors, patients, students, and managers are not satisfied.

Many healthcare institutions having been researching for tools to improve the actual situation of patients, to reduce costs and to guarantee efficient use of hospital services, especially surgeries that are among the most expensive treatments in the medical treatment.

Because they use a lot of the more expensive material resources and the rarest human resources (surgeons, anesthetists, nurses), ORs are considered among the most critical resources that generate higher costs for a hospital.

In addition, in public hospitals most care is supported by the state, so the income paid by the patient does not cover the operating costs, for these reasons, planning, and scheduling OR activities become major priorities for hospitals.

It is incumbent upon the medical and academic institutions to improve the public health system in the country and be the pivotal hub of this collaboration. Many studies have been established trying to remedy the most obvious problems. The second step is the establishment of a thorough assessment of the current environment and the development of a gap analysis by confronting the best practices around the world in public health care related matters. This will require implementing state-of-the-art processes to collect, analyze, and diffuse relevant public health information aggregated both at national and regional levels. Such processes should incorporate all the aspects of public health such as epidemiology, environmental health, medicine, social, behavioral science, economics, policy, and governance. They should be totally transparent and allow to accurately gather informative and up-to-date key performance indicators about the healthcare system through an extensive use of information systems, including electronic registries, data warehouses, electronic health records, and mobile health information technologies.

Future work of the

Tunisian Hospital beds

Hospital beds consist of inpatient beds accessible in private, public, general, specialized hospitals and therapy centers. Always, beds for both acute and chronic care are involved.

Hospital beds (per 1,000 people) in Tunisia were 2.10 as of 2010. Its highest value over the past 50 years was 2.86 in 1992, while its lowest value was 1.70 in 1997.

Classification of Hospital

The ministry of Healthcare has classified Hospitals, according to many criteria, exactly as we did: the number of beds, the types of care provided and whether or not teaching facilities are available. The Ministry of Healthcare and long-term care has classified hospitals in regulation 1964. Hospitals are classified from Group A to Group V (TMOH 2012).

Hospitals are classified as General hospitals, active treatment, teaching hospital, and regional rehabilitation hospital as follows:

Group A:

General hospitals having teaching facilities for medical students of any university with which they have affiliations with a written agreement. These hospitals provide postgraduation certification in one or more specialties. These types of hospitals are very large organizations.

Group B:

They are the hospitals having more than 100 beds. These are mostly community hospitals.

Group C:

They are the hospitals having less than 100 beds. These types of hospitals are aimed to serve very small communities.

Group D:

Hospitals treat patients suffering from Cancer and undertake research for the causes and remedies of cancer with facilities for medical students.

Likewise, group E to group V classification is listed in the regulation 964.

Operating blocks component

The OR service is a passageway serving multiple services and specialties; its mission is to provide an efficient framework for all elective or urgent interventions. It consists essentially of 11 units:

 Operation Room: almost all departments contain ORs for scheduled operations and ORs for emergency operations that run 24/24 h. There are multi-specialty ORs that are versatile ie, dedicated to holding surgical cases in all specialties and their monospecialty that are specialized ORs.

 Induction room: the operating department has one induction room, near to the recovery room in which patients are anesthetized before they are transferred to the operation already sleeping, but often the patient's induction takes place directly in the OR.

 Reception room: it is located at the entrance of the operating theater, in which patients wait before being transferred and brought to the operating room. This room can contain between 3 to 5 beds.

 The post Interventional surveillance room (SSPI): is a place to receive and install patients, in a safe and comfortable manner and in the medical and aesthetic requirements, it hosts over a more or less long duration wake patients.

 Block dedicated to obstetrics is composed of local prepare for childbirth and monitor the onset of labor; of workplaces in which all these premises, the operations room of Interventional post surveillance rooms are located at the same level in order to allow the rapid movement of patients, neonates, staff, and materials needed.

 Post-anesthesia care unit (PACU): when surgery is over, patients are taken to the PACU where they will be monitored continuously until they are awake and can return to their rooms or leave the hospital.

Stretcher team is trained in first aid and handling of people, it handles patient transport on within the hospital  A sterilization room where mobile devices, as well as biomedical equipment such as microscopes, ventilators, monitors, are cleaned and disinfected  Care services.

 A reserve for pharmacy.

 Storage rooms and cloakrooms.

Description of operating rooms

The importance of OR in the hospital is analogous to the importance of the engine in an automobile [START_REF] Blake | A goal programming approach to strategic resource allocation in acute care hospitals[END_REF]. A surgery center well known as OR, is the component of a hospital where surgical processes are accomplished, an OR need to be well equipped to provide specialized care to patients with specific conditions.

Operating room characteristics

Since the ORs are for the most part costly resources in hospitals. Their management typically needs to take into account numerous factors (e.g., personnel availability, surgical instruments, ICU and ward bed capacities, etc.) and involves the actions of different players, such as surgeons, nurses and patients [START_REF] Van Oostrum | A master surgical scheduling approach for cyclic scheduling in operating room departments[END_REF].

The optimization of the management of operating room is a complex problem that chaining.

It should be taken into mind, and must constitute one of the first concerns of a hospital, especially in the case of increasing demand. The improvement of efficiency and productivity of the hospital sector involved a great interest to operating block; therefore, this latter attracted the attention to a detailed study.

Multiple constraints such as the timetable and surgeon's expertise, availability of beds, the variability of operation duration's, and the urgent cases must be taken into account in the operating theater.

Several studies have been carried out until today to solve scheduling problems and planning of the OR; Fei et al. (2008); [START_REF] Jebali | Operating rooms scheduling[END_REF]….

By dealing with the allocation of surgical interventions in two common cases (emergency and programmed) and the various resources allocated to each intervention all flows of patients from different departments, surgical converge towards the operating theater, to establish a programming procedure.

In this section, we allow a great interest on the components of the operating block, the different operating activities and resources used.

The OR department is the juxtaposition of large modular, versatile and flexible ORs:

 Each room's area shall be sufficient (greater than or equal to 40 m 2 ), giving the ability to accommodate the necessary equipment of modern technology;

 Flexibility and modularity should show adaptability to the entry and exit of bulky materials (e.g the robot ...) and/or operational activities requiring a large number of stakeholders (e.g transplants ...) and multidisciplinary teams;

 Versatility implies the adaptability of the room to the various operating activities, but does not imply daily modifications of random allocations to different specialties;

 The number of rooms must be sufficient to allow proper maintenance in order to lower the threshold of contamination;

 Waste packaging in the OR makes the notion of clean and dirty circuits obsolete.

 Such a structure requires sufficient areas attributed to logistics, the location of which must allow making areas and all the necessary equipment to cope with unforeseen events available very quickly.

Relationship between OR and the other departments

The operating blocks are considered as the main engine of the hospital. The activities of the OR affect a lot the other departments and almost every activity within the hospital environment. Therefore, the OR service is in a close and direct relationship with all other departments, communication is one of the organizational functions that help this service to stay efficient and productive one of the most important forms of organizational communication is interdepartmental communication. The magnitude of communication between different departments in any organization, especially in a hospital facility, becomes most evident when that communication breaks down. Implementing policies to strengthen interdepartmental communication help to underscore its importance and maintain an efficient flow of information.

The appropriate performance of the OR depends on the coordination with them, this can give enormous help to the efficiency of these rooms, such as analytical laboratories, Laboratory and Blood Bank, radiology department, and pharmacy …thus a good coordination leads to the effectiveness of surgical service.

To demonstrate the relationship between the OR and the other departments in the hospital, we present the different phases of the operating process. This interaction can be decomposed into three main phases [START_REF] Chaabane | Gestion prédictive des blocs opératoires[END_REF].

 The pre-operative phrase: extends from the patient's care until his transfer to the OR for surgery. During this phase, the patient endures surgical and anesthetic consultations. During this phase, a date that is "temporary" for the intervention is fixed to the patient. This date may be changed according to the political block procedure and the uncertainty cases.

 The preoperative stage: corresponds to the stay of the patient in the OR. It covers the period from when the patient enters the block until he leaves the recovery room. On the day of the intervention, stretcher from his room into the OR first transports the patient; he/she will then be anesthetized and finally operated by a surgical team. Note that various activities such as sterilization, setup and preparation are made just before and after the intervention. After the surgical intervention is done, the patient is transferred to the recovery room. He/she stays there until the anesthesiologist allows him/her to return to his/her room or he/she is transferred to the unit intensive care and recovery.

 The postoperative phase: from the recovery room, the patient is transferred to his room or to the intensive care and recovery unit, if there are any complications.

This phase covers all the care necessary following the intervention.

As we explained above and from the description of the operating process, it is clear that OR accounts as an interface between several other areas of the hospital, such as the services of hospitalization, ICU, sterilization activities, and stretcher logistics (consumable supplies and various equipment).

Operating room's indicators 1.3.4.1 The Work Time: TMDA

The TMAD is the potential of time available to perform the surgical activity.

Computing formula; for example: the time between the block opening (7:00 am) and closing (7:30 pm) is 12 h 30 minutes. TROS is the time when a surgical activity takes place in the time reserved.

Computing formula: this is the sum of time during which the ORs are occupied for a week.

Figure 1.3: TROS

Type of surgeries

Mainly two types of surgeries are registered, following the type of the patient, elective or emergency one; the elective surgery or elective procedure is a surgery that is scheduled in advance because it is considered a medical emergency. The semi-elective surgery is a surgery that must be done to preserve the patient's life.

Hence, an urgent operation is one that can wait awhile until the patient is medically stable, but should generally be done today or tomorrow, and an emergency does not necessary need to be performed immediately.

In other cases, the surgery must be performed immediately, immediately; the patient has no choice other than immediate surgery if they do not want to risk permanent disability or death.

Only elective surgeries can be scheduled.

Patient types

In the hospital, there are two types of patients: elective patients (programmed) and emergency (unscheduled) patients.



Elective patients [START_REF] Tan | Mathematical Programming for the Scheduling of Elective Patients in the Operating Room Department[END_REF] They are the type of patients who do not need emergency medical treatment and can be served at a pre-defined time. They are those who pass by the outpatient service. The patient goes through several services during their exams in the service as the radiology department, laboratory collection service, etc. to obtain their complete application and be prepared to hospitalization. The reception service prepares for each patient a folder, this folder contains all the medical information from different services and follows the patient in his journey through the hospital. The necessary information stored as records related to the patient and the procedure performed.

The administration has set up surgical target wait times for different surgeries, which are calculated from the date of diagnosis to the date of commencement of surgery.

Elective patients are subdivided into the following categories.

 Inpatient: A patient who needs to be admitted for a day or more before surgery in OR is classified as an inpatient.

 Same day patient: Patients expected to be discharged on the same day of the surgery are also known as the same day patients.

 Overnight patient: Patients who are expected to be discharged on the day after surgery are called overnight patients.

 Same day admission patient: These types of patients are expected to stay more than one day after surgery in the hospital recovery area, but they are admitted to the hospital prior to surgery on the surgery day (same day) itself.

 Emergency patients:

Immediate care is needed for emergency patients. The majority of hospitals have especially devoted OR for emergency surgeries. Emergency patients have been served just after arrival, while urgent patients are served with less priority than that of emergency patients. The figure 1.5 adapted and modified from (Tan et al., 2007b) explain the flow of different main types of patient.

Operating room planning and scheduling

In the order to manage and coordinate the various activities of the OR, hospitals use a management tool called an operating program [START_REF] Kharraja | Evaluation de performances pour deux stratégies de programmation opératoire de bloc[END_REF][START_REF] Jebali | Vers un outil d'aide à la planification et à l'ordonnacement des ressources dans les services de soins[END_REF]Chaaban et al., 2004).

The term "operating program" has different meanings from one institution to another.

However, the purpose is the same: to establish provisional schedule interventions for a given horizon, ranging from a day to a week or more, in their allocating resources (human and material) and setting the order of their execution.

The objective of the OR planning is to assign an operating theater and time slot a day at each scheduled or unscheduled patient. (Laamiri, 2007) Scheduling (canon et al. 2006), is the step that makes an orderly association between tasks and resources. The problem, therefore, has two dimensions: the allocation of tasks; and the temporal arrangement of their tasks on each resource. The objective of achieving this combination is to maximize efficiency criteria while respecting the defined constraints.

Research value

ORs are the principal cost centers and the greatest source of revenues for private hospitals, but in public one, the incomes do not cover the costs. Planning and scheduling of the OR are key devices that can be useful for the improvement of the productivity level of ORs and the related departments.

Surgical case scheduling consists of allocating all hospital resources to individual surgical cases and deciding on the suitable time to perform the surgeries. This task plays a great role in the utilization of hospital resources efficiently while ensuring a good quality of care for patients.

The imbalance between the number of scheduled operations per day and number of rooms, lack of surgeons, regional imbalance, hospitals in small town, with no ORs, pose problems of congestion in major cities such as the case of the city of Sfax, where is located the hospital in our case study. This congestion makes scheduling problems very difficult, especially with the emergency cases.

With the increase of aging population, social demands for surgical service have been constantly increasing. The overall surgery process involves several activities before (preoperative/surgery), during (peri-operative/surgery) and after (post-operative/surgery) an actual surgical procedure. These acts need a number of materials and human resources, the major problem in accomplishing the planning and the scheduling prepared is the lack of these resources (absence of medical staff, patients, emergency, an impervious breakdown of one or plus machines.

Hospitals are institutions with many departments working under one roof. Scheduling involves many demands to be satisfied simultaneously or on a priority basis.

Hence, it is very natural to have multiple objectives to be accomplished while creating an efficient schedule, which satisfies all requirements of booking manager. Sometimes, it is possible to have a conflict of interests

Approaches to prepare operating room schedules

The surgeries planning and scheduling process include the scheduling of elective and emergency patients.

One main objective is to prepare a Master Surgical Schedule (MSS) which is a cyclic timetable defining types and number of ORs available at a hospital, the operating hours and the human resources especially surgeons who are assigned for the surgical procedures [START_REF] Blake | A goal programming approach to strategic resource allocation in acute care hospitals[END_REF]. [START_REF] Kharraja | Outils d'aide à la planification et l'ordonnancement des plateaux médico-techniques[END_REF] discusses three different approaches to schedule ORs, which affect the cost, and service levels of the patients.

 Open scheduling approach:

In this method, a blank schedule is established for each schedule period. The schedule is filled chronologically on the first come, first serve basis as surgery teams show interest in OR slots. Negotiations also take place between two conflicting OR slots. The open scheduling approach is not very common in Tunisian Hospitals. This approach is free of constraints.

 Block scheduling approach:

In this type, pre-allocated slots of ORs are used to create the schedule for a period of a month. Surgical specialties then assign slots to surgery teams. Surgery teams decide their preferences of slots over the other teams within their specialty.

 Modified block scheduling approach:

This approach is a combination of open and blocks scheduling approach. At first, blocks have to be assigned using the block scheduling approach, after that the reallocation of the unused blocks is done for the other surgical specialties by using the open scheduling approach.

The major approaches used in hospitals are the block scheduling approach and the modified block scheduling. The open scheduling approach is time-consuming as well as not an intuitive management tool for hospital management.

Scheduling under uncertainty

An important issue in OR scheduling is uncertainty; it will lead to the invisibility of the optimized schedule in practice.

The uncertainty which causes many troubles on the MMS comes from the randomly durations of surgery, or the emergency cases, involved with human or material resources.

The various hazards surrounding the exploitation of the OR can be classified into two categories. In one category, there are the hazards due to a malfunction or poor organizational practices; resulting in unavailability of human or material resources. In a second category, there are the hazards due to the nature of the medical world; it combines the vagaries concerning the demand process and the surgery duration.

 Demand process

The practice of the surgical procedures may occur unexpectedly. We cannot generally predict when the request for care is presented.

Some requests may be queued and scheduled for future dates. These Requests are generally interventions that are not of an urgent nature; they can be delayed without danger to the patient. In medical language, this type of application is usually referred to as controlled or programmed surgery. However, a significant part of the request falls within the requirement of immediate care. This type of request is, by its nature very, predictable, and therefore unplannable; it is usually referred to as emergency surgery. In such situation, the hospital must accept all urgent patients; it is necessary to insert urgent patients into the already planning, which sometimes causes dysfunctions and generally additional operating costs.

According to a study carried out in a Quebec hospital [START_REF] Lafon | Achieving a More Effective Management of Operating Theatre Inventories Through the Planning of Surgical Interventions[END_REF], Another type of hazard characterizing the demand process is the deferral or cancellation of an intervention already planned. Indeed, in some situations, a change in the condition of the patient may require further testing or testing to lead to a postponement of the intervention.

69%

 Availability of material and human resources

The unavailability of hardware resources is usually due to under-sizing resource, or the sudden damage of one or several resource. As an example, the case of an under-sized of the recovery room will block the flow of patients and eventually lead to the unavailability of the ORs. Concerning human resources, their unavailability is due to several reasons; as the under-sizing, the organizational practices, the unexpected absence, or the illness of the patient or the medical staff surgeons, for example, are generally affiliated with different institutions and they can arrive late for their appointments.

 Surgery duration

The duration of a surgical procedure is subject to significant variations according to the type of intervention, the level of expertise of the surgeon, the state of the patient, the anesthesia technique, etc.

The duration of the intervention corresponds to the length of stay in the operating room. It is composed mainly of a period of preparation for intervention (preparation of anesthesia, etc.), duration of the surgical procedure (which varies according to its nature, surgeon performance, and patient state), and the duration of cleaning and re-conditioning of the room. This Length of stay, function of multiple parameters, is denoted by the duration of operation.

The variability of the operating times very often leads to considerable modifications in the planning of the activities of the block. This leads to a deterioration of the quality of service and patient's satisfaction (waiting times, postponement of intervention ...) and operating costs of additional hours (overtime). So the efficient exploitation of the operating block is closely related to the integration of the stochastic aspect of the operating times in the planning of surgery activities, in order to propose robust schedules.

Scheduling and robustness

This lateness and problems encountered, leads us naturally to interest to the robustness of the system, i.e. its capacity to maintain its performance in the presence of uncertainty. In the case of scheduling, this concept is linked to the stability of the system when the execution times are nondeterministic. As affirm Canon et al. (2006), the robustness is not a measure, but a criterion which is applied to a measure of performance as the total duration of a scheduling or the makespan, the length of stay, the release time or the average wait time in a queue.

The robustness approach is an efficient approach to control uncertainty and making decisions under uncertain conditions.

The robust scheduling approach tries to create a schedule that minimizes the effect of disturbances caused by uncertainty during the operation on the objective function of initial scheduling, Canon et al. (2006). The surgical specialties that are handled at the site include Urology, Orthopedics, Dental medicine, Plastic, Ear, nose & throat (ENT), General laparoscopic surgery, and Gynecology.

Habib Bourguiba Hospital: an introduction

Approximately 65 surgeons supported by an administrative staff of a 100 personnel serve ORs. Two books clerks are assigned to book surgical cases requested from surgeons' offices.

The surgical blocks are assigned on weekdays from 8:00 am to 5:00 pm ORs are different because of different equipment and surgery performed. Surgical blocks are assigned as per specialty and surgeon.

We will take an interest in the ophthalmology surgery department, in order to discover the characteristics of this service.

In our study, we will analyze the method process of the OR, its resources, and flows, in order to identify the forces and weaknesses of the actual process and to define the major management issues. Then, we will study the organizational levels of the operating process, we will focus on the preoperative (before surgery), the per-operative (during surgery) steps of the operating procedure, and we will give a special interest to the post-operative (after surgery). Finally, we will present the necessary tools to solve the identified management concerns and we will specify their efficiency.

Thesis organization

The thesis is organized as follows in next chapters: chapter 2 covers the related literature review of hospital OR planning and scheduling, it describes the variety of strategic, tactical and operational scheduling problems and solution. Chapter 3 develops an exhaustive approach that challenge by presenting a new generalized model for surgery scheduling problems. We show the efficiency of this model by a game of test with variable size instances.

Chapter 4 presents a stochastic programming model used to solve the problem of the robustness of surgeries scheduling and the solution of the model with results analysis. This approach is applied in the hospital of case study CHUHB Sfax.

Conclusion

In front of continually increasing healthcare demand, limited government support and increasing competition, hospital's managers are more and more conscious of the need to use their capital as efficiently as possible. ORs are among the most critical resources that generate higher costs for a hospital. For these reasons, planning and scheduling, OR activities have become major priorities for hospitals. In this chapter, we described the OR environment; the different mobilizes resources and the complexity of its operations. We have presented different forms of uncertainties that can occur and need to consider them in the planning phase, which is the motivation of this work.

In this chapter, we present an overview of modeling approaches and of resolution methods used in the literature to solve problems of OR management. These problems are mainly the hospital management systems, the patient characteristics, and the lack of human and material resources, the performance evaluation, the uncertainties cases, and the robustness as a solution to uncertainty cases.

Introduction

The surgical intervention planning, is an operational problem, it consists of the assignment of interventions to ORs, in order to specify the surgery to be performed in each OR during each day of the planning horizon.

The operating program consists of two processes: Planning and scheduling. The process can have disturbances during operations, which must be taken into account when constructing an operational program. Three forms of uncertainty characterizing the disruption of the activity of the OR; uncertainty regarding the variability of surgery duration, the uncertainty about the unforeseen arrival of urgent cases and the unavailability of Human and/or material resources [START_REF] Lamiri | Planification des blocs opératoires avec prise en compte des aléas[END_REF].

Operating Room's scheduling has attracted a lot of researchers' attention, reflected in the abundant literature on the subject. The vital importance of the OR planning and scheduling explains the abundant literature that has dealt with the subject of different component and appearance.

This chapter describes methods and approaches used to model and resolve main issues raised by the management of operating theaters like human and material resources sizing, surgical activities planning and scheduling, human resource management, and indicator performance evaluation. Researchers focused on the OR scheduling problems from both modeling and algorithmic points of view.We present relevant ideas in literature organized according to different stakeholders and appearances.

The achievement of surgery planning is performed at two levels. The first level concerns the planning of the interventions that is to assign the surgeries or the surgeons on ORs while respecting their capacities; in this framework, we can mention the following work (Dexter 1999d;Guinet et al.2003a;[START_REF] Marcon | The operating theater scheduling: an approach centred on the follow-up of the risk of the planning[END_REF]). The second level concerns the scheduling of interventions, which is to establish the detail of achievement of surgical operations in theaters of operations while optimizing a criterion, as studied by [START_REF] Fei | A planning and scheduling problem for an operating theatre using an open scheduling strategy[END_REF].

Many

Hospital management systems

The management aspect of providing health services to patients in hospitals is becoming increasingly important. Hospitals want to reduce costs and improve their financial assets, on the one hand, while they want to maximize the level of patient satisfaction, on the other hand.

The OR is the unit that is of particular interest. Since this facility is the hospital's largest cost and revenue center [START_REF] Macario | Where are the costs in perioperative care?: Analysis of hospital costs and charges for inpatient surgical care[END_REF], it has a major impact on the performance of the hospital as a whole. Glauberman and Mintzberg (2001) affirmed that managing the OR is a hard task due to the conflicting priorities and the preferences of its stakeholders and due to the lack of costly resources. Moreover, [START_REF] Etzioni | The case for early detection[END_REF] encouraged health managers to anticipate the increasing demand for surgical services caused by the aging population.

Various research have attracted particular attention in the management of hospital systems.

They present the issues of hospital management and the possible contributions of production management or more management that is general.

In recent decades, many applications of modeling in the area Hospital have been undertaken.

These models are used for the prevention, research predominance and the study of the mortality of chronic diseases or sets specific diseases such as cardiovascular diseases. Other models in the design of healthcare systems to estimate future resource requirements have been developed.

The models are now increasingly developed as analytical support and decision making in medical practice. For example, the work of [START_REF] Lagergren | What is the role and contribution of models to management and research in the health services? A view from Europe[END_REF] actually, relates to the contribution of modeling in the management of hospitals. Modeling for understanding the operation of a given system and predict his reactions to different changes that the system faces. The models developed in this framework provide the opportunity to study not yet existing systems to predict the complex consequences of decisions or developments and allow the virtual completion of tests impossible or too expensive to perform in reality.

Since 1980, the need for models describing patients' waiting lists and projecting the effect of allocating resources is increasingly important. In this context, De Vries et al. (1998) presented a dynamic model, minimizing the waiting time of patients for admissions to care.

They keep hold of the example of waiting for older people in psychiatry lists.

Patient characteristics

The literature on OR planning and scheduling considered two major patient classes are, that is elective and non-elective or emergency patients [START_REF] Tan | Mathematical Programming for the Scheduling of Elective Patients in the Operating Room Department[END_REF]).

The first class represents patients for whom the surgery can be planned, whereas the secondclass represents patients for whom a surgery is unexpected and so needs to be performed immediately.

Elective patient planning and scheduling are well studied in the literature compared to the non-elective one. Although researchers do not point out what category of elective patients they are considering, some discriminate between inpatients and outpatients.

Outpatients have same-day surgery and leave the hospital the same day of surgery, while inpatients are hospitalized one or more days before and after surgery.

Adan and [START_REF] Bibliography Adan | Patient mix optimisation in hospital admission planning: a case study[END_REF] investigated both outpatients and inpatients in their study. They established a mixed integer-programming model to identify the cycle number and mix of patients that have to be admitted to the hospital in order to obtain the target utilization of several resources such as the OR or the ICU. In their case, outpatients are considered as inpatients with a length of stay of one day who do not necessarily need specialized resources such as the ICU.

When considering non-elective patients, a distinction can be made between urgent and emergent surgery (Cardean et al., 2010), this distinction is based on the reactivity to the patient's arrival (i.e. the waiting time until the start of the surgery). While the surgery of emergent patients has to be achieved as soon as possible, urgent patients refer to non-elective patients that are sufficiently stable so that their surgery can be delayed for a short period. [START_REF] Wullink | Closing emergency operating rooms improves efficiency[END_REF], for instance, examined whether it is possible to keep back a devoted OR or to reserve some capacity in all elective ORs in order to recover the responsiveness to emergencies cases. They use a discrete-event simulation, to prove that the responsiveness, the amount of overtime and the overall OR utilization significantly improved when the reserved capacity was spread over multiple ORs. [START_REF] Bowers | Managing uncertainty in orthopaedic trauma theatres[END_REF] grouped orthopedic urgencies into trauma sessions and use Monte-Carlo simulation to establish which session length balances a number of sessions overrun with an acceptable utilization rate. They moreover provided both a discrete-event simulation model and an analytical approximation to investigate the effects of including elective patients in the trauma session.

The operation execution time cannot be defined in previous, because it depends on the pathology of the patient, which can be partially known, and on the surgeon's expertise [START_REF] Dexter | Applications of information systems to operating room scheduling[END_REF]. That is for [START_REF] Sier | Scheduling surgical procedures[END_REF] took into account supplementary constraints, such as the patient age, the patient priority, and the operation allocation rule.

The developed mathematical model is nonlinear. Later, Dexter et al. (1999) used computer simulation to model OR scheduling to find an optimal scheduling strategy, in order to maximize the use of OR block time. [START_REF] Saadani | Hybrid heuristic for patients tasks scheduling on medical resources with bed allocation[END_REF], affirmed that a scheduling model of patients in the various hospital resources was presented by taking into account the availability of beds whose objective is to reduce the duration of patients. They proposed a mathematical programming model. The problem is solved first by the CPLEX solver and then by a hybrid heuristic.

Performance indicators

In order to evaluate the performance of the planning and scheduling methods, varieties of criteria are used. One frequent estimation measure relates to the waiting time of patients or surgeons. [START_REF] Denton | Optimization of surgery sequencing and scheduling decisions under uncertainty[END_REF] that are furthermore easy to implement. Patient waiting time is often considered the best measure for quality of care, especially in an increasingly complex environment like healthcare (Laurainne Pauline et al., 2016) Note that patient waiting time may also be interpreted as the stay on a surgery waiting list.

VanBerkel and Blake (2008) illustrated that this issue is strongly related to throughput analysis. In their work, they established a discrete-event simulation to examine how a change in throughput generates a reduction in waiting time. In particular, they influence throughput by varying the ability of beds in the wards and by varying the amount of available OR time.

Note that their operating theater of interest is spread over multiple sites, which is rare in the literature. This goal enables the hospital to increase returns on installing resources and thus helps to increase the efficiency of this service. The constraints include ORs available time and doctor's available time. The heuristic approach, which is based on the mathematical model, proposes near to optimal solutions in a very competitive time.

In the same objective to satisfy the patient and reduce its waiting time, Van Ostrum et al.

(2008), build a schedule with two objectives: the first is to maximize the occupation of the block; the second is to minimize the number of waiting days for patients between their hospitalization date and date of the transaction.

The utilization rate of resources is considered as a second performance measure, next to waiting time that is well addressed in the literature. Especially the utilization rate of the OR has been the subject of many types of research. For example, Kharraja, Chaabane, and [START_REF] Kharraja | Evaluation de performances pour deux stratégies de programmation opératoire de bloc[END_REF] realized the minimum makespan of ORs. [START_REF] Dexter | Managing risk and expected financial return from selective expansion of operating room capacity: Mean-variance analysis of a hospital's portfolio of surgeons[END_REF][START_REF] Dexter | Tactical decision making for selective expansion of operating room resources incorporating financial criteria and uncertainty in subspecialties' future workloads[END_REF] evaluated the procedure based on the OR efficiency, which is a measure that incorporates both the underutilization and the overutilization of the OR. The authors' related underutilization to under time and overutilization to overtime, although they do not necessarily represent the same concept. Utilization actually refers to the workload of a resource, whereas under time or overtime includes some timing aspect. It is therefore possible to observe an underutilized OR complex, even though over time may occur in some

ORs. The authors proofed their idea by considering an operating block with two ORs with a daily capacity of 4 hours. Whilst they presume that OR 1 (room 2) has a surgical workload of 2 (5) hours, only 7 out of 8 OR hours are used. Although this operating theater is underutilized, one hour of overtime in OR 2 is incurred.

The OR schedule also depends on supplementary services and facilities in the hospital, researche as well paying attention, to a lesser extent, on the utilization of resources other than the OR. [START_REF] Fei | A planning and scheduling problem for an operating theatre using an open scheduling strategy[END_REF] used a hybrid genetic tabu; the used objective function is a combination between the minimization of makespan of the OR department (include recovery room) and the OR. Regarding the OR over and underutilization, it is recommended to cancel surgical cases that start after the closing time of the OT. Since this may be difficult to implement, it is advisable to reduce the workload planned at the off-line operational level to 90% of the OT's capacity.

Regarding the variability of the OR completion times, it is judicious to adopt a single queue for all surgical cases. When this is infeasible from a technical or a managerial point of view, mixing surgical cases is preferable to separating them by type unless the hospital further decreases the number of minor cases assigned to the OT. Finally, the transfer of the last surgical case from a busy OR to a free one reduces the range of OR completion times.

Adan and [START_REF] Bibliography Adan | Patient mix optimisation in hospital admission planning: a case study[END_REF] presented the deviation between the target utilization of resources such as the ICU staff, ICU beds or regular ward beds: the performance criteria waiting time is minimized. [START_REF] Vissers | Patient mix optimization in tactical cardiothoracic surgery planning: a case study[END_REF] furthermore provided a case study in which they illustrate this approach for a department of cardiothoracic surgery.

Other research are multi-objective and multi-resources ie have more than objective to optimize and deal with more than human or material resources, these research are more efficient because they deal with the reality.

One example is [START_REF] Meskens | Multi-objective operating room scheduling considering desiderata of the surgical team[END_REF] dressed multi-objective OR scheduling considering desiderata of the surgical team, and the aim of this research was to optimize the use of the OR by minimizing the makespan, minimizing the overtime hours, and maximizing the harmony among members of the surgical group. This study is quite original because of the consideration of the surgical team's wishes in the establishment of an OR schedule.

To resolve the OR scheduling problem, the authors took advantage of the "expressive power" of the constraint-programming paradigm to introduce various real-life constraints in their models, such as availability, staff preferences, and affinities among staff members.

Then they developed a "generic" model that includes most of the problems encountered in the literature as well as constraints apparent in our hospital. The results achieved, when using Despite the importance of reducing OR costs, few studies in the literature address the issue of reducing costs through a better use of the ORs. Among them, we mention that [START_REF] Dexter | A strategy to decide whether to move the last case of the day in an operating room to another empty operating room to decrease overtime labor costs[END_REF] examined the decision to move the last case of the day in an OR to another empty OR in order to decrease overtime costs. Dexter and Macario (1999) used simulation to determine whether small decreases in surgical or anesthetic procedures allow an additional case to be scheduled in an OR during regular working hours.

Several stochastic approaches are also available for the off-line OR planning. So [START_REF] Lamiri | A stochastic model for operating room planning with elective and emergency demand for surgery[END_REF] proposed a stochastic approach for an OR that handles both planned elective and randomly arriving surgical cases. showed average reductions of 5% on the total completion time and 38% on the patients' total waiting time.

The literature presented a various set of manuscripts that integrate a leveling objective. [START_REF] Marcon | An observational study of surgeons' sequencing of cases and its impact on postanesthesia care unit and holding area staffing requirements at hospitals[END_REF], proposed a discrete-event simulation to examine how standard sequencing rules, such as longest case first or shortest case first, may assist in reducing the peak number of patients in both the holding area and the PACU. A similar analysis of such sequencing rules is provided in [START_REF] Marcon | Impact of surgical sequencing on post anesthesia care unit staffing[END_REF]. In this research, however, the authors restrict the focus to the PACU and study, between another factor, the makespan and the peak number of patients.

The completion time of the last patient's recovery is referred as makespan, in this case. In both studies, ORs are sequenced independently, which resulted in a reduced complexity. One other evaluation approach is to determine how well OR planning or scheduling procedures fulfill the preferences of its stakeholders. [START_REF] Cardoen | Evaluating the capacity of clinical pathways through discrete-event simulation[END_REF], also, solved a case, sequencing problem in which they try, amongst other, to schedule surgeries of children and prioritized patients as early as possible on the surgery day. At the same time, they want patients with a substantial travel distance to the ambulatory surgery center to be scheduled after a certain hour.

There are other categories of performance measures than those that were addressed in the previous paragraphs, This category groups criteria related to the use of the additional capacity of specific resources [START_REF] Persson | Optimization modelling of hospital operating room planning: Analyzing strategies and problem settings[END_REF], delayed in PACU admissions [START_REF] Marcon | Impact of surgical sequencing on post anesthesia care unit staffing[END_REF] or OR target allocation [START_REF] Rohleder | An operating room block allocation model to improve hospital patient flow[END_REF]. This statistic information has shown the importance of having all necessary resources during any operation. Only a few papers considered both OR and PACU or ICU [START_REF] Augusto | Operating theatre scheduling with patient recovery in both operating rooms and recovery beds[END_REF][START_REF] Testi | Tactical and operational decisions for operating room planning: Efficiency and welfare implications[END_REF][START_REF] Tànfani | Operating room planning considering stochastic surgery durations[END_REF], and even fewer research considered the interaction with PHU [START_REF] Pham | Surgical case scheduling as a generalized job shop scheduling problem[END_REF].

Based on the work of [START_REF] Xiang | A short-term operating room surgery scheduling problem integrating multiple nurses roster constraints[END_REF] tried to take the other personnel resources like nurses (Nurse rostering: take into account the nurses' skill set and qualifications) and anesthetists which are required during the complete surgery flow of the three stages into account.

Resolution methods

Since the interest granted to the problem of planning and scheduling of operating rooms, several of resolution methods are used, such as the mobilization of the problem by a mixed integer mathematical programming to be generally resolved by the Cplex solver. If the program is NP-hard, and cannot be resolved by Cplex, one used the heuristic meta-heuristic to optimize the obtained solution. Other passed through simulation as performance evaluation tool, it should rather set the assignment rules and give the scenarios (scenario being a particular set of decision variables); the simulation will evaluate each scenario (measure its performance) and thus the possibility to choose the best (but among those you have defined).

Other research preferred the realization of an optimization using a new or an existing heuristic (H), or a meta-heuristic (MH), simulation method, Stochastic or deterministic resolution, or the combination of two or of three methods.

Many Heuristics and meta-heuristic have been developed. In addition, some data sets "benchmarks" are available and are used to compare the different methods of the resolution approaches.

More goals have been set; each of these methods has made an addition to hospitals. Often we find the coupling of several methods, all tried to achieve the objectives referred. In the following, we try to sort many types of resolution method, although in general, these methods are conflicting and inseparable.

Stochastic approach

Xiang et al. (2015), proposed a mathematical model and an ant colony optimization approach to efficiently solve such surgery scheduling problems.

Simulation

When simulation optimization is the main goal, approaches of Lin, Mustafa, and Pasupathy (2013) or [START_REF] Klassen | Improving performance in outpatient appointment services with a simulation optimization approach[END_REF] became useful. The former uses a combined genetic algorithm and data envelopment analysis to assess the simulation results and guide the search process while sampling as few points as possible. The second uses simulation optimization to confirm that the dome-shaped sequencing rule is the most robust in terms of many performance criteria, but that a flatter dome-shaped rule could be more useful.

Van proposed a stochastic approach for an OT that handles both planned elective and randomly arriving surgical cases. The elective surgical cases are planned over a finite planning horizon with a random slack prearranged for emergency cases.

They tackle the problem using a method that mixes integer programming and simulation with the objective of minimizing costs related to patients and to ORs expected over time.

Min and Yih (2010) used the stochastic dynamic programming to schedule elective surgical cases of different priorities with the objective of minimizing the cost of ORs' overutilization and of the healthcare associated with postponing the cases. [START_REF] Batun | Operating room pooling and parallel surgery processing under uncertainty[END_REF] investigated the utility of pooling ORs using a two-stage stochastic integer program, which determines the optimal number of ORs to be used, the sequence and the starting time of surgical cases. Determining optimal resource levels in surgical services.

Summary table

Uncertainty

One of the main difficulties related to the expansion of accurate, scheduling, or capacityplanning strategies is the uncertainty inherent in surgical services. Uncertainty is prevalent in the context of OR scheduling due to lack of accurate process models and variability of process and environmental data. Therefore, it is of critical importance to building up organized methods to deal with the trouble of scheduling under uncertainty, in order to generate efficient and reliable schedules [START_REF] Floudas | A new robust optimization approach for scheduling under uncertainty: I. Bounded uncertainty[END_REF].

The process and the environmental data, based on the literature review are presented in (cardoen et al., 2010), two types of uncertainty characterizing the activity of the OR: (1)

uncertainty regarding the variability of operating time and ( 2) uncertainty on the unexpected arrival of urgent cases). Whereas deterministic planning and scheduling approaches ignore such uncertainty or variability, stochastic approaches try to incorporate it. In the stochastic literature, two types of uncertainty that look to be well addressed are patient arrival uncertainty and surgery duration uncertainty.

The former points, for instance, at the unpredictable arrival of emergency patients or at the lateness of surgeons at the beginning of the surgery session, whereas the latter represents the variation between the real and the considered surgery durations of actions associated to the surgical process. Remarkably, only a few manuscripts explicitly refer to resource uncertainty, for example, [START_REF] Cardoen | Evaluating the capacity of clinical pathways through discrete-event simulation[END_REF], while this topic currently is a hot topic in, for instance, project management or project scheduling as the present by Lambrechts el al.

(2008). It should be noted, though, that resource uncertainty often coincides with arrival uncertainty. For example, the arrival of emergencies may result in a claim of both the surgeon who is needed to perform the emergency surgery and a specific OR. These privileges essentially result in resource breakdowns as the elective program cannot be pursued and hence has to be delayed.

The nurse-scheduling problem also attracts a lot of research; it can be complicated because of the competing performance measures involved regarding multiple stakeholders (i.e., patients, surgeons, nurses).

Nurses must be used efficiently as well as possible. The latter is maximized by minimizing mutually nurse overtime and idle time. The overtime stresses nurses and consequently decreases the quality of care, whilst idle time causes great material waste [START_REF] Maenhout | Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem[END_REF]Welton, 2006).

Due to the significant uncertainty in surgery duration, the scheduling of nurses highly effects on-time surgery starts. For instance, consider a state while a nurse is assigned to two nonoverlapping surgeries in two ORs. If the previous surgery finishes later than expected, the other operation could be delayed just because of the nurse's absence. On-time surgery starts are important in practice since late starts increase the probability of overtime, which results in higher direct surgery costs, patient and surgeon fatigue [START_REF] Denton | Optimal allocation of surgery blocks to operating rooms under uncertainty[END_REF][START_REF] Marcon | The operating theatre planning by the follow-up of the risk of no realization[END_REF]. [START_REF] Guo | Maximizing the efficiency of use of nurses under uncertain surgery durations: a case study[END_REF] established a new approach for nurse scheduling under uncertain surgery durations. The primary contributions of this paper include: first a mixed integer programming model that explores the trade-off between the two competing performance criteria: on-time surgery start and performance nurse efficiency, with respect to nurses, surgeons, and patients satisfactions'; second an explicit probability modeling of uncertain surgery durations that can be used for mastering on-time surgery start performance. [START_REF] Holte | The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care[END_REF] have elaborated an implementor/adversary algorithm for the cyclic and robust scheduling problems in healthcare. He introduces a mathematical model for a cyclic and the robust scheduling problem in healthcare and he has developed a row and column generation approach for its solution. The interest of this work is that the authors model both the uncertain and the cyclic allocation problem as adjustable robust scheduling problems.

This model solved real-life instances of surgery scheduling provided by a major hospital in the city of Oslo. [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] and [START_REF] Averbakh | On the complexity of minmax regret linear programming[END_REF] affirmed that different robustness optimality criteria could be adopted, according to the specific nature of the application.

Among the most, adopted ones are the following two criteria:

 Absolute robustness in which one wants to find the solution with minimum cost in its worst scenario;

 Robust deviation, also called min-max regret [START_REF] Averbakh | On the complexity of minmax regret linear programming[END_REF], the regret for a given solution (say x) is defined as the difference between the cost of x, obtained with its worst input instance, say y, and the cost of the best possible solution when the input is y;

For the strategic and tactical OR planning problem, [START_REF] Tancrez | Assessing the impact of stochasticity for operating theater sizing[END_REF] proposed a Markov chain based model to account for the uncertainty of surgical times in an OT that handles both elective and emergency cases and has a limited PACU capacity. For the same levels, [START_REF] Holte | The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care[END_REF] proposed an adjustable robust scheduling model to build MSSs that account for the variability of the demand for surgical cases.

Critical point of view

The Surgery is teamwork: multi-agent, multi-objective, multi-resource. Therefore, if we want to obtain an optimal scheduling; we must consider the coherence between all stakeholders of the operative act. Despite the OR, scheduling problem is much studied: there are some decisive actors, which are not enough, discussed in the literature: for example:

 The working hypotheses of many mathematical models are not applied in reality; so they do not reflect reality. Our goal is to approach modeling to the reality.

 An unexpected event can occur and disrupt scheduling (failure of a device, sudden illness of a member of the operating staff, accident…); these events must be considered when preparing the scheduling.

 The resources used are of three kinds: material resources, human resources, and informational resources, most of the research focused on the first two types of resources. The informational resources that are of paramount importance have not been treated to my knowledge.

 The robustness of OR scheduling is not well treated, also the costs of underutilization or over-utilization of materials and human resources are not well treated, is not highlighted especially in the public hospital. The traceability of the equity of resource distribution also is not studied enough.

Despite all the done work, hospital scheduling systems are not sufficient to solve the problems in the field since all work is carried out with existing resources, which are a real handicap, especially in poor countries, or limited resources, and emergencies are difficult to program because one can never predict exactly.

Observe that few of the related articles consider together a variety of factors. The latter could affect the scheduling process; e.g., case priorities based on criticality and delayed start times, multiple resources (ORs, surgeons, nurses, and equipment) and their availability, multiple days in the scheduling window, time off-day assignment, and surgeon performance (which could affect the duration of the surgery on that day).

We believe that a comprehensive surgical case scheduling model, even though deterministic, is essential to generating truly implementable schedules and to further our understanding of the complexity of the problem, based off of which advanced stochastic programming models may be developed in the future.

Conclusion

In this chapter, we reviewed manuscripts on OR planning and scheduling that have recently appeared. We analyzed the contributions of a set of research in various fields. We emphasized the most important trends and we illustrated important concepts through the citation of key references. We furthermore allow tracking specific contributions over the Then, we solve the problem with Cplex resolver. From the optimal solution obtained by Cplex resolution, an efficient schedule is built. This approach provides nearoptimal solutions as well as which makes possible to evaluate the quality of the solutions obtained. The numerical experiments show that this approach makes possible to find near-optimum solutions in a very short calculation time.

Introduction

In a hospital organization, the operating theater presents the most complex service, because of the human and material resources that it immobilizes and the more and more restrictive constraints. It is also one of the most critical services of the hospital with the highest costs and income [START_REF] Macario | Where are the costs in perioperative care?: Analysis of hospital costs and charges for inpatient surgical care[END_REF]. In addition, the operating block is considered the focal point for many activities of the hospital [START_REF] Chaabane | Une approche hiérarchique d'aide a la décision pour la gestion des blocs opératoires[END_REF]. Thus, the optimization of its use has become an obligation to achieve the compromise between the economic gain and the assurance of the safety of the interventions in the block.

Based on our exhaustive review of the literature, we concluded that the Hospital management area and the planning of operations faced the same challenges, and they encountered the same types of problems (lack of material and human resources, emergency, uncertainty in operating times ...) with some degree of difference viewing the wealth of some countries compared to others.

According to Pauline et al. (2016), patient waiting time is frequently considered as the best measure for the quality of care, especially in an increasingly complex atmosphere like healthcare.

Also [START_REF] Cardoen | Operating room planning and scheduling: A literature review[END_REF] affirmed that minimizing patients' waiting time, reducing the number of cancellations, the leveling staff workload and improving the overall performance of a hospital are among the relevant performance indicators. These goals can be reached by an efficient surgery planning and scheduling.

In order to manage and coordinate the different activities of the operating theater, hospitals use a management tool called operational programming [START_REF] Kharraja | Outils d'aide à la planification et l'ordonnancement des plateaux médico-techniques[END_REF][START_REF] Jebali | Vers un outil d'aide à la planification et à l'ordonnacement des ressources dans les services de soins[END_REF][START_REF] Chaabane | Une approche hiérarchique d'aide a la décision pour la gestion des blocs opératoires[END_REF]).

The operational program or a schedule is a sort of agenda that specifies for each OR the patients who will be operated, their order and their hours of passage.

The time horizon can range from one day to several weeks. The programmed interventions can come from one or more surgical services depending on the type of mono or multidisciplinary block.

Intervention requests may be known one or more months in advance, as in the hour preceding the establishment of the operating program according to the policy adopted in the block.

According to [START_REF] Magerlein | Surgical demand scheduling: a review[END_REF]Martin, 1978, Fei, 2006) In this chapter, we are interested in the problem of assigning a set of surgeries on each workday in an OR suite. We try to minimize the completion time or the makespan which involves the minimizing of the overuse and the underuse of the OR suite, by controlling the overtime and the idle time.

This problem plays a decisive role in utilizing OR efficiently, which is of paramount importance for OR suites to provide high quality service at ever reduce the cost of trading off between the two performance criteria idle time and overtime.

We formulate the problem as a mixed integer programming (MIP) model, we are concerned in improving OR efficiency in terms of overtime and idle time. The MIP model is validated by small instances then it will be applied to a large size instances, and the results will be compared with the actual performance of the concerned OR suite.

The problem of planning consists now in determining the date of intervention for every elective patient as well as the OR where the intervention will take place; taking into account the uncertain surgery duration.

In order to generate a generalized surgeries scheduling, we take into consideration the different steps of surgeries.

Figure 3.2 Surgery flow and involved resources in OR management. (Xiang et al. 2014)

In this chapter, a new technique that improves the surgery schedule is suggested. We have developed a new approach that can be applied to any hospital system. In the next chapter, this approach resolution takes into account the specificities of some surgical department found in the literature [START_REF] Landa | A hybrid optimization algorithm for surgeries scheduling[END_REF][START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]). However, with some change in the parameters, this study can be valid for all Hospital systems.

Problem statement

The problem we are studying is considered as the problem of scheduling mono-disciplinary

ORs using an open programming approach. We assume that the operating planning stage was carried out in advance where the patients are assigned to a horizon F. The N scheduling jobs model the patients.

The problem can be defined as follows: a set N of n tasks must be processed on a horizon F of, f days. Every day there is a set R of identical ORs available. Each of them must perform the same set M of m operating phases.

Every day is available to handle all tasks; once a task j, j ∈ N is assigned to a day f, f ∈ F it cannot be transferred to another day before being completed. The task execution time j in room r, at day f is denoted Pj,i,f.

Our goal is to find a sequence of tasks during the days which minimizes the biggest date of completion of works (global makespan) of every day in order to minimize the overtime, noted by Cmax = MAX {Cmax1, Cmax2, ..., Cmaxx, ..., Cmaxy, ... CmaxF}, respecting certain constraints that will be presented in the next section.

Depending on the operational planning strategy used and the simplification assumptions made, the OR scheduling problem may have certain specificities and be modeled in different ways. Indeed, it can be considered as a Job Shop with duplicated machines [START_REF] Saadani | Ordonnancement des blocs operatoires[END_REF], generalized job shop [START_REF] Pham | Surgical case scheduling as a generalized job shop scheduling problem[END_REF]. A three-stage hybrid flow shop [START_REF] Kharraja | Block scheduling: Toward a master surgical schedule[END_REF] or a two-stage hybrid flow shop [START_REF] Fei | Vers un outil d'aide à la planification et à l'ordonnancement des blocs opératoires[END_REF]. Alternatively, a distributed permutation flow-shop scheduling problem [START_REF] Xu | An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem[END_REF]. In addition, it can be considered as a distributed no-wait flow shop [START_REF] Shao | Optimization of makespan for the distributed no-wait flow shop scheduling problem with iterated greedy algorithms[END_REF].

We have inspired our scheduling problem from the problem of distributed permutation flowshop scheduling workshops (DPFSP), [START_REF] Naderi | The distributed permutation flowshop scheduling problem[END_REF] with the addition of the following time constraints (no-wait and release when completing blocking (RCb)). Dauzère-Pérès et al., 2000, have studied the RCb constraints in the first time. In this model, a fictitious intervention 0 is assigned to all the rooms for every day, and consequently, the indices k and j start with 0. In addition, a fictitious phase 0 is assigned for all the interventions, and consequently the index i starts with 0.

Decision Variables

 𝑋 𝑓,𝑟,𝑘,𝑗 ∶ Binary variable that takes the value 1 if the intervention j takes place at position k in the sequence of interventions that will be performed in the room r, at day f and 0 otherwise.  𝐶 𝑚𝑎𝑥 : Continuous variable that represents the maximum of the completion times of all the interventions for the whole horizon F (makespan global).

Objective function and constraints

Our principal objective is to obtain an efficient and feasible OR scheduling that models the reality, optimizes the patient's satisfaction, and can be applied to schedule any OR. The objective is to minimize simultaneously patient waiting time and completion time in the SS.

One of the strong points of this model is its attachment to reality of what really happens in the operating block. Taking into account, in the surgery planning, the different stages gives a touch of reality to our scheduling and makes generalizing the model in other operating units, and in other hospitals possible.

We have formulated the model as follow:

(P1) Objective function 𝑀𝑖𝑛 𝐶 𝑚𝑎𝑥 (3.1) Subject to 𝑋 𝑓,𝑟,𝑘,0 = 1 ∀ 𝑓, 𝑟, 𝑘 (3.2)
∑ ∑ ∑ 𝑋 𝑓,𝑟,𝑘,𝑗 = 1 ∀ 𝑗 > 0 𝑁 𝐾=1 𝑅 𝑟=1 𝐹 𝑓=1 (3.3) ∑ ∑ ∑ 𝑋 𝑓,𝑟,𝑘,𝑗 ≤ 1 ∀ 𝑘 > 0 𝑁 𝑗=1 𝑅 𝑟=1 𝐹 𝑓=1 (3.

Description of the constraints

The objective function expresses the minimization of the makespan.

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝐶 𝑚𝑎𝑥

(3.1)

 Constraint 3.2
Constraints related to the fictitious intervention that is assigned in every OR for every day.

𝑋 𝑓,𝑟,𝑘,0 = 1 Makespan formula for all rooms for every day.

∀ 𝑓, 𝑟, 𝑘 (3.2)
𝐶𝑚 𝑓,𝑟 ≥ 𝐶 𝑓,𝑟,𝑀,𝑘 ∀ 𝑓, 𝑟, 𝑘 (3.12)

 Constraints 3.13

Maximum makespan formula among all the rooms of every day.

𝐶 𝑚𝑎𝑥 ≥ 𝐶𝑚 𝑓,𝑟 ∀ 𝑓, 𝑟 (3.13)
 Constraints 3.14

Respecting the number of hours worked per day.

Experimental results

In order to verify the validity of the proposed method, we carried out several experiments.

The mathematical model discussed in this chapter was formulated as a mixed integer linear program (MILP). Moreover, it was programmed in A Mathematical Programming Language (AMPL). It was solved with IBM ILOG CPLEX Optimizer STUDIO 12.3 software tool. We used a personal computer with Intel®Core i5-3612QM CPU @ 2.1 GHz processor with 8 GB RAM to perform experiments.

For the larger test instances, the model cannot be solved to optimality within a reasonable time. In such instances, we program to use a more performing engine and to implement a suitable metaheuristic of resolution.

This section includes current scenarios, proposed model calculations, and results with different sets of instances that prove the performance of the obtained schedules.

In order to test the efficiency of our approach, which we want to be efficient for all surgical unit, we carried out tests on a set of randomly generated instances; we test the efficiency of the algorithm by changing the size of instances randomly. Comparisons with previous and similar works will be established later proving the effectiveness of our developed approach and its capacity to adapt to larger instances.

Generation of instances

In order to test the efficiency of our model, and verify its capacity to endure the variation of parameters, we generate a set of random instances,

The generated instances should give a good indication of the model's performance. We want to execute the program on small instances and a larger one. The small instances are generated randomly as indicated previously; moreover, larger instances are prepared based on the benchmark [START_REF] Landa | A hybrid optimization algorithm for surgeries scheduling[END_REF][START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF].

Experimental results

As explained in the previous section, we begin the execution of the program with a small set of the instance. The latter is tested on a bigger set of instances. Moreover, we check the capacity of the resolution of the problem in a short time execution and acceptable values of performance indicators.

The daily problem A) A small example: Schedule generation

In order to verify the validity of the proposed method, we carried out several experiments; we start with a small example.

Suppose we have two ORs and eight patients with different surgery duration, we note the duration of the three phases of surgery as summarized in Table 3.3. By applying the program we get the following scheduling represented by the following chart of Gantt. The diagram presented in Figure 3.3 shows a balance between the tasks. In this example, we suppose that 1 slot time = 15 min.

Table 3.3 Estimated operations duration

Preoperation

Perioperation

Post

Figure 3.3 Gantt chart for a daily schedule

B) A daily schedule

We start by applying our program on a detailed surgery-scheduling problem, with a planning horizon of one day. Our test instance generator generates the patients themselves.

We generate 6 instances. The instance name indicates the number of projects (operations or patients). For example, d-12_01 is a daily problem instance with 12 patients.

For each instance, we have generated a number of possible scenarios by randomly changing the duration of the operations.

We fixed the OR number to two; we change the number of operations and the duration of the 3 phases of the operating activities. We run the program for all instances and correspondents' scenarios.

For each instance, we generate 10 scenarios; we report the maximum, the minimum, the average and the standard deviation of solutions values at the chosen computation time limits.

The overall measurement results obtained by running the following instances are summarized in Table 3.4. seconds. The computational analysis confirmed the aptitude of the proposed approach to deal efficiently with the trade-off between hospital managers and patient perspectives in reasonable computational times.

We note that the variation of the number of operations and the surgery duration involve the variation of the value of the objective function, which is logic. We note that Stv. value of the instance 4 is the smallest between the other instances, we note that this instance, presents a more balance against the other instances set. We can conclude that the ideal number of operations assigned is fourteen.

The application of our approach avoids the over-utilization of the OR with all the involved material and human resources since it avoids the idle time and maximizes the use of all available resources.

We remark the respect of the time offered. Of course, this parameter can be changed to test the limits and the ability of our scheduling, if we want to treat urgency cases. The decision maker or the scheduler of the concerned operating block can change the parameters and decide if they allow overtime, the number of desired operations, the resources that can they sacrificed to increase patients' satisfaction etc.

Figure 3.4 The impact of the variation of patient number on CT

The weekly problem

From the benchmark of [START_REF] Landa | A hybrid optimization algorithm for surgeries scheduling[END_REF] and [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]. We generated two different benchmark sets which characteristics are summarized in Table 3.

CT Number of patients

Recall that N: presents the intervention number, R is the operating rooms number and TVO presents the offered vacation time. When running program with weekly instance the execution time increase considerably, the execution stops without reaching the optimal solution. In addition, the instances with more than 2 operating rooms cannot be resolved by a deterministic resolver because the problem becomes NP-Hard and needs a metaheuristic to reach a near-optimal solution, as noted in the previous section.

For the generation of large instances (in order to generate weekly and monthly scheduling)

and the application of the benchmark of [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF], and the benchmark of Landa et al.

(2016) we will treat it as prospects and will be published later.

Conclusion

In this chapter, we have presented a model that captures a wide range of real-world elective operational surgery scheduling problems. We have shown how this model extends the multiresource constrained project-scheduling problem. Our model covers some constraints, which to our knowledge have not been studied together previously. In addition, we have solved the proposed model and drown results.

Therefore, we have developed a new scheduling approach that can be applied to any hospital system. The larger random instances will prove the efficiency and the reliability of the In this chapter, we propose a stochastic model for OR planning by taking into account the perturbation due to uncertainty of surgeries duration. One solution to overcome these problems is to build a robust scheduling, able to maintain these performances in the event of uncertainties. The planning problem determines, for a given horizon, the set of patients and the respective surgeons, who will be assigned each day in such a way as to minimize the makespan. The latter allows minimizing the costs and increasing the utilization of OR. Then. We formulate this Problem in the form of a stochastic mathematical program and we propose a meta-heuristic method of resolution, which is the PSO optimization, the stochastic aspect of this method allows realizing a robust scheduling and a clear improvement of the used performance indicators.

Introduction

When planning ORs, one of the main questions hospital managers are faced with is how the available OR capacity should be allocated in order to improve the efficiency and the productivity and how can the efficiency be attained and measured. Efficient management of the OR is strongly associated with the integration of the uncertainty of the surgery duration when planning surgical procedures. However, as we saw in the previous chapter, most approaches and models do not take this type of uncertainty into account.

The main objective of our work is to establish an efficient system that can control and organize The stochastic model is developed for a surgical suite in ophthalmology surgery department of a public Tunisian hospital. We should point out that the patient assignment model studied here is in fact a stochastic version of the SCAP which is NP-hard in its deterministic version [START_REF] Bowers | Managing uncertainty in orthopaedic trauma theatres[END_REF][START_REF] Landa | A hybrid optimization algorithm for surgeries scheduling[END_REF]2016); efficient exact solutions for solving realistic sized instances of the problem studied here are therefore unlikely.

We propose a metaheuristic approach to solve the problem. However, we hypothesize that the duration of interventions assigned to a given room has the same variance and that the sum of these durations follows a lognormal distribution [START_REF] Landa | A hybrid optimization algorithm for surgeries scheduling[END_REF]2016).

Problem description

In our case study hospital, demand widely exceeds the supply, since it is a regional hospital, it receives patients from all southern Tunisia, usually it is common to suspend a surgery in order to promote emergencies; this problem can be solved by adding a third OR, which is impossible now, due to the lack of space in the hospital. Therefore, we must work with the available resources. An optimal schedule can clearly improve the number of surgeries performed; which will increase the patient satisfaction by reducing the time of waiting.

In the hospital of our study, every three days a list of operations is prepared by the head of the department and his assistants following an order depending on the patient's condition, they obtain complete information for registration and insurance certification. They discuss among the most urgent cases, they check the patient's folder, estimate the time allocated for every operation, schedule all procedures for pre-operative services and ensure an adequate time to each procedure.

In addition, they check the surgeon's daily schedule and confirm all cases with OR's reorganization to ensure that all surgery schedules are post carefully with the correct arrangement, they communicate with the surgeons and supervisors to verify changes and avoid conflicts.

The following table presents the list of most recurrent surgeries practiced in ophthalmology service in the case study hospital. The originality of the present study is in integrating the notions of efficiency and robustness to a surgery-scheduling problem, which provides maximum patient satisfaction and respecting the equity of resource allocation, especially surgeon and nurses, taking into account the uncertainty cases.

In order to obtain an efficient schedule, we must minimize the average makespan. To evaluate the scheduling robustness, we will use the probability of delays. The OR schedule is a powerful tool that assists hospital-wide communication and staffing. Supervising surgeries' costs enables the hospitals to provide an overall higher quality of care by reducing the patient's wait time.

The stochastic mathematical model

Uncertainty is all around us; OR schedulers have a serious problem scheduling a random number of surgeries, with significant uncertainty in surgeries' durations and patient's arrival time. Our goals are to minimize the overuse of operating resources by minimizing the makespan average while maximizing the OR's performance rate; for this, we try to develop an efficient and robust OR schedule.

The scheduling makespan is the total time that has elapsed from the beginning of a certain task to its end, denoted Cmax. A scheduling is efficient if its average makespan is minimized, whereas a scheduling is robust if it maintains its performance in the presence of uncertainties [START_REF] Canon | A comparison of robustness metrics for scheduling dags on heterogeneous systems[END_REF].

There are many consensuses to measure the robustness; specified by canon and Jeannot, ( 2008), one of them is the Lateness probability introduced by [START_REF] Shi | Robust task scheduling in nondeterministic heterogeneous computing systems[END_REF]. The authors affirm that a scheduling is late if its total duration Cmax exceeds a given value (the expectation of Cmax for example). The probability of delay is a value that we seek to minimize it is defined as:

𝐿 = Pr[𝐶𝑚𝑎𝑥 > 𝐸(𝐶𝑚𝑎𝑥)] (4.1)
A schedule is late if its makespan exceeds a given target such as the average makespan. The lateness probability is defined as the probability to be late. If this metric is large this means that the makespan tends to be often late and then that the robustness is low. Therefore, this metric is a value that we want to minimize.

The objectives of this paper are a twin. The first is to provide an efficient algorithm to solve the problem of equity of human resource allocation, especially nurses, which is very beneficial to reduce overtime and the cancellations of surgery.

The second is to provide a tool to develop a robust OR schedule, which considers the tradeoff between the uncertainties of surgery duration while maximizing the operating block utilization.

To solve our problem, we develop efficient tools, simple to implement in the real context, and useful to assist the decision-maker.

Problem assumptions

We present a stochastic programming model for the surgery-scheduling problem. The following assumptions are made in developing our model:

 Only one surgeon can perform a surgical case. However, a surgeon may perform more than one case and in multiple ORs during a given day.

 The duration of intervention of the patient includes preparation time, surgery, and duration of room cleaning and reconditioning; so the induction time for each operation and the cleanup time before leaving the OR are included in the operating time or operation duration.

 Surgical case durations known in advance.

 Idle time between interventions is generated randomly.

In the model (P1), we optimize the work of all the surgical team in relation to the most valuable material resource that is the OR.

However, the model (P2) is interested in the robustness of the planning taking into account the satisfaction of the surgeons and the variability of surgeries duration.

In order to guarantee the efficiency and the robustness of the scheduling, the lateness probability of delay must be equal to a random value 𝛼 or less, which could be used as a realistic estimation, we present in the following the model's notation.

Parameters and variables of the model

Resolution method

The stochastic model presented in the previous section, (which is a stochastic model), since it contains a chance constraint, is NP-hard [START_REF] Landa | A hybrid optimization algorithm for surgeries scheduling[END_REF]. We solved and validated the model in its deterministic form with the ILOG.CPLEX solver using small instances.

If we take the parameters closest to reality (what is in the service), the size of the instances increases and the model takes longer to be solved with the ILOG.CPLEX solver.

For this reason, and to obtain an acceptable solution to the problem within a reasonable time, that is to say a near optimal solution or an achievable solution, we need a metaheuristic approach; metaheuristics are generally more efficient and less resource intensive/time than an exact method.

So an efficient metaheuristic was required to solve larger problem instances. Consequently, realistic problem instances are difficult to solve. Our preliminary tests suggest that the model was able to solve problems up to 15 patients, time 600 min per day with a horizon of 5 days, 2 ORs, and 8 surgeons in 10 hours on a Pentium 4 processor with 512 MB RAM. Such problem instances are not representative of real-world instances, which are much more complex and require a schedule to be generated in a matter of minutes. Consequently, an efficient metaheuristic was required to solve larger problem instances. We next present one such efficient metaheuristic. In the following, we present a method of resolution for this new problem.

A metaheuristic resolution method

As metaheuristic optimization approach, we choose the Particle swarm optimization.

Presentation: A Particle swarm optimization (PSO) algorithm

PSO is an intelligent optimization algorithm invented by [START_REF] Kennedy | Particle swarm optimization[END_REF], also introduced by Eddeli et al. (2016) and [START_REF] Azimifar | Optimization of characteristics of an array of thin fins using PSO algorithm in confined cavities heated from a side with free convection[END_REF]. This approach simulates the behaviors of bird flocking.

PSO is initialized with a group of random particles, representing probable solutions to the problem, and then searches for optima by updating generations and using a fitness function, in our case it is the makespan.

The swarm consists of N particles. Each particle i may be represented through m-dimensional vectors: the first one is denoted by 𝑋 𝑖 𝑗 = {𝑥 𝑖1 𝑗 , 𝑥 𝑖2 𝑗 , … , 𝑥 𝑖𝑚 𝑗 }, 𝑖 = (1,2, … , 𝑁), that indicates the position of the particle i in the searching space at the iteration j.

The second vector is 𝑉𝑒𝑙 𝑖 𝑗 = {𝑣𝑒𝑙 𝑖1 𝑗 , 𝑣𝑒𝑙 𝑖2 𝑗 , … , 𝑣𝑒𝑙 𝑖𝑚 𝑗 } that represents the velocity with which the particle i moves. The third vector is 𝑃 𝑖 j = {𝑝 𝑖1 𝑗 , 𝑝 𝑖2 𝑗 , … , 𝑝 𝑖𝑚 𝑗 } that denotes the best position of the i-th particle and the last one is 𝐺 𝑖 𝑗 = {𝐺 𝑖1 𝑗 , 𝐺 𝑖2 𝑗 , … , 𝐺 𝑖𝑚 𝑗 } that represents the global best position in the swarm until j-th iteration.

At each iteration j, the particle i adjusts its velocity and its position according to the previous personal best position𝑝 𝑖 𝑗-1 and the previous global best position 𝐺 𝑗-1 by using the following equations:

𝑣𝑒𝑙 𝑖𝑘 𝑗 = 𝑣𝑒𝑙 𝑖𝑘 𝑗-1 + 𝑐 1 𝑟 1 (𝑝 𝑖𝑘 𝑗-1 -𝑥 𝑖𝑘 𝑗-1 ) + 𝑐 2 𝑟 2 (𝐺 𝑗-1 -𝑥 𝑖𝑘 𝑗-1 ) (4.19) 𝑥 𝑖𝑘 𝑗 = 𝑥 𝑖𝑘 𝑗-1 + 𝑣𝑒𝑙 𝑖𝑘 𝑗 (4.20)
where 𝑐 1 and 𝑐 2 are learning factors. 𝑟 1 and 𝑟 2 are random numbers between [0,1]. The particle uses the stochastic mechanism of PSO algorithm to escape from local optima.

PSO pseudo-code

Pseudo-code of PSO algorithm is presented as follow:

Pseudo-code of PSO algorithm

PSO algorithm for surgeries scheduling 4.5.1 Fitness function

The fitness function in our case is the makespan value, calculated for each particle using the expected operation duration for each patient assigned to day d in an OR o.

Definition of a particle

Our swarm contains N particles, each particle 𝑥 𝑖 𝑗 is represented by a matrix representing an operative day schedule, the rows represent the ORs, the columns represent the number of operations, and each case of the matrix contains the patient number with the corresponding surgeon. The constraints of shift working and the number of days surgeons' work are respected and the patient p is assigned only once a day.

PSO parameters

Table 4.3 explains the parameters used in the implementation of the PSO algorithm.

Experimental results

This section summarizes the results of this work and draws conclusions.

Description of Data Set

We are interested in the ophthalmology department in a Tunisian hospital; the operating theater in this hospital is composed of two ORs and eleven recovery rooms with three beds each. All the ORs are open from 8:00 am to 6:00 pm.

In this study, the experiments are based on two months' data from 1 st January 2015 to 28 th February 2015. We have collected and sorted the useful information to construct our database (Amami et al;2016, 2017a) Table 4.4 summarizes data from the surgery department of the hospital of interest.

Performance indicators

The selected Performance indicators used to evaluate our approach are:

 TROS: the time when a surgical activity takes place in the time scheduled.

 OROR: the ratio of the real room occupancy time (TROS) to the time allocated of surgeries.

𝑂𝑅𝑂𝑅 = ∑ 𝑇𝑅𝑂𝑆 ∑ 𝑇𝑉𝑂

 PSP: the ratio of the number of patients scheduled for the involved week to the number of patients awaiting the assignments.

 Cmax: the makespan.

Computational results

The proposed method has been executed by a program coded by MATLABR2013b on a DELL (Dual core CPU: PM 2.6 GHz, memory: 2.0 GB, Operating System: Windows 7).

The implementation of the PSO algorithm is applied on a swarm that contains 50 particles, each particle represents a random probable daily schedule, that contains the wanted number of patients operated on one day in the two ORs, which is 16 patients, operated by 8 surgeons, the operative week contains five days. The program is iterated 100 times.

Results with fixed surgery duration

In this sub-section, we applied our approach without integrating the variation of the surgery durations to test its effectiveness. Then we will integrate the variability of the operating times.

Moreover, we will check the reliability of the solutions obtained in the next sub-section.

As shown in figure 4.4 and 4.5, the constraints of material and human resource allocation are respected; for example; a surgeon practices only one shift per day and the equity between surgeons is guaranteed. The analysis of performance indicators of the scheduling realized by the proposed approach shows a clear improvement, especially PSP which increases from 48.7 % to 100%. It is interesting to note that the number of operations is increased and all awaiting patients are operated. The number of the operated patient increases by 51.3% by using the same material and human resources. In addition, we remark a large improvement in the average value of Cmax compared to the number of operated patients.

In addition, the values of OROR also show a remarkable improvement, an average improvement by 20 % of OROR that are good indications of enhancement. Moreover, significant costs of the operating theater can be saved.

The surgery duration used in this section is the deterministic surgery duration checked in real data from the hospital of study, so the deviation parameter 𝜎 is not integrated.

The main objective of our study is the realization of an efficient and robust scheduling that minimizes the makespan, while increasing the OR utilization rate, consequently increasing the number of interventions performed. These objectives can be reached by realizing a surgery scheduling that respects the balance of tasks between various resources such as ORs and surgeons. This approach takes into consideration, apart from the constraints of human and material resources, the problem of uncertainty that usually disrupts the planning of operations, to avoid these defects altogether; we must prepare a robust planning that allows a random margin of uncertainty. The solution reliability is expressed by the chance constraints (4.3) which limits the probability 𝛼 ∈ [0,1] that the daily makespan is greater than Cmaxborne. The latter can be considered as the mathematical average of different values of Cmax.

Commonly the easiest way to integrate probabilistic constraints in a model is the use of scenarios (a reasonable number to be able to trace the probability law) so there will be an index s per decision variable and a probability of occurrence of each scenario.

The resolution method exploits PSO techniques combined with Monte Carlo simulation to deal with the uncertainty and the variability of surgery durations.

A stochastic scenario generation procedure is established in order to generate the value 𝜀 𝑝 of each surgery 𝑝 ∈ 𝑃, following a predetermined distribution probability 𝐹 𝜀 𝑝 .

In the literature, several authors recommend the use of the lognormal distribution for simulating surgery times (Hancock et al. 1988[START_REF] Zhou | Method to assist in the scheduling of add-on surgical cases-upper prediction bounds for surgical case durations based on the log-normal distribution[END_REF][START_REF] Strum | Modeling the Uncertainty of Surgical Procedure TimesComparison of Log-normal and Normal Models[END_REF][START_REF] Kharraja | Outils d'aide à la planification et l'ordonnancement des plateaux médico-techniques[END_REF][START_REF] Dexter | Tactical decision making for selective expansion of operating room resources incorporating financial criteria and uncertainty in subspecialties' future workloads[END_REF].

So the stochastic surgeries durations are generated by lognormal random variables using mean μ equal to the patient expected surgery time and as standard deviation 𝜎.

The principal objective of this procedure is to measure the reliability and so to check the feasibility of each solution.

The choice of the 𝛼 and 𝜎 parameters values can have a significant impact on the final solutions. A sensitivity analysis of their impact was performed to provide additional perceptions into the algorithm behavior.

To evaluate the reliability of the solution we use mainly as metrics the makespan as introduced in constraints (4.3) of the stochastic model (P2) and the OROR of the OR blocks. As can be observed, the percentage improvement decreases when the variability of the surgery durations increases. If α and 𝜎 exceed a certain limit (above 30%) it is more difficult to maintain the solution feasibility (with respect to the chance constraints).

Despite the observed effect on the results, the solutions provided by our approach are efficient and acceptable since our approach is based on the balance of loads and the equality of distribution of the tasks between the different stakeholders. Therefore, a limit of α and 𝜎 maintains its abilities. So scheduling robustness is guaranteed. (Amami et al;[START_REF] Amami | A PSO approach to optimize the robustness of surgery scheduling[END_REF]

Conclusion

This chapter presented an efficient approach for solving the problem of assigning and sequencing a set of patients to a set of available OR time blocks, for a one-week planning horizon, while taking into account the uncertainty of surgery durations. Therefore, we develop a stochastic model that reflects the reality of most constraints encountered in the block of the case study; we resolve the model with the PSO algorithm. A set of instances based on real data and random instances based on Monte Carlo simulation has been constructed to test the reliability and the robustness of the solutions produced. The computational analysis demonstrated the capability of the proposed method to deal efficiently with the trade-off between the hospital and patient perspectives.

Despite the efficiency confirmed by the suggested approach, it has not yet been integrated into the hospital practice. The main reasons are linked to difficulties in introducing and interfacing stand-alone resolution methods into the hospital information systems.

Conclusion and future work

The objective of this thesis was to develop optimization models and tools for the planning and the scheduling of the ORs, taking into account the uncertainty due mainly to the emergency surgery and the variability duration of surgical procedures. In the first chapter, we have described the different forms of planning and scheduling of the ORs; we emphasized the uncertainty that characterizes the environment of the operating block and we stressed the importance of considering them during the planning. In Chapter 2, we presented a literature review on methods and approaches developed for the management of operating theater.

We have noted the dominant use of deterministic approaches for the operating block planning;

approaches that ignore all forms of uncertainty and not integrate them in planning. However, the recent research give more importance to the uncertainty cases have shown that the success of a planning is linked by its approach to reality and must take into account the uncertainty surrounding the hospital area.

In the third chapter, we have proposed a new generalized approach for improvement in solving the problems related to the surgeries planning, which allows patients to be allocated to surgical rooms. To minimize the costs generated by the over-use of operating theater for this we changed the assumption related to surgery duration, we divided surgery duration into three steps, in order to detect the reason of idle time, which leads to expensive overtime. We tested different instances to evaluate the performance of this approach. The tests have shown that this approach provides approximate solutions that are very close to the optimum in a very short calculation time, for problems of realistic sizes.

Through experimentation, we have illustrated the effectiveness of this approach and have shown that significant material and human gains can be achieved by using a stochastic approach to the planning of the OR.

In the fourth chapter, we proposed a stochastic model for the proactive robust planning of the surgeries, taking into account uncertainty of surgery duration. In this chapter, we assumed that the ORs are versatile, and only the overall capacities of all the ORs are considered. In this planning model, we are interested in determining the dates of the intervention of patients. The assignment of patients to specific surgery rooms and the specific surgeon are taken into account.

We have formulated the problem of planning in the form of a stochastic mathematical model.

We proposed an optimization method that uses PSO approach to solving the problem. The result obtained by this method shows a great improvement in the performance indicators despite the level of uncertainty.

To recapitulate, we considered, within the framework of this thesis, the problem of planning under uncertainties in the OR. We have proposed mathematical models processes that capture the essential elements to consider when planning surgical activities, allow explicit modeling of different forms of uncertainties such as the uncertainties concerning the duration of the interventions and the emergency surgeries, and can be easily extended to model other constraints due to practices. We have developed optimization approaches for the stochastic planning of the OR. By means of experiments, we evaluated the performance of these different approaches and we have shown their effectiveness. In particular, we have shown that significant gains can be achieved through stochastic modeling of the problem of planning the OR.

This thesis opens the way to many research perspectives essentially on two levels:

improvement of optimization methods and the enrichment of planning models.

In chapters 3 and 4, we proposed different planning models that allow the modeling of uncertainty in surgery duration, and we have developed different resolution approaches.

We note that some constraints (concerning the availability of surgeons, the adequacy of ORs, or the deadlines for interventions) can be easily taken into account explicitly, by defining for each patient an explicit set of rooms-days in which the patient can be planned. The models and the resolution approaches proposed can easily integrate this type of restrictions. However, it would be interesting to test the sensitivity of the results extensions.

The proposed approaches could represent a useful decision tool to be used by OR managers to determine efficient OR schedules (i.e., planning and sequencing of patients). These approaches had the advantage of exploiting the tradeoff between achieving an acceptable level of OR utilization rate while limiting the negative effects.

The prospects of our work are multiple. First the mathematical models presented in the thesis assumed that the ORs represent the only few critical resources. In the future, it would also be interesting to include other resources such as Recovery rooms, hospital beds, intensive care room, etc. In addition, we think to add some constraints that are closer to reality and give us results that are more efficient. For example constraints that allow the computing of the costs of over-use of the operating theaters and the overtime of the medical staff and what engenders the use of the electric energies and the expensive devices.

Another perspective concerning the integration of a Lean healthcare technique, for example, the kaizen approach helping us to more precise the preferences of surgeries, assisted simulation tools to achieve these objectives.

…………………

: 2 : 4 :Table 4 . 2 :Table 4 . 4 :

 244244 Figure 1.1: Evolution of tunisian hospital bed ................................................................

Figure 1 . 2 :

 12 Figure 1.2: TMDA .........................................................................................................

Figure 1 . 3 :

 13 Figure 1.3: TVO .............................................................................................................

Figure 1 . 4 :

 14 Figure 1.4: TROS ...........................................................................................................

Figure 1 . 5 :

 15 Figure 1.5: Emergency and elective patient flow in the hospital adapted and modified from (tan et al., 2007b) ............................................................................................

Figure 1 . 6 :

 16 Figure 1.6: Patients flow at CHU H B Sfax...................................................................

Figure 2 . 1 :

 21 Figure 2.1: Overview schema of the simulation-optimization approach (Juan et al. 2015) ........................................................................................................................

Figure 3 . 1 :

 31 Figure 3.1: Hierarchical approaches to schedule elective patients in the hospital (Testi et al., 2007) ..............................................................................................................

Figure 3 . 2 :

 32 Figure 3.2: Surgery flow and involved resources in OR management. (xiang et al. 2014) ........................................................................................................................

Figure 3 . 3 :

 33 Figure 3.3: Gantt chart for a daily schedule ..................................................................

Figure 3 . 4 :

 34 Figure 3.4: The impact of the variation of patient number on CT .................................

Figure 4 . 1 :

 41 Figure 4.1: Partition of surgeries on ORs during january 2015 .....................................

Figure 4 . 2 :

 42 Figure 4.2: Partition of surgeries on ORs during february 2015 ...................................

Figure 4 . 3 :

 43 Figure 4.3: Partition of surgeries on ORs during 2015 ..................................................

  .................................................................................................... 1.2 Healthcare system ............................................................................................ 1.2.1 Objectives and challenges ....................................................................... 1.2.2 The Tunisian health care system ............................................................. 1.2.3 Classification of Hospital........................................................................ 1.3 Operating room blocks component ................................................................ 1.3.1 Description of operating rooms ............................................................ 1.3.2 Operating room characteristics ............................................................. 1.3.3 Relationship between operating block and the other departments ....... 1.3.4 Operating room's indicators ................................................................. 1.3.5 Type of surgeries .................................................................................. 1.3.6 Patient types .......................................................................................... 1.4 Operating room planning and scheduling ...................................................... 1.4.1 Research value ...................................................................................... 1.4.2 Approaches to prepare operating room schedules ................................ 1.4.3 Scheduling under uncertainty ............................................................... 1.4.4 Scheduling and robustness .................................................................... 1.5 Habib Bourguiba Hospital: an introduction ................................................... 1.6 Thesis organization ........................................................................................

  Tunisian healthcare systemTMOH (2014) proposed the solution to build a public health research center. The center could be designed as an academic and a research-based institution having an autonomous administration and an independent funding system. Its affiliated scholars represent the whole range of the public health field such as public health professionals, economists, and health policy experts. Its first mission will be the development of the previously mentioned strategy and its implementation with the collaboration of the government, medical schools, hospitals, innovators, administrators, leaders... As a first step, the center should develop a common public health framework for project planning, implementation, and evaluation. This framework must be a consistent tool for planning current health strategies, improving existing programs, and evaluating the old and the new results of the different investments. It should be a conjoint device for evaluating the different strategies planned by different stakeholders. Stand by to the different steps and standards of this framework will tolerate an understanding of each program's context and will improve how the programs are conceived and conducted.

Figure 1 . 1 :

 11 Figure 1.1: Evolution of Tunisian hospital bed

Figure

  Figure 1.1: TMDA 1.3.4.2 The Offered vacation time: TVO

Figure

  Figure 1.2: TVO

Figure 1 . 5 :

 15 Figure 1.5: Emergency and elective patient flow in the hospital adapted and modifiedfrom(Tan et al., 2007b)

  disturbances resulting in changes in the operating program are due to the emergency surgery. Referring to a Canadian hospital, Carter (2006) reports that 50% of Cardiac surgeries are performed as part of the emergency surgery. Another study in four Belgian hospitals (Rossi-Turk, 2002) reveals that an average of 20% of the activity of the OR is an emergency activity. Thus, good programming of interventions depends directly on the ability to anticipate the needs of emergency surgery, hence the need to consider this when planning of OR activities.

  CHUHB was created in 1986, it is classified as a teaching hospital since 1993, was established as a public health institution under the Ministry of Public Health (Category A) according to the law 56-92 on 06/09/1992. It has legal personality and financial autonomy.It is considered among the most important health facilities in Tunisia. It is a social institution that aims to improve the public health level of curative and preventive measures.In fact CHUHB is the most important health material of the region, which further includes two university hospitals, three hospitals of circumscriptions, an outpatient treatment center and diagnostic hundred and thirty basic health center, in addition to the private structure developed enough (16% of the region beds). Moreover, the training plane CHU Constitute a field trip for students in the Graduate School of Science and Health Technology and Health professional school. Students of the Faculty of Medicine of Sfax University Hospital found an excellent environment to complete their training practices (160 students between internal and residents). The hospital also hosts trainees in management and biomedical training. The hospital CHU HB is a surgical hospital in the essentially vocation of 535 beds; it has 27 medical hospital services presented by the figure below.

Figure 1 . 5 :

 15 Figure 1.5: Patients flow at CHUHB Sfax

  Bougerra et al. (2015) addressed a mathematical model for maximizing OR utilization. The main objective of the proposed model is to maximize OR utilization and to minimize the idle time between planned surgeries. The proposed model takes into account the surgeon's availability.

  this model in a real-life situation show a great improvement in the OR use by minimizing the makespan, minimizing overtime hours.Other interesting research established by[START_REF] Vijayakumar | A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital[END_REF], they presented a surgical case scheduling problem practiced at a publicly funded hospital. A MIP model and a heuristic based on the first-fit decreasing algorithm are developed to resolve a multiresource, multi-period, priority-based case-scheduling problem as an unequal-sized, multibin, multi-dimensional dual bin-packing problem. The presented results have shown a great optimization, thus we note the following improvements: 20% reduction in the number of days and up to 20% increase in OR utilization once compared to actual schedules obtained from the surgical department at a publicly funded hospital. Despite the improvements noticed by this research, it has been done better by taking into account the uncertainties cases.

  Granja et al. (2014) prepared a simulation-based optimization approach to the patient admission Scheduling Problem is presented. Simulation techniques and modeling tools are used in the optimization of a diagnostic imaging sector. The proposed techniques have confirmed to be effective in the estimation of diagnostic imaging workflows. The authors used a simulated annealing algorithm to optimize the patient admission sequence towards minimizing the total completion time and the total waiting of patients. The developed results

  [START_REF] Ghazalbash | Operating room scheduling in teaching hospitals[END_REF] elaborated a new mixed integer programming model minimizing the total idle times of ORs and the Cmax that represent the completion time of the last patient's surgery. The number of deferred, refused or canceled patients may also evaluate the quality of a planning or scheduling procedure.[START_REF] Kim | Adaptive supply serial links with sub-1-V operation and per-pin clock recovery[END_REF], for example, studied how to include quotes in the surgery scheduling process in order to restructure the access to the ICU. In particular, they tried to decrease the number of canceled elective surgeries that result from ICU bed shortages, without significantly worsening the waiting times of other patients who are seeking admission to the ICU. Financial criteria make up an alternative performance perspective.[START_REF] Dexter | Tactical decision making for selective expansion of operating room resources incorporating financial criteria and uncertainty in subspecialties' future workloads[END_REF] proved how adequate planning and scheduling contributes to an increased contribution margin, which they defined as revenue minus variable costs. It should be noted that research efforts are not limited to the identification of best practice. For example,[START_REF] Dexter | How to schedule elective surgical cases into specific operating rooms to maximize the efficiency of use of operating room time[END_REF] formulated a linear programming model in which the variable costs are maximized in order to determine the worst-case scenario.

  [START_REF] Aringhieri | Assigning surgery cases to operating rooms: A VNS approach for leveling ward beds occupancies[END_REF] exploited the flexibility of the variable VNS, to provide a solution framework; they have shown that it could be easily adapted to operative contexts M'Hallah et al. (2014) had addressed a planning and scheduling of operating rooms by a simulation approach, the new contribution of this paper investigates how to enhance the OT's expected under and over utilization while maintaining the current average number of surgical cases in general and of the major ones in particular. Specifically, it considers two methods that reduce the overutilization of the OT: canceling surgical cases at the on-line operational level, and limiting the workload planned at the off-line operational level building a simulation model for each strategy, and compares the model's output to that of the current situation. It assesses the utility of each strategy based on statistical inferential techniques.[START_REF] Hongying | A Survey of Recent Research on Optimization Models and Algorithms for Operations Management from the Process View[END_REF] established column generation procedures to prepare weekly OR schedule. Then OR daily schedule is prepared with the help of a hybrid genetic algorithm.The constraints of the study are relaxed. For example, there is no limitation on the recovery beds and any room can accommodate any surgical specialty, which is not the case in actual practice. Houdenhoven et al. (2007) used bin-packing algorithm to assign OR blocks in MSS. The paper also utilizes portfolio technique (technique widely used in the financial stock markets) to reduce non-utilized OR time. The study splits OR blocks in the OR schedule. The recovery area is not considered. The model is validated with a Dutch hospital. Lamiri et al. (2008) developed a stochastic model for OR planning with the combination of elective and emergency surgery demands. The model design includes the processing time for each possible arrival and cost of underutilization of resources. The Monte Carlo convergence algorithm is helpful to solve problems for the emergency patients. Aringhieri et al. (2014) seek to optimize both patient utility (by reducing waiting time costs)and hospital utilization (by reducing production costs measured in terms of the number of weekend stay beds required by the surgery planning). They used a 0-1 linear programming formulations exploiting the stated hierarchy are proposed and used to derive a formal proof that the problem is NP-hard. Then two level metaheuristics are developed for solving the problem and its effectiveness is demonstrated through extensive numerical experiments carried out on a large set of instances based on real data.[START_REF] Aringhieri | Assigning surgery cases to operating rooms: A VNS approach for leveling ward beds occupancies[END_REF] interested in assigning surgery cases to ORs, state that this work aims to optimize the level of the post-surgery ward bed occupancies during the days. In addition to that, the authors exploited the flexibility of the variable VNS. This variable provides a solution framework, shown to be easily adapted to operative contexts.[START_REF] Choi | An approach to optimize block surgical schedules[END_REF] dressed a prototypical non-linear, stochastic programming model to structure relevant and practical features of the problem and four adaptations, along with associated solution approaches, with the goal of facilitating solution by overcoming the computational disadvantages of the prototype. Each of these adaptations offers advantages but is also attended by the disadvantages.Computational tests compare the four adaptations and solution approaches with respect to solution quality and runtime. The objective is to minimize total expected costs due to penalties for any patients who are not accommodated and for under-(i.e., idleness) and over-(i.e., overtime) usage of OR capacity Several optimization methods have been used to solve combinatorial optimization problems (COPs), among them the simulation and meta-heuristics methods, a new approach appears: simheuristics, as presented by[START_REF] Juan | A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems[END_REF], (see fig 2.1) which describes a general methodology for that, allows extending metaheuristics through simulation to solve stochastic (COPs). 'Simheuristics' allow modelers and research to address the real-life uncertainty in an expected approach by integrating simulation into a metaheuristic-driven framework.

Figure 2 . 1

 21 Figure 2.1 Overview schema of the simulation-optimization approach (Juan et al. 2015)

  [START_REF] Van Essen | Minimizing the waiting time for emergency surgery[END_REF] established simulation modeling to illustrate the effect of inserting emergency surgical cases on the on-line operational level where emergency cases arrive according to a Poisson process and the surgical times of elective cases follow a Lognormal distribution. They investigate the insertion procedure that minimizes the waiting time of emergency cases.[START_REF] Ma | A multilevel integrative approach to hospital case mix and capacity planning[END_REF] applied an integrated approach for the four levels of OR planning and scheduling. The developed approach uses mutually the mathematical integer programming and the simulation tools for resolving the strategic and operational levels problems, respectively. Their approach accounts for different lengths of stay of surgical patients and resource availability. Its main goal is to establish the best-case combine of surgical cases and aptitude level of elective surgical cases. For the strategic level,[START_REF] Choi | On capacity allocation for operating rooms[END_REF] modeled the allocation of ORs to specialties as a non-linear stochastic problem that minimizes the expected costs of cancellation, over and underutilization of the OT. They proposed and compare four solution approaches that are based on the newsvendor model.[START_REF] Azari-Rad | A simulation model for perioperative process improvement[END_REF] applied simulation modeling to determine the impact of perioperative processes, scheduling and sequencing rules in the proportion of canceled surgical cases in an OT that handles both elective and emergency surgical cases. Several stochastic approaches are available for the off-line OR planning.[START_REF] Lamiri | Optimization methods for a stochastic surgery planning problem[END_REF]

  [START_REF] Saadouli | A stochastic optimization and simulation approach for scheduling operating rooms and recovery beds in an orthopedic surgery department[END_REF] provided a discrete event simulation model to compare the new model and the head surgeon actual practice to evaluate the global performance of the proposed model. The efficiency of the suggested solution is then validated by an illustrating example, which shows that a substantial amount of operations and hence cost can be saved. Two types of resources are considered: OR and Recovery Beds (RB). The problem consists of optimizing the assignment of surgeries to OR's and planning the recoveries in order to avoid them in the OR's when no bed is available in the recovery room.The proposed solution takes into account the uncertainty in surgery and recovery durations and the capacity of resources.[START_REF] Altamirano | Low-frequency quasi-periodic oscillation from the 11 Hz accreting pulsar in Terzan 5: not frame dragging[END_REF] proposed a particle swarm optimization algorithm to determine the shifts assignment of nurses (i.e., Day shift, Emergency day shift, And Emergency Night Shift) at a French public hospital.Unfortunately, these studies fall into the category of tactical nurse rostering problem at medium term (1 or 2 weeks), in which collective agreement requirements such as legal regulations, personnel policies are the major concerns(Cheang, Li, Lim, & Rodrigues, 2003).

  [START_REF] Harper | A framework for operational modelling of hospital resources[END_REF], for instance, presented a detailed hospital capacity simulation model that enables system evaluations by means of scenario analyses. The participation of multiple hospitals in the development phase resulted in a generic framework that allows incorporating uncertainty or trends in the arrival profiles of patient groups as well as duration varies (e.g. length of stay or surgery durations).[START_REF] Persson | Analysing management policies for operating room planning using simulation[END_REF] described a discrete-event simulation model to study how resource allocation policies of the department of orthopedics affect the waiting time and utilization of emergency resources, taking into consideration together surgery duration variability and patient arrival uncertainty.Note that simulation is often preferred as the solution technique to study complex stochastic settings, as it features an extensive modeling flexibility. In addition, of patient arrival and duration uncertainty, other types of uncertainty are addressed.[START_REF] Dexter | Managing risk and expected financial return from selective expansion of operating room capacity: Mean-variance analysis of a hospital's portfolio of surgeons[END_REF], for instance, examined to what extent uncertainty in the estimated contribution margin of surgeons (characterized by standard deviations) may lead to lesser allocations of OR ability while the target is to maximize the hospital's estimated financial return.For the strategic and tactical OR planning problem,[START_REF] Tancrez | Assessing the impact of stochasticity for operating theater sizing[END_REF] proposed a Markov chain based model to account for the uncertainty of surgical times in an OR that interest at the same time into elective and emergency cases and has a limited PACU capacity. For the same levels,[START_REF] Holte | The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care[END_REF] proposed an adjustable robust scheduling model to build MSSs that account for the variability of the demand for surgical cases.

3. 3 . 2

 32 Parameters of the model .......................................................................... 3.3.3 Decision Variables .................................................................................. 3.3.4 Objective function and constraints .......................................................... 3.3.5 Description of the constraints .................................................................. 3.4 Experimental results ......................................................................................... 3.4.1 Generation of instances ........................................................................... 3.4.2 Experimental results ................................................................................ 3.5 Conclusion........................................................................................................We are interested in optimizing the scheduling of the operating theater with an account of the hazards caused by surgery duration. In this chapter, the problem of scheduling is to determine the set of elective patients who will be operated in each OR and every day over a given planning horizon. The objective is to minimize the costs of overuse and under-use of ORs by minimizing the makespan. We reformulate the scheduling problem in the form of mixed integer programming (MIP) model.

  Figure 3.1 Hierarchical approaches to schedule elective patients in the hospital[START_REF] Testi | A three-phase approach for operating theatre schedules[END_REF]

Figure 3 . 2 (

 32 Figure 3.2 (Xiang et al. 2014), depicts the surgery flow and the involved resources in OR management used during the three steps of the operating process. It also presents the different phases of the surgery involved in different type of resources and takes as variable the slot of time.

  𝑋 𝑓,𝑟,𝑘,𝑗 = { 1 if the intervention j takes place at position k in the sequence of interventions that will be performed in the room r, at day f and room r 0 otherwise. 𝐶 𝑓,𝑟,𝑖,𝑘 : Continuous variable that represents the end time of the intervention, in the position k for stage i in the OR r, at day f.  𝐶𝑚 𝑓,𝑟 : Continuous variable that represents the end time of all interventions in the OR r, at day f (makespan per room per day).

4 )

 4 𝐶 𝑓,𝑟,0,𝑘 = 0 ∀ 𝑓, 𝑟, 𝑘 (3.5)𝐶 𝑓,𝑟,𝑖,0 = 0 ∀ 𝑓, 𝑟, 𝑖 (3.6)𝐶 𝑓,𝑟,𝑖,𝑘 = 𝐶 𝑓,𝑟,𝑖-1,𝑘 + ∑ 𝑋 𝑓,𝑟,𝑘,𝑗 * 𝑃 𝑗,𝑟,𝑖,𝑘 ≥ 𝐶 𝑓,𝑟,𝑀,𝑘-1 + 𝑀𝐵 * ∑ 𝑋 𝑓,𝑟,



  Constraint 3.3 Each intervention occupies exactly one position in the same sequence of interventions in an operating room for one day. Limit that each position in a sequence of interventions is occupied by at most one intervention ∑ ∑ ∑ 𝑋 𝑓,𝑟,𝑘,𝑗 ≤ No waiting time between the phases of an intervention 𝐶 𝑓,𝑟,𝑖,𝑘 = 𝐶 𝑓,𝑟,𝑖-1,𝑘 + ∑ 𝑋 𝑓,𝑟,𝑘,𝑗 * 𝑃 𝑗,An intervention can only begin in an operating room in a day when the previous intervention performs all its phases 𝐶 𝑓,𝑟,𝑖,𝑘 ≥ 𝐶 𝑓,𝑟,𝑀,𝑘-1 + ∑ ∑ 𝑋 𝑓,𝑟,The treatment of an intervention k in phase i can begin only after the treatment of the intervention k-1 in phase M is finished.𝐶 𝑓,𝑟,𝑖,𝑘 ≥ 𝐶 𝑓,𝑟,𝑀,𝑘-1 + 𝑀𝐵 * ∑ 𝑋 𝑓,𝑟,𝑘,

Figure 3 .

 3 Figure 3.3 depicts the Completion Time (CT), as a function of patients' number; it presents the impact of the variation of the patient number on the completion time. This figure shows that there is an equilibrium between different values of CT, justified by the small size of the instances.

  5: each benchmark is composed of four instances by varying the number of operations N. the number of ORs R and the OR time block duration TVO. If the number of ORs exceeds 2 this problem becomes NP-Hard. This part of the problem will be treated and published in an article.

  obtained scheduling by scheduling the wanted number of patients. Reducing the waiting time, which is most of the performance indicators in relation to patient satisfaction. Patient satisfaction has an indirect influence on team satisfaction and costs reducing.

  the appointments and take care of their cancellation and rearrangements. The problem focuses on creating a proactive robust MSS (Master Surgical Schedule) based on the available number of resources hours, materials, human resources … This step seeks a robust assignment of the set of patients to the available OR time blocks in such a way as to maximize the overall OR utilization while leveling the OR blocks utilization over the planning horizon. The solution must satisfy the operational constraints regarding the OR block's length.Healthcare optimization problems are challenging, often requiring the adoption of unconventional solution methodologies. The solution approach proposed in this chapter belongs to this family.We first develop a stochastic mathematical model. The planning problem (P2) is a combinatorial stochastic (nonlinear) problem. The latter is determined based on patient expected surgery durations while respecting surgeon capacity, availability, and preference of shift work (working the shift of morning or the afternoon shift).

Figure 4 Figure 4 . 2 andFigure 4 . 1 Figure 4 Figure 4 . 3

 44241443 Figure 4.2 and Figure 4.3 represent, respectively the repartition of surgeries on ORs during January, February 2015 and the partition of surgeries on ORs during the year 2015

Tables 4 .

 4 5 and 4.6 present comparisons made between the actual surgery schedules and the surgery schedules obtained by the proposed method and the actual surgery schedules for the scenario are performed with indicators introduced in the previous section. The stochastic mechanism of PSO guarantees a significant improvement in the values of performance indicators.

Tables 4 .

 4 7 and 4.8 represent the impact of the variation of the two parameters α and σ on the reliability of the solution. Recall that α and σ represent, respectively the value of reliability and the level of variability of surgeries duration. (When α increases, the level of reliability decreases).

  other surveys are presented; we mention the survey of cardoen, Demeulemster, and Belien (2010), which classified the problems with the patient's condition (elective or nonelective). A measure of performance (waiting time, makespan, idle time, the rate of utilization, patient referrals, financial measures…), decision type (date, time, duration etc.),

research method (problem considered, solution technique, and constraints), uncertainty (deterministic against stochastic), and efficiency of the technique.

The notion of robustness of the scheduling OR as the solution to the uncertainty, trouble is also considered in different research. Several studies are available. We present a review of recent research on OR planning and scheduling classified by the theme of interest.

  [START_REF] Augusto | Operating theatre scheduling with patient recovery in both operating rooms and recovery beds[END_REF] examined the impact of a situation where the patient starts recovery in the OR due to the non-availability of recovery bed in the recovery unit. They developed an open scheduling approach, in which patients are scheduled deprived of any surgical constraints. The study concluded that profit is high while recovery unit utilization rate is high. Each patient data is used to construct OR schedule. Lagrangian relaxation heuristic is established to solve the problem efficiently.

Table 2 .1 Summary of resolution method

 2

					Resolution method
	Authors	Date	Objective
				MIP	H or MH	Simulation
	Saremi et al.		Scheduling of outpatient surgical services.	X	X Tabu search	X Real data
	Navneetkumar et al.		Optimization of Post-Capacity Surgery Recovery Unit	X	X
						X
	Tancrez et al.		Assessing the impact of stochasticity for OR sizing.			Markov
						theory
	Lin et al.

Table 3 .1 The parameters used

 3

	Parameters	Description
	N	Interventions number
	M	Intervention phases' number
	F	Scheduling horizon
	R	OR number
	Pj,i	Necessary duration for accomplishing the phase i
		of intervention j
	TVO	Total surgical time
	MB	Large positive constant

Table 3 .2 The variables of the model

 3

	Index	Role	Scale
	j	Index of intervention	{1,2,…, N}
	k	Position of an intervention in a sequence {1,2,…, N}
	i, m	Indices of a phase of the intervention	{1,2,…, M}
	f	Day of intervention index	{1,2,…, F}
	r	OR index	{1,2,…, R}

Table 3 .4 results of the daily instances.

 3 By varying the data set, we test the ability of our solution to generate daily planning in short time. The results present the values of objective function that is 𝐶 𝑚𝑎𝑥 measured in

	Instance	Avg.	Min.	Max.	Stv.	Computational time(s)
	d 10-01	457.500	414.000	566.000	38.380	50
	d 12-02	555.375	523.000	566.000	18.679	66
	d 13-03	536.375	521.000	595.000	24.779	70
	d 14-04	584.25	565.000	595.000	4.573	94
	d 15-05	552.125	549.000	574.000	10.214	84
	d 16-06	562.875	546.000	568.000	10.165	88

Table 3 .5 Set of weekly random instances B1 B2

 3

	Id	N	R TVO	Id	N R TVO
	1	85	4 540	5	128 6 600
	2	98	4 540	6	163 6 600
	3	100	6 600	7	199 6 700
	4	115	7 600	8	230 6 700

Table 4 .1 List of most recurrent surgeries practiced in ophthalmology service Nature of Intervention Estimated Duration

 4

	Vitrectomy	1 H 30 min
	Cornea transplant	1 H 30 min
	Faco-aspiration	45 min
	DCR ( dacreo-cystite) 1 h
	Strabismus	1 h
	Potosi	45 min
	Cataract	45 min
	Trabectomy	1 h
	Lacrimal	10 min
	The problem of the weekly OR's scheduling of the ophthalmology surgery division of the
	CHUHB can be resumed as follows: a set of n operations to be scheduled on o ORs and
	executed by s surgeon groups, on a special day d with time t. An interesting point in this
	service is that demands exceed widely supplies. A lateness in executing surgeries and a large
	number of daily postponements are observed, because of uncertainty and other human
	resource constraints (sickness, absence etc.). That is why the rate of performance of ORs
	equals 48.5% whereas the normal value is from 75 to 80 % (MEAH, 2012).

Table 4 .

 4 2 presents the variables and parameters of the model.

Table 4 .2 Variables and parameters used

 4 The objective function expresses the minimization of the makespan.State that at most one surgery can be scheduled in an OR on a given day and time.Ensure that each surgeon can perform at most one surgery on a given day and time.Express the end time for the patient's surgery.

	Parameter	Description
	𝑝	Set of patients requiring a surgery 𝑝 ∈ (1,2, … , 𝑃).
	𝑆	Set of surgeons available on a workday 𝑠 ∈ (1,2, … , S).
	𝐷	Index of day 𝑑 ∈ {1. .5}.
	𝑇	Index of slot time during ; t=1,2,…,T.
	𝑂	Set of OR o ∈ (1,2, … , O).
	𝐼	Set of nurses available on a work days 𝑖 ∈ (1,2, … , I).
	𝑟𝑖 𝑝	Number of nurses required for surgery
	𝑑 𝑝	The surgery duration of patient p
	𝑚𝑎𝑥 𝑖𝑑	Maximum hour of work per day for nurse i
	TVO	Offered vacation time
	𝐶𝑚𝑎𝑥𝑏𝑜𝑟𝑛𝑒 Reasonable value of 𝐶𝑚𝑎𝑥: limit that we do not want to exceed
	𝛼	User-defined value 𝑤𝑖𝑡ℎ 𝛼 ∈ [0,1]
	σ	Variability of 𝑑 𝑝 σ ∈ {0.1 ,0.15, 0.2,0.3 }
	𝑠ℎ1	Shift of working surgeon = {0, 1, 2} with 0: rest, 1: morning, 2:
		afternoon.
	𝑠ℎ2	Shift of working surgeon = {1, 2} with 1: morning 2: afternoon
	4.3.3 Decision variables
	 𝑥 𝑝𝑜𝑠𝑑𝑡 : binary variable identify if patient p is scheduled in OR o by surgeon
	s, on day d at time t;
	1 if patient p is scheduled in OR o by surgeon s on day d at time t 𝑥 𝑝𝑜𝑠𝑑𝑡 = { 0 otherwise

Constraints 4.15, 4.16, 4.17 and 4.18 are

  integrity constraints.

	𝑥 𝑝𝑜𝑠𝑑𝑡 ∈ {0,1} ∀ 𝑝, 𝑜, 𝑠, 𝑑, 𝑡	(4.15)
	𝑦 𝑠𝑑𝑠ℎ1 ∈ {0,1}	∀ 𝑠, 𝑑, 𝑠ℎ1	(4.16)
	𝑦 𝑠𝑑𝑠ℎ2 ∈ {0,1}	∀ 𝑠, 𝑑, 𝑠ℎ2	(4.17)
	𝑧 𝑖𝑝𝑑 ∈ {0,1}	∀ 𝑖, 𝑝, 𝑑	(4.18)

Table 4 .3 PSO parameters

 4

	Parameter	Description	value
	N	Size of the swarm " number of birds "	50
	bird_setp	Maximum number of birds steps	100
	MatR	Dimension of the problem	2
	MatC	Dimension of the problem	8
	C1	PSO parameter C1	0.12
	C2	PSO parameter C2	1.2
	w	PSO momentum of inertia	0.9
	r1	Random matrix	rand(MatR,MatC)
	r2	Random matrix	rand(MatR,MatC)

Table 4 .4 Summary of the Database

 4

	ORs	2
	Principal surgical specialties	12
	Number of surgeons	17
	Number of nurses	11
	Availability of surgeons	2-3 days/week
	Availability of nurses	6-8/day
	Expected surgery duration	0.15-1.5 hour per case

Table 4 .5 Numerical results for the scenario with 80 patients awaiting assignment and 30 surgeons

 4

	Method	PSP (%)		TROS (minutes)	OROR (%)	Cmax (minutes)
	Actual surgery schedule	48.7	Min Mean Max	260 307.5 390	43 53 59	520 533.5 570
	Schedule obtained by the proposed method	100	Min Mean Max	385 426 470	71 73 76	415 458 495

Table 4 .6 Comparison between the real schedule data and PSO

 4

	Date	Comparison	TROS(minutes)	Cmax(minutes)	OROR (%)

St_dev Min Max St_dev Min Max St_dev Min Max

	Monday Tuesday Wednesday Thursday Friday 0.01 4.6.3.Real data 106.07 415 435 88.39 410 540 0.16 PSO 21.23 345 415 21.21 395 425 0.04 Real data 90.61 375 510 28.28 510 550 0.05 PSO 31.82 360 410 31.32 410 460 0.02 Real data 49.50 315 390 67.18 395 490 0.05 PSO 10.00 370 460 14.15 395 425 0.00 Real data 91.92 265 305 109.60 365 520 0.15 PSO 21.22 315 345 21.21 415 440 0.04 Real data 31.82 220 335 49.50 345 380 0.08 PSO 25.35 415 440 35.36 380 430	41 76 42 72 36 73 46 69 31

2 Evaluating robustness scheduling under uncertainty of surgery duration

Table 4 .7 Impact on average Cmax with varying α and σ parameters.

 4

	α		5%	10%	15%	20%	25%	30%
		10%	395	432	440	452	540	551
	σ	15% 20%	415 442	448 480	459 487	479 510	590 600	598 612
		30%	530	545	558	519	630	639

Table 4 .8 Impact on average OROR with varying α and σ parameters.

 4

	α		5%	10%	15%	20%	25%	30%
		10%	71.30% 70.13% 65.00% 55,60% 48.22% 39.86%
	σ	15% 20%	67.05% 63.50% 59.89% 51.45% 43.67% 35.09% 53.65% 50.00% 47.43% 39.00% 33.65% 24.22%
		30%	45.00% 41.02% 35.44% 27.49% 24.90% 18.75%

Acknowledgments

PhD THESIS To obtain the degree of doctor in Management Sciences

Exhaustive approaches to optimize the robustness of surgeries scheduling List of symbols 𝛼: User defined value level of reliability of the obtained solution.

𝜎: The level of variability of surgeries duration.

The robustness as a solution of uncertainty cases

Another trend in scheduling optimization is the notion of robustness; the robustness approach is one of the newest approaches to deal with the uncertainty of scheduling problems. It allows for the initial scheduling to be set in such a way that changes in data during the implementation of the schedule will have a minimal impact on the primary scheduling.

In spite of its importance, the issue of robustness in scheduling under uncertainty has received relatively little attention, especially in the field of healthcare and OR scheduling.

This intuitive notion has led to a lot of different interpretations and metrics. Among them, [START_REF] Kouvelis | Robust discrete optimization and its applications[END_REF] defined three robustness measures for the scheduling problem and developed a mathematical model for the problem of single machine scheduling and a twomachine flow shop. Later [START_REF] Canon | Evaluation and Optimization of the Robustness of DAG Schedules in Heterogeneous Environments[END_REF] performed an experimental study on these different metrics and show how they are correlated with each other. Furthermore, the authors proposed different policies for minimizing the makespan whereas maximizing the robustness of the scheduling: from an evolutionary metaheuristic (best solutions but longer computation time).

In addition, [START_REF] Lin | A new robust optimization approach for scheduling under uncertainty:: I. Bounded uncertainty[END_REF] applied an innovative robust optimization approach to mixedinteger linear programming (MILP) problems; this later produces robust results that are resistant to bounded uncertainty.

In a single machine environment and total completion time as their objective function, [START_REF] Yang | On the robust single machine scheduling problem[END_REF] used the scenario-based planning with uncertain processing time to achieve robust scheduling. They also proposed a dynamic programming algorithm and two heuristic algorithms, one with a complexity of 𝑂(2 𝑛 ) and the other with polynomial complexity of 𝑂(𝑛 4 |𝑆|) and the other with a polynomial complexity of 𝑂(𝑛𝑙𝑜𝑔𝑛 + |𝑆|𝑛), where |𝑆| refers to the number of scenarios. In addition. [START_REF] Briceño | Robust static resource allocation of DAGs in a heterogeneous multicore system[END_REF] established a measure that quantifies robustness in a heterogeneous environment. There are several metrics for describing the robustness of the schedule with regard to the makespan as explained in canon (2010).

For a horizon H of F days, for each day we have identical ORs that correspond to identical factories found in the DPFSP. Each of them must perform the same set of M operating phases, in the DPFSP that correspond to the identical machines. No waiting time between the operating phases of an intervention and between interventions (no-wait). Moreover an OR r remains blocked by a task until its completion (RCb).

The representation of the DPFSP problem with time constraints, no-wait and RCb using the notation introduced in [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF] and allowing the classification of the scheduling problems using the triplet

This problem is known to be NP-Hard when F ≥ 3, according to [START_REF] Naderi | The distributed permutation flowshop scheduling problem[END_REF].

Model formulation

In this section, our target is to develop an algorithm, which produces an optimal solution that covers the constraints of OR scheduling and solves realistic instances in a short time.

The diversity of surgery scheduling problems can be handled through generalization.

Moreover, a generalized model can be applied to a large set of operating block that belongs to a large set of the hospital.

Problem assumptions

Because of the complexity of the problem, we have simplified the model concerned by posing the following assumptions: we assume that:  All patients are operated at time zero.

 Once started, an operation cannot be interrupted until it is finished.

 Each patient is operated in at most one OR and each OR can process only one patient at the same time.

 All ORs are polyvalent, thus each surgery can be performed in any OR.

 Each OR must be assigned to at least one patient in each day.

 The ORs are available continuously (no breakdowns).

Parameters and variables of the model

The model parameters' and variables have been presented respectively in table 3.1 and table

3.2.

The most important restraint of our model is that it if the number of ORs exceeds 2 the problem becomes NP-hard and can't be resolved by the deterministic resolver. By implementing a meta-heuristic and generating a great number of instances. We can decrease the effect of this limit. Future research will be continued in this direction by evaluating the appointment rules delivered by the deterministic model using a discrete event simulation model (DES). The DES model can take into account different sources of variability such as the unpunctual arrivals of patients and the variation of service times etc.

In the next chapter, we developed a new approach that takes into account the specificities of the surgical ophthalmology department of the CHUHB. However, with some change in the parameters, this study will be valued for all hospital systems.

Objective function and constraints

Our principal objective is to obtain an efficient and robust OR scheduling, that models the reality, optimize the patient's satisfaction, allows us to compute many indicators of performance such as the OR' performance rate, makespan,...