Metaheuristic Approach for the Facility Layout Problem in a Hospital

Les impacts d'un aménagement sur la performance d'une organisation dans les différentes industries et secteurs de services sont indéniables. Par conséquent, le besoin d'un système d'aide à la décision parmi les décideurs dans la planification de l'aménagement des installations a amené les problèmes d'aménagement des installations (FLP) à l'épicentre des recherches dans le domaine de l'optimisation. En tant que première partie d'une approche en deux étapes de la planification de l'aménagement des installations, cette recherche vise à concevoir et à mettre en œuvre un cadre d'optimisation pour proposer la meilleure allocation des services aux bâtiments et aux étages d'un futur hôpital près de Montréal, au Québec. Pour cela, une approche de programmation mathématique et plus précisément des problèmes de semi-affectation quadratique (QSAP) est utilisée pour modéliser ce problème d'aménagement d'installations. Le modèle QSAP adopte les quatre types de contraintes : affectation unique des points de service aux étages, disponibilité de l'espace d'un étage, affectation restreinte d'un point de service aux étages, et la contiguïté et la proximité au sein des points de service. L'objectif de ce problème d'optimisation est de minimiser le flux entre les points de service, ce qui peut inclure les déplacements des patients et du personnel et la manutention du matériel. Le modèle QSAP a été reformulé comme un problème linéaire à nombres entiers mixtes pour s'appliquer à l'un des solveurs MIP existants. La complexité du problème, qui est attribuée à la nature des problèmes combinatoires, empêche l'optimisation du problème de fournir une solution optimale en un temps polynomial. Ce problème réaffirme le fait que, malgré les formidables avancées observées dans le domaine du calcul numérique, qu'il soit logiciel ou matériel, l'utilisation des méthodes exactes dans les problèmes d'optimisation en taille réelle est encore inefficace. La recherche est passée de l'utilisation d'une méthode exacte au développement d'un optimiseur méta heuristique basé sur l'algorithme génétique, qui peut proposer une solution presque optimale avec une qualité acceptable dans un délai raisonnable. L'optimiseur a été mis en œuvre à l'aide d'une architecture multicouche et dans un environnement de développement de avant-garde. Une analyse statistique descriptive approfondie des résultats des expériences démontre : Avec quelle efficacité l'optimiseur converge vers une solution quasi optimale. Comment le processus de recherche optimal et les solutions sont sensibles aux modifications des paramètres de l'GA tels que la taille de la population, le taux de croisement, le taux de mutation, la taille du pool d'élite et la taille du tournoi. Et avec quelle efficacité l'optimiseur applique les contraintes aux solutions.

Abstract

The impacts of a layout on the performance of an organization in the different industries and service sectors are undeniable. Therefore, the need for a decision support system amongst decision-makers in the facility layout planning has brought the facility layout problems (FLPs) to the epicenter of the researches in the optimization arena. As the first part of a two-stage approach to facility layout planning, this research aims to design and implement an optimization framework to propose the best departments allocation to buildings and floors in a future hospital near Montreal, Quebec. For this purpose, an approach of mathematical programming and specifically quadratic semi-assignment problems (QSAP) is used to model this facility layout problem. The QSAP model adopts the four types of constraints: unique assignment of service points to the floors, floor space availability, and restricted assignment of a service point to floors, and the adjacency and proximity within the service points. The objective of this optimization problem is to minimize the flow between the service points, which may include traveling of patients and personnel and material handling. The QSAP model was reformulated as a mixed-integer linear problem to apply to one of the existing MIP solvers. The complexity of the problem, which attributes to the nature of combinatorial problems, prevents optimizing the problem from providing an optimum solution in a polynomial-time. This problem reasserts the fact that, despite the tremendous breakthroughs observed in the field of digital computation, whether software or hardware, using the exact methods in real-size optimization problems is still inefficient. The research has shifted its focus from using an exact method to developing a metaheuristic optimizer based on the genetic algorithm, which can propose a near-optimal solution with acceptable quality in a reasonable time. The optimizer has been implemented using multi-layer architecture and in a state-of-art development environment. A thorough descriptive statistical analysis on the results of the experiments demonstrates: • How effectively the optimizer converges to a near-optimum solution. • How the optimal search process and the solutions are sensitive to changes in GA parameters such as population size, crossover rate, mutation rate, the size of the elite pool, and the tournament size. • And how effectively the optimizer applies the constraints to the solutions.