A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services

• Parallel batch scheduling approach for hospital sterilization services.
• A branch and bound based heuristic method is developed.
• Our algorithm, BBHBBH, can solve real-world size instances with short computation time.
• BBHBBH outperforms the current state of the art solution methods for most of the problem instances.

In this paper, we address the problem of parallel batching of jobs on identical machines to minimize makespan. The problem is motivated from the washing step of hospital sterilization services where jobs have different sizes, different release dates and equal processing times. Machines can process more than one job at the same time as long as the total size of jobs in a batch does not exceed the machine capacity. We present a branch and bound based heuristic method and compare it to a linear model and two other heuristics from the literature. Computational experiments show that our method can find high quality solutions within short computation time.