We tackle the operating room planning problem of the Plastic Surgery and Major Burns Specialty of the University Hospital “Virgen del Rocio” in Seville (Spain). The decision problem is to assign an intervention date and an operating room to a set of surgeries on the waiting list, minimizing access time for patients with diverse clinical priority values. This problem has been previously addressed in the literature considering different objective functions. The clinical priority depends on the surgery priority and the number of days spent on the waiting list. We propose a set of 83 heuristics (81 constructive heuristics, a composite heuristic, and a meta-heuristic) based on a new solution encoding, and we compare these methods against existing heuristics from the literature for solving operating room planning problems. The heuristics are adapted to the problem under consideration (i.e. considering all constraints and the new objective function), being re-implemented using the information provided by the authors. In total, after a calibration procedure, we compare 17 heuristics. The computational experiments show that our proposed meta-heuristic is the best for the problem under consideration. Finally, the proposed heuristics are tested using data from the Plastic Surgery and Major Burns Specialty. The results show significant improvements on several key performance indicators (number of scheduled surgeries, quality of surgical plan, resources utilization, etc.) when comparing with the actual results obtained by the specialty in the current practice. The aforementioned hospital is currently implementing the heuristic methods.