Si usted tiene un conjunto de reservas y un número fijo de habitaciones, entonces la pregunta no es cómo maximizar la utilización sino para verificar si las reservas pueden ser efectivamente realizadas en absoluto o no. La utilización obviamente sigue siendo la misma si todas las reservas se realizan.
Otro posible caso de uso es que tiene un conjunto de reservas que usted sabe que se pueden realizar, y luego intenta insertar una nueva reserva, es decir, un nuevo cliente desea hacer una nueva reserva y desea verificar si es posible que reubique algunas de las reservas para crear espacio para la nueva.
En ambos casos, la pregunta real es cómo comprobar si se puede realizar un determinado conjunto de reservas.
Para las reservas inamovibles esto es trivial, por lo que asume que se pueden realizar y que desea comprobar si las reservas reubicables se pueden realizar también.
El primer control es calcular por cada noche el número de reservas por esa noche; si en alguna noche el número de reservas excede el número de habitaciones disponibles una vez que se tienen en cuenta las reservas fijas, no se pueden realizar las reservas mediante ningún truco; su hotel está sobrevendido para esa noche.
lo contrario se puede entonces utilizar un algoritmo voraz a intento una solución: proceso de las reservas en el orden de sus fechas de inicio y reservar cada reserva a una primera habitación (por ejemplo, con el fin sala numérica) que está disponible. Si esto le da una solución, entonces se ha dado cuenta de las reservas y listo.
Si eso no funciona, entonces puede usar GRAPH COLORING para resolver el problema, y esta es la solución universal. Construya un gráfico donde cada reserva es un nodo y dos nodos (reservas) están conectados solo si se solapan en el tiempo. Incluir las reservas fijas (no reubicables) en el gráfico. Luego, intente hacer una coloración completa del gráfico con N colores (N = número total de habitaciones en su hotel) una vez que haya precoloreado las reservas fijas con los números de las habitaciones a las que pertenecen.
Puede gestionar también reservas solo parcialmente flexibles de esta manera, agregando un enlace desde la reserva r a un nodo especial precoloreado para la sala n si y solo si la reserva NO se puede realizar en la sala n (p. Ej.)
Este mismo algoritmo de coloreo gráfico se usa con éxito, p. en compiladores para la asignación de registros.
Por supuesto, la pregunta es cómo implementar la coloración gráfica de manera eficiente; para eso hay implementaciones ya hechas.
¡Buena suerte!
¿Está bien poner varias reservas en una habitación para aumentar la utilización? –
@Anders, no lo creo :) – JohnIdol