How would you linearize this scheduling problem? Or how would you solve this? It is variation of a set coverage problem for OpenSolver

Question

So, it's been about 15 years since I took my OR class in college. I'm not versed in any programming language besides a little bit of VBA.

A client of mine is looking to solve the following problem. I tried to model it in excel and use OpenSolver, but there must be something I'm missing in the configuration of the solver engine, or in the problem setup.

The idea is this: Yo have a workforce of 50 teachers, and you have 30 classrooms. For each classroom you have the demand (in number of teachers) that must be in that room by 15 minute timeslots. You have to minimize the cost of allocating teachers to rooms, while trying to respect the teachers restrictions (for example, if the teacher can't be in earlier than 8 am, or need to leave by 4 pm, or can't work more than 4 hours, or if they only want to be with the students in classrooms 1 or 2, etc.)

I tried formulating this problem as a set covering problem and tried to solve it with OpenSolver, but despite my best efforts to linearize or to reconfigure the problem, I'm kind of lost. I've uploaded a copy of my file to S3 https://examplesforsolver.s3.amazonaws.com/HowWouldYouLinearizeThis.xlsx

Also, I decided to make a quick proof of concept using excel's evolutionary solver and OpenSolver's Nomad engine, but still, didn't work. I've uploaded this file as well. https://examplesforsolver.s3.amazonaws.com/Very+Quick+Nomad+Test.xlsx

Please, take a look at the files. Any help will be greatly appreciated. But please bear in mind that neither myself or my client is versed in anything that is not excel, so coming up with a solution using Python, C++ or whatever else will not work.

Thanks a lot for your help.

Answer 1

In general, you could try defining the problem as a linear programming problem and then use the simplex algorithm or Gaussian elimination to find a solution or understand that there is no feasible solution.

In theory, you write it as a system of equations and solve for the solution vector.

Example:

We have a budget $b_{max}$ and the sum of costs should not exceed $b_{max}$ so that becomes a constraint of the model. $X_1+X_2+X_3+...+X_N < b_{max}$. You arrange all constraints to an equation system and solve it to get the solution vector. You can program it in Excel but it should be easier to invoke a stand-alone program if you are comfortable with a few rows of program for using the simplex algorithm or use the built-in Solver in Excel with the LP simplex algorithm.

If you want to try Python, there are instructions on how to solve linear programming with python at this link https://realpython.com/linear-programming-python/