An Emergency Department (ED) represents the gateway to every health care cen- ter. It opens 24 hours per day and 7 days per week. During the last years, the ED have benefited special attention. The goal is to offer a better quality of service to the pa- tient. In fact, the number of visits to EDs has greatly increased causing overcrowding and dissatisfaction of patients. Improving its efficiency as well as patients’ treatment is a significant challenge.
This thesis focuses on the scheduling of patients in ED. The problem is considered as a Hybrid Job Shop Problem (HJSP). The objective is to find a schedule that minimizes the total completion time or the makespan. This problem is a N P -hard combinatorial optimization problem. So, we developed and validated a Genetic Algorithm (GA) and a Hybrid Genetic Algorithm (HGA) by testing them on benchmarks found in the literature on manufacturing systems. The performances obtained were compared to existing HJSP approaches of the literature.
Then, we adapted and applied both algorithms to plan patient journeys in a Tunisian hospital ED, in which, we collected data. In ED, the objective is to min- imize patient waiting times in order to reduce the problem of overcrowding while taking into account the categories of patients. Particular attention must be paid to the categories of critical patients who must be quickly taken care of by a team. Initially, we only considered the expected patients and we simulated several scenarios to verify and measure the effectiveness of an approach based on patient categories, assuming that all data are perfectly known. Then, in a second step, considering all the reality of an emergency (i.e. with dynamics events), we took into account the uncertainties related to the patient arrivals and the duration of treatment provided by caregivers. Finally, we considered unexpected patients whose arrivals are unpredictable. To deal with these dynamic events, we studied a predictive and reactive planning strategy based on the previous algorithms. All the approaches were tested compared to the existing strategy based on the principle of "first come, first served" combined with a category priority rule which is usually found in emergency services. Results show that our approaches can improve the usual strategy when the rate of dynamic patients is under 50%.