Optimizing hospital sterilization operations: A column generation approach for parallel batch scheduling with job families

The Central Sterile Services Department (CSSD) plays a crucial role in hospital operations, ensuring that medical devices are sterilized and available for procedures. However, the CSSD's sterilization stage, where instruments are grouped into batches and processed in sterilizers, presents significant scheduling challenges due to high demand variability and stringent turnaround requirements. This paper addresses these challenges by formulating the sterilization process as a parallel batch scheduling problem with different job release dates, job sizes, and job families with family-dependent processing times. The objective is to minimize the total flow time of medical device processing. Given the problem's NP-hard nature, standard solvers do not find solutions for realistic instances within a reasonable runtime. To tackle this, we implement a novel column generation heuristic, decomposing the problem by job families and time slots to generate multiple subproblems, allowing for a fast convergence. In addition, we introduce a heuristic to solve the subproblem more efficiently and generate promising columns. The proposed methodology is validated on real-world CSSD data, solving instances with over 200 jobs in an average of 9 seconds while maintaining an LP-IP GAP below 1%, highlighting its potential to enhance scheduling efficiency, reduce total flow time by up to 70%, and improve hospital workflow continuity. This approach contributes to the field of operations research in healthcare by providing a scalable and practical solution for CSSD optimization.