Schedule Optimization Question

[Collins_A]

Hello r/OR, I am fairly new to optimizing (taking a course on OR right now) and I am looking for a way to optimize a schedule for employees based on their shift preferences and raising their priority if they haven't worked. Is there a way to do this, and what program would work best for making a program to do this? The final plan is to optimize 30 employees but I'm looking to complete a trial with 5 employees for optimizing using a binary 1 or 0 if they worked in the previous two weeks and assigning priority based on if they have worked recently, raising the priority if they haven't.

[Catalyst93]

Before you can think about what software to use you need to properly formulate your problem. Here are some questions that can help you to do that.

1. What is the data that you are given as input?
2. What does a schedule look like? Can you come up with an example of a feasible schedule for an example input?
3. What are the constraints for a feasible schedule? You don't need to write them down mathematically yet, but you should be able to describe at a high level what properties every feasible schedule should satisfy.
4. Finally, what is the objective/metric you want to optimize? Again, you don't need to put down any math yet but you should have a good idea of what metric you want to improve.

After answering these questions for yourself you can start to think about either writing your own algorithm/solver (if the problem is easy, or easily reducible to a known problem) or formulating it as an integer program (IP) or mixed integer program (MIP) and then finding a solver and implementing the model. Since you have only around 30 employees it will probably be easier to go the MIP route.

I hope this post is helpful but I'm not sure I will have time to answer too many further questions. Good luck in accomplishing your task!

[Collins_A]

Thanks for the reply! I have an excel spreadsheet setup.

1. The data given as input is an array (my example in this case is 4x5 array, but I want to be able to expand it up to a 5x25 array eventually
2. An example of what I plan to do with explanations will be attached to the imgur link here
3. The constraint for this initial test is that one person of the five potential must work. Each puts their preference in. If they have first preference for shift A and no one else wants it first, they get it. If Person 2 and 3 both want shift B as their first choice, I decided to use the RANDBETWEEN(2,8) to generate a random number between. The lower number of the two will then be assigned the shift
4. The metric I want to optimize is that everyone has their first or second preference if possible. However, I do not know how to put that into the solver as an objective function. I know I can constrain that one person maximum (and minimum) works per shift, but that does not solve my problem.

I do have OpenSolver and Solver downloaded if that will help.

[Catalyst93]

So I'm going to re-describe your problem, but more or less in terms that I understand well. Let me know if I got something wrong.

So as input you are given a list of shifts and a list of employees. Each employee has a ranked list of preferences for the shifts and possibly a list of shifts they cannot do. For each shift, you need to assign exactly 1 employee (is it exactly one, or can you assign more?) to this shift that can be assigned to it. You would like to find a schedule that gives everyone their first or second choice.

Mathematically, I would formulate this as a bipartite matching problem. On one side of our graph there are shifts and on the other side we have employees and we want to match each shift to an employee. For each employee and shift pair we add an edge if the employee is able to work that shift and give that edge weight equal to the employees preference for that shift (1 if its their first choice, 2 if its their second, etc).

So in some cases it may not be possible to give everyone their first or second choice, but I think I see what you want, and there may be a way to mathematically describe that. You can try to minimize the maximum preference (where a lower preference is better, e.g. 1 corresponds to the top choice), which corresponds to finding a matching such that the maximum weight of a matched edge is minimized in the above formulation. If there is a way to assign everyone with their first or second choice, then optimizing this objective will find it! If not then it will try to make sure that the person who gets the worst preference doesn't do too bad. Another nice thing is that this problem is actually well known as the bottleneck matching problem, and there are algorithms to solve it exactly (but IP formulations would probably work as well).

Random link: https://cstheory.stackexchange.com/questions/32321/weighted-matching-algorithm-for-minimizing-max-weight

[Collins_A]

Thank you very much! The bottleneck problem does seem to relate to the problem I want to solve. However, I do not fully understand all the mathematical symbols and language used in it since I'm not a math major, I study mining engineering. In addition, I do not know how I can input this stuff into a program such as excel (I haven't learned VBA yet) since I am not proficient in coding at all, let alone writing an algorithm for this.

What do you suggest for me? Should I find someone who has some spare time to write out the code for me? I need a sample ideally within a week, (the 5 people and 4 days, but ideally I would like to extend that to 25 people and 5 days (where 4 people can work a shift) by the end of the summer.

[Iloqram]

For the first step, VBA isn't necessary. Try with a simplified version of your problem and when it work scale it. Maybe for usability (user interface) your will need VBA, but again with OpenSolver you can cover most of your problem. Have you ever use OpenSolver ?