Constrained Optimization Usage - Creating Optimal Volunteer Schedule for Community Service Organization

Question

I'm a college student who volunteers as a program manager for a local community service organization. One big part of my job involves matching volunteer schedules (submitted to me via text and email) with tutee schedules (submitted by teachers via a google form). For the past two years, I've been matching the requested time slots with volunteer availabilities manually with excel sheets and color coding. This has been easy so far because I've received a relatively small number of tutor requests and volunteer sign ups.

Over the past two months, I've worked hard to grow the tutoring program at the school I manage. This semester, I received 18 request forms for over 25 students. Matching volunteer schedules manually for this many people will take hours, if not days, for me to complete. Given my work load, I figured there'd have to be a better way to approach this problem.

I am curious if any of you all with constrained programming experience could help me (1) solve my scheduling problem or (2) recommend software that can help. Below I will outline the scheduling process in more detail and list the constraints that must be taken into consideration when scheduling shifts.

THE SCHEDULING PROCESS

I ask my volunteers to send me their Monday - Thursday availability in a format like so:

M: 9:30 - 12:00 T: 2:00 - 4:30 W: 12:00 - 1:30 Th: 10:00 - 11:30

The school is a 15-20 minute drive away, so I rely on 'drivers' to carpool other volunteers to their 1-hour shift. If the volunteer has a car and is willing to carpool, then I try and match at least 2 other volunteers with the same availability with that driver (given that the car has enough room and a tutor has been requested by a teacher for that time slot).

I then pray that a teacher has requested a tutor for that carpool's time-slot. If not, then the carpool is no good and I have to manually come up with another solution.

THE CONSTRAINTS AND VARIABLES

Obviously, there are several constraints and variables that come into play when making the schedule. I will list as many as I can below:

• Is the tutor a 'driver'?
• If the tutor is a 'driver,' how many seats does he have?
• Does the driver's availability match up with any of the requested time slots?
• Are there other, non-driving tutors that have the same availability as the driver? (i.e. is there anyone that can carpool with the driver)
• Do all volunteers in the carpool have a student they could tutor?
• Did the teacher request individual or group tutoring (i.e. one or more tutor for one or multiple students)?
• If yes, how many tutors did the teacher request?
• REMEMBER, one volunteer can tutor more than one student

That is a small list of the constraints and variables I can come up with off the top of my head.

So can anyone offer a solution to this scheduling problem? Would someone who has no knowledge about constraint programming be able to use OptaPlanner to solve this problem?

Thank you for giving this a read and offering your advice.

Answer 1

You can use OptaPlanner for solving this problem, but it feels like Minizinc could be a better option. My point is that in case of Minizinc you describe required properties of a solution, instead of implementing workflows and algorithms to manage variables, constraints, parsers for input data etc, in case of OptaPlanner.

If one is not experienced with constraint satisfaction, it could be much simpler - just describe allowed/disallowed configurations in a text configuration file and run a solver. You can even provide a simple GUI for generating input data.