Optimize reservation system algorithm

Question

Im am developing a logistics application and at the moment, I try to solve the following problem:

1. In the system, there are multiple machines.
2. Each machine has one or more skills. For example, machine 1 can have skill A and B and machine 2 can have skill B and C.
3. Users can make reservations like: At some unknown time in the future, I need to use a machine with skill A. The application may accept or reject this reservation request.
4. Later, users can redeem their reservation: I have reserved a machine with skill A, please make it available to me now.
5. When a user is finished using a machine, they release the machine and return it to the system, so that the machine becomes available again.

Context: A "user" is a worker in a factory that needs to use a machine "soon", for example, in 5 minutes, or in 30 minutes, or in 2 hours. I guess we can assume that it is on the same work day. The worker does not know beforehand for how long they need to use the machine. It may be only for 5 minutes, but usually it is for about 30 minutes up to a few hours. In the past, workers were able to reserve concrete machines. However, they would always reserve those machines with most skills and block those for other workers. If they would have chosen a machine with a smaller subset of skills, specific for their problem, more workers would be able to work on the machines at once.

I thought about using some kind of ticket system: When the user makes a reservation and the application knows the it can be fulfilled, the app returns a reservation token, for example, a guid. When redeeming the reservation, the user sends the reservation token to the app.

I am now struggling with step 3. If the user made a reservation in step 3, then redeeming the reservation in step 4 must always succeed. (That's kind of the point of making a reservation.) This means that in step 3, the application needs to check that there are always enough machines available to fulfill all granted reservations. How can I do this in an optimal way? The application should be able to accept as many reservations as possible.

For me, the fact that each machine can have multiple skills makes it hard to solve the problem.

Example:

Say there are three machines:

• Machine 1: Skill A and B.
• Machine 2: Skill B and C.
• Machine 3: Skill C and D.

Say there are currently two active reservations, one for skill B and one for skill C. If another user now wants to make a reservation for skill A, this is okay, because all three reservations can be mapped to the machines simultaneously.

However, if there are currently three active reservations, one for skill B, one for skill C, and one for skill D, then an incoming reservation for skill A must be rejected.

What I tried:

I know that I can use a greedy algorithm that ensures that all granted reservations can be fulfilled: In step 3, the application looks for a machine that is not reserved and not in use and then reserves it. For example, in above setting, if a user reserves a machine with skill B, the application internally marks machine 1 as reserved and blocks it until the reservation is redeemed and the user releases the machine.

However, this algorithm is not optimal. Take above example. If the first user reserves a machine with skill B, the application may choose machine 1. If then another user tries to make a reservation for skill A, the application must reject the request, because the only machine with skill A is already reserved. If however the application had chosen to use machine 2 for skill B, it would be able to accept the reservation for skill A.

Is there some optimal algorithm that maximizes the number of accepted reservations?

Answer 1

If your reservation isn't specific regarding the time slot, it's not actionable. Such reservations are useless.

The only bit of information that you have is "user X wants to use one of the machines A or B at an unknown time for an unknown duration". This can not be used for scheduling, and if you block other users from using the machines while there exist reservations you may starve them, which is not productive. You may as well just let users use machines when they need them, and let them wait if currently no matching machine is free. No reservations involved at all.

I you want to use reservations productively (scheduling) you need to have a reasonable estimate of the duration a machine is going to be used for a task (so you can forecast the utilization and know when the machine is going to be available) and the approximate time when it is going to be needed. Other factors which often play a role in scheduling is the allowable delay (for example, if the product is due on April 1st, you may defer the step to prioritize something that is due tomorrow).

There is a wealth of research in the operations research domain regarding scheduling and different optimization strategies, but I'd assume that most concrete algorithms depend on at least some information about the tasks to be scheduled.

Answer 2

First, I would strongly encourage you to impose some limits on reservations and time in use, otherwise the system seems like a worse version of "first come, first serve". But you and your stakeholders are in the best place to understand the requirements, so below I will assume that reservations are "forever", and that the problem lies only in selecting the machines, not trying to schedule them.

Instead of "permanently" (until redemption) assigning a machine for each reservation, try to calculate a new reservation scheme each time a reservation is made. If the first attempt fails, backtrack or try again in a different order. How long you spend trying depends on how your computing/memory capacity and how long users can wait before they get a confirmed / rejected result.

As for the algorithm itself, there might be some nuggets in graph theory - matching algorithms, probably. But just for fun, I took a stab at something with a basic heuristic. It is hand-wavy and not proven correct, but may work as inspiration:

When a reservation is attempted:

1. Calculate the number of requests and the number of (not-in-active-use) machines for each skill, and the ratio between them
2. If any ratio is > 1 (more requests than machines), the new reservation must be rejected
3. Until all requests are satisfied:
   1. Select the skill Sn with the highest ratio of requests / machines
   2. Give all machines able to handle Sn a "weight" according to the sum of the ratios for the skills it has
   3. Select the lowest-weighted machine Mn able to serve Sn
   4. Tentatively reserve Mn to serve a request for Sn: Reduce the number of requests for Sn, and the number of machines able to serve each skill Mn has, by 1.
   5. Recalculate ratios based on the new counts
   6. If any ratio is > 1, remove the tentative reservation, block Mn and all identical machines (unassigned with same skill-set) from serving Sn, recalculate counts and ratios and try again from 3.2.
   7. If there are no remaining machines (they have all been discarded), backtrack by resetting the "blocks" applied for Sn, reverting the previous tentative reservation, and instead apply a block for "Sn-1" to all machines like "Mn-1"
   8. Once you have backtracked for long enough (in real time, memory use, or until exhaustive search), reject the new reservation and keep whatever assignments were calculated before.

When a reservation is redeemed:

1. Calculate the weights among all available machines (either reserved for that skill, or not reserved at all)
2. Assign the lowest-weight machine to fulfill the reservation
3. Free up the highest-weight machine among those reserved for the skill

Answer 3

incentives

I try to solve the following [reservation] problem

It is true that reservations could address this observed business issue:

they would always reserve those machines with most skills and block those for other workers.

But this really sounds like scarce resources are being allocated with inappropriate incentives. Traditionally the field of economics has had the most to say on this topic.

Let each worker start out the day with a fixed number of credits, and/or award credit upon completing a task that adds business value. Machines have hourly rental rates, which cost more credits for machines that are more capable. Bill each worker for time spent using the machine, and power it off if their credits drop to zero.

This lets workers assess whether a machine is a sensible match for the task.

Almost the same thing: gamify and publish a leader board showing who made poor use or good use of equipment.

central planning

Workers submit dependency DAGs for their sub-projects, and the system synthesizes these into an evolving global Gannt chart. Perhaps it only looks a few hours into the future.

Identify the critical path and manage bottleneck skills / machines.

Reducing each worker's decision making autonomy may pose retention and recruiting issues, even after you've introduced a LunchBreak "skill". Treating workers as machines doesn't always work.

capital expenditure

It sounds like you sometimes suffer lost worker productivity due to critical / bottleneck machines being busy. It's unclear whether costs are dominated by CapEx, by equipment maintenance, or by wages.

Add a fixed number of dollars to an equipment fund each month. In light of recent factory performance, make a {buy, no-buy} decision. So we either let it ride, having a bigger fund next month, or we purchase machine N which has bottleneck skills {X, Y, Z}.

This is an "outer loop" wrapped around your daily scheduling. Your system should be able to support such monthly decisions.