UPM Institutional Repository

Solving single and bi-objective surgery scheduling problems using local search heuristic


Ab Rashid, Nur Shafiqah (2021) Solving single and bi-objective surgery scheduling problems using local search heuristic. Masters thesis, Universiti Putra Malaysia.


Due to the increasing number of elective patients required for surgery, the higher demand for an efficient and effective operating room planning in the health care sector is needed. Thus, better operating room planning is needed to prevent any complication to the patients for waiting too long for the treatment. A longer waiting time can affect the patient’s health condition if they are not treated in the specified time frame. It is essential to ensure that higher urgency patients get the surgeries done as soon as possible to avoid any health complications. An accurate estimation for the surgery duration is also one of the challenges in creating a good operating room planning. The surgeon assignment problem is completed after the scheduling case has been solved. The first problem is a single-objective surgery scheduling problem, where the surgeries are scheduled in the planning week by prioritizing the higher urgency patients and then assigning the available surgeons to the surgery. A simple heuristic is developed to produce an initial solution for the problem. Following from there, local search heuristic is applied to improve the solution, where the surgeries are scheduled based on the urgency value assigned to each patient. This ensures that high urgency patients are prioritized first to avoid any health complications or patients dissatisfaction. The results are compared between the exact method and the heuristics proposed in this study. The proposed heuristics shown a good performances based on the solution quality and the computational time. Since there is no historical data from the hospital, the surgery duration needs to be generates using the statistical distribution. The surgery duration is generated using two probability distributions based on the information from the previous researcher. The most common probability distribution used in generating the data is the uniform distribution and also the exponential distribution. These two distributions are used to generate the surgery durations tested with our heuristic to determine which distribution is better. The exponential distribution is used to generate the surgery duration since this distribution is better than the uniform distribution in maximizing the urgency value for scheduled surgeries. Not only that, the exponential distribution also managed to minimize the urgency value for the unscheduled surgeries. Based on the single-objective problem, the model is formulated into a bi-objective and the exponential distribution is used to generate the data for the surgery duration. The aim of this study is to maximize the total urgency value scheduled and the total number of time periods scheduled in the planning week. Since exact method is time consuming, a heuristic is proposed to solve the problem. A multi-objective local search heuristic is developed based on the previous local search heuristic to suit with the bi-objective problem. This multi-objective local search heuristic works by multiple checking the objectives in each of the iteration. The results show that the heuristic used is efficient as the average operating room productivity measures show good results.

Download File

[img] Text
FS 2021 43 IR.pdf

Download (838kB)

Additional Metadata

Item Type: Thesis (Masters)
Subject: Heuristic algorithms
Subject: Heuristic programming
Call Number: FS 2021 43
Chairman Supervisor: Nor Aliza Abd Rahmin, MPhil.
Divisions: Faculty of Science
Depositing User: Mas Norain Hashim
Date Deposited: 26 Apr 2022 01:49
Last Modified: 26 Apr 2022 01:49
URI: http://psasir.upm.edu.my/id/eprint/92760
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item