An Improved Saturation Degree-Based Constructive Heuristic for Master Surgery Scheduling Problem: Case Study
Open Access
- 25 March 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 12, 44748-44772
Abstract
The Master Surgery Scheduling Problem (MSSP) can be described as a timetabling problem involving assigning surgery groups to operating theatre (OT) time slots. Previous MSSP optimization models considered throughput, waiting measures, resource utilization, costs, and schedule assignment objectives, neglecting consecutive days assignment preferences and surgical equipment-sharing limitations. Furthermore, previous works utilize greedy constructive heuristics to produce solutions, which increases quality but decreases feasibility. Our prior study demonstrated that the saturation degree heuristic enhances feasibility by considering assignment difficulty during event selection. However, its impact on solution quality remained unexplored. Therefore, this study proposes an improved saturation degree-based constructive heuristic that integrates objective function value for event selection to increase both quality and feasibility. The algorithm sorts surgery groups based on unit scores , prioritizing lower assignment difficulty and higher objective value. The highest-scoring group is assigned to its feasible slot with the highest slot score , following similar goals. In case of no feasible slots, the repair mechanism vacates the highest swap score slot, assessing the impact on quality and feasibility. A new mathematical model is also formulated, incorporating novel objectives regarding consecutive days assignment preference and surgical equipment-sharing limitations. Validated using real-world data from Hospital Canselor Tuanku Muhriz, the proposed algorithm is evaluated considering repair mechanism usage for feasibility and objective function value for quality. The algorithm is benchmarked against greedy, random, regret-based, and saturation degree-based constructive heuristics. Our algorithm achieved a 14.63% improvement in feasibility compared to the original variant. Its objective function value is over two times better than the closest competitor and 2.6 times superior to the original variant. Comparison with the hospital’s actual plan demonstrates competitive objective function value and a more balanced waiting time distribution among surgical groups. Our study showcases that a saturation degree-based constructive heuristic considering objective function value has increased solution quality while maintaining feasibility.Keywords
Funding Information
- Ministry of Higher Education (MoHE) Malaysia, through the Transdisciplinary Research Grant Scheme (TRGS/1/2019/UKM/01/4/2)
This publication has 84 references indexed in Scilit:
- An Improvement in Master Surgical Scheduling Using Artificial Neural Network and Fuzzy Programming Approach2020
- Reallocating Operating Room Time: A Portuguese Case2020
- Stochastic Master Surgical Scheduling Under Ward Uncertainty2020
- Sequential Constructive Algorithm incorporate with Fuzzy Logic for Solving Real World Course Timetabling Problem2020
- A Two Level Hybrid Bees Algorithm for Operating Room Scheduling Problem2018
- Hyper-Heuristics: Theory and Applications2018
- Solving University Examination Timetabling Problem Using Intelligent Water Drops Algorithm2015
- Metaheuristics2009
- Exact, Heuristic and Meta-heuristic Algorithms for Solving Shop Scheduling Problems2008
- Approximating the Shapiro-Wilk W-test for non-normalityStatistics and Computing, 1992