Heuristics for the Operating Theatre Planning and Scheduling

Abstract

In this paper, we present a two-stage approach for planning and scheduling of operating theatres. The first stage concerns the operating theatre planning problem with the objectiveof minimizing number of days required to assign all surgical cases and number of days wasted for failure to meet surgical cases deadlines. The second stage refers to the operating theatre scheduling problem with the objective of minimizing total tardiness of surgical cases and total waiting time of surgeons in operating rooms. For each problem investigated, a mathematical formulation using a mixed integer programming has been suggested. And to solve the foregoing problems, we propose firstly a set of dispatching rulebased heuristics and secondly three metaheuristics. Finally, computational experiments are presented to compare the performances of these heuristics.

Dans ce papier, nous présentons une approche à deux niveaux pour la planification et l’ordonnancement des blocs opératoires. Le premier niveau concerne la planification des blocs opératoires avec comme objectif la minimisation du nombre de jours nécessaires à l’affectation de toutes les interventions chirurgicales et le nombre de jours dépassant les dates limites. Le deuxième niveau se résume à l’ordonnancement des blocs opératoires avec objectif la minimisation du retard total des interventions chirurgicales et du temps total d’attente des chirurgiens dans les salles d’opérations. Pour chaque problème examiné, une formulation mathématique utilisant la programmation mixte entière a été proposée. Et pour la résolution, nous proposons, en premier lieu, un ensemble d’heuristiques basées sur des règles de priorité, et en second lieu, trois méta-heuristiques. Finalement, des expérimentations ont été présentées pour comparer les performances de ces heuristiques.

Keywords:

• Operating theatre
• Genetic Algorithm
• Variable Neighborhood Search
• Iterated Local Search

Mots clés:

• bloc opératoire
• algorithme génétique
• recherche à voisinage variable
• iterated local search