Algorithm to determine optimal availability for scheduling appointments with several resources

Question

I’m working on a system where several resources are scheduled (users, rooms, and equipment). Each appointment is scheduled for a user, and may also take a room and/or equipment. Appointments are scheduled over time, slowly filling up the calendar. It’s thus not a classic scheduling problem where everything can be scheduled at once.

My problem is determining ‘optimal’ availability slots that clients may choose from when booking an appointment.

It’s easy to determine all availability slots: it’s the overlap of the availability for the requested user(s)/room(s)/equipment(s). However, I want to prevent introducing 5/10 minute gaps in the schedule that cannot be filled later.

Relevant properties of the system are:

• A 5-minute interval is used
• Different appointment types have different (predefined) lengths (multiples of 5 minutes)
• Users/rooms/equipments can perform/have several appointments types with different lengths

The system should take this into account when determining availability slots that are offered for appointment bookings.

I think there is no ‘real’ optimal solution for this, since there are many factors and it’s not known in advance which appointments types will be scheduled later on. However, I want to prevent offering availability slots that introduce useless gaps (or other suboptimal situations) in the schedule.

I created a solution that only takes the availability of one resource (users) into account. It first determines the least common multiple (LCM) of the appointments durations the user can perform. It then generates availability slots in the total available time of that user, using the LCM as step size. This seems better than just offering all availability options at each 5-minute step, though it isn’t ideal. (E.g., if the LCM is high, few options will be offered.) Additionally, it doesn’t take the other resources (rooms/equipment) into account.

Are there any known algorithms/methods/best-practices for determining availability slots in such a situation?

• Neil: It seems to me like you're dealing with the Change-making problem except rather than dealing with coin values, you're dealing with time intervals. Ideally you'd want a schedule to be full, but the greedy approach may end up leaving you with large holes in the schedule, am I right?
• user1118321: You say, " I want to prevent introducing 5/10 minute gaps in the schedule that cannot be filled later." Is that what your users want? Meetings always go over, and there's context switching when entering/leaving a room. Since there's equipment involved, is there any extra time needed to setup/tear down the equipment?
• Jonathan: @Neil Yes, that sounds correct! However, clients should still be able to choose from a number of availability slots, rather than offering just one option which may be optimal to us.
• Jonathan: @user1118321 Everything that needs be done is included in the appointment duration, so there’s no extra time required between appointments.
• ferit: Searching for 1/Rj/Lmax scheduling problems might give you an idea.

Answer 1

Because you are dealing with uncertainty, you will have to resort to forecasting

You are selling something so the key is to reduce the combination of rooms and equipment to profitability

Here is a simple example

1. Alex wants to book a certain room for 2 hours as soon as possible
2. Beatrice usually books the same room in the next hour, for 3 hours

Our usual rate is 15ドル per hour

Analyzing the booking history, we realize that

• Alex never booked anything
• There's an 80% chance that Beatrice will book that room

Math is simple,

• Alex will bring us 1 x 15ドル x 2h = 30ドル
• Beatrice 0.8 x 15ドル x 3h = 36ドル

Not obvious but will work for us in the long term. So here are our options

1. We can up the price for Alex
2. We can impose a minimum of 2 hours and 30 minutes to Alex so that he exceeds Beatrice
3. We can offer a different room, and make this one seem unavailable

I hope this helps

• Jonathan: Thanks! Forecasting makes sense. In our situation, I could find how common different appointment durations are using historical data, and use this to smartly create availability slots.

Answer 2

This reminds me of a hotel reservation system we developed for a destination resort using AI in the 1980s. In this system, we outright refused to take any reservation that left a gap smaller than two nights. Doing this increased their peak season occupancy rate from 93% to over 100% (they put rollaway beds in rooms to get over 100%). This strategy worked because we knew the hotel was in high demand during peak season.

Another approach that can work well for incremental scheduling is to implement a pricing strategy, a kind of yield management. If a client takes a resource that leaves a gap, and that gap may be left unsold as a result, add a portion of the price of the gap to the resource cost. In the limit, at 100% of the gap cost, you will not have any loss as a result of any schedule. The math for this is akin to the use of an objective function in an optimization problem.