الگوريتم شاخه و كران براي يك مسيله‌ي دو‌هدفه‌ي زمان‌بندي اطاق‌هاي عمل

A BRANCH-AND-BOUND ALGORITHM FOR A BI-OBJECTIVE OPERATING ROOM SCHEDULING PROBLEM

موضوع مورد مطالعه در اين نوشتار «زمان‌بندي اطاق‌هاي عمل» است كه در آن انجامِ هر عمل جراحي به چهار مرحله تقسيم‌بندي شده، و منابع اصلي مورد نياز هر مرحله جراحان و اطاق‌هاي عمل هستند. اين مسيله‌ توسط يك مدل برنامه‌ريزي عدد صحيح مختلط فرموله شده كه در آن تخصيص بيماران به اطاق‌هاي عمل، و توالي عمل‌هاي بيماران هر اطاق طوري تعيين مي‌شود كه تابع هدف دو‌معياره ي ميزان اضافه‌كاري جراحان و فواصل بيكاري بين جراحي‌هاي آن‌ها كمينه شود. به‌منظور حل مسيله‌، يك الگوريتم شاخه و كران توسعه داده شده و با توليد نمونه مسايلي، كارايي الگوريتم بررسي شده و حساسيت برخي پارامترها مورد تحليل قرار گرفته است. براساس نتايج ارايه شده، بهتر است 20‌درصد به طول كل زمان جراحي‌هاي هر جراح اضافه كرده و آن را به‌عنوان طول بازه كاري وي در نظر بگيريم زيرا بازه هاي كاري بزرگ‌تر هيچ گونه بهبود چشم‌گيري در جواب بهينه نخواهند داشت.

In this research, the operating room scheduling problem is studied. During recent years, this problem has attracted many researchers in an effort to reduce costs and raise the quality of health services. In this article, a surgery is divided to four steps and the required resources for each step are determined, where surgeons and operating rooms are the main critical resources. For this problem, a mixed integer programming model is developed, in which, assignment of patients to rooms and, also, the sequence of patient surgery, are determined, such that the bi-objective function, including additional work costs and idle time costs of surgeons, is minimized. This model is able to solve very small size problems in a reasonable time. Thus, a branch-and-bound algorithm has been developed to find an optimal solution, in each node of which, a patient is assigned to a room. The sequence of operations for patients of a room and also for patients of a surgeon is established using parent-child relations of the search tree. Moreover, in order to prevent the enumeration of repetitive nodes or the extension of nodes that surely will not improve the best found solution, four properties are developed. This algorithm has been implemented in C++ programming language and a set of test problems are generated to evaluate its efficiency and analyze the sensitivity of some parameters. Based upon presented results, the solution time is increased if each of the three following parameters is increased: Number of patients, number of surgeons or average number of possible rooms for each patient. In addition, it seems that if 20% is added to the total surgery time of each surgeon, this new time interval is proper to be considered as the working time interval, and longer intervals will not noticeably improve the quality of the optimal solution. It is shown in this paper that 0.25 is the best suitable coefficient for the idle gaps of surgeons in the objective function.