An Improved Saturation Degree-Based Constructive Heuristic for Master Surgery Scheduling Problem: Case Study

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, but have overlooked 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 by unit scores, prioritizing higher assignment difficulty and objective value. The highest-scoring group is assigned to its feasible slot with the highest slot score. If no feasible slots exist, the repair mechanism vacates the slot with the highest swap score, which prioritizes lower assignment difficulty and objective value. A new mathematical model is also formulated, incorporating novel objectives regarding consecutive days assignment preference and surgical equipment-sharing limitations. 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

• Constructive heuristic
• graph colouring heuristic
• healthcare management
• master surgery scheduling
• operating theatre planning
• solution feasibility