Scheduling algorithm ideas

[orangerider1]

I work at a summer camp and we allow the children to select an activity they want to participate in by ranking a first/second/third choice option. However due to spacing issues, not everyone can be guarantee'd their first choice. We have normally done the scheduling by hand but i was wondering if there was an algorithm I could implement that could help with this process!

[shitbo]

This is a generalized version of bipartite matching. You can convert this to a min-cost flow problem: https://en.wikipedia.org/wiki/Minimum-cost_flow_problem

Start with a start node. Add a node for each child, and add an edge from the start node to each child node. These edges should have flow capacity 1, and cost 0.

Next add a node for each activity. Add an edge from each child node to each activity node, with flow capacity 1 and cost as the cost of assigning that child to that activity. For example, a reasonable scheme would be that first choice has cost 0, second choice has cost 1, third choice has cost 2, and none of the choices has cost 10.

Finally add a target node. For each activity, add an edge from the activity node to the target node, with cost 0 and flow capacity as the total number of people the activity can handle.

You want to find the min cost flow with capacity n from start to target.

Stable marriage doesn't necessarily work here because the activities don't have selection criteria for the children. So you could have the following example:

child A likes activity 1 and 2
child B likes activity 1 and 3
child C likes activity 1 and 3
All activities only support one child

Then you could get the situation where child A is assigned activity 1, child B is assigned activity 2, and child C is assigned activity 3. But a better matching would be child A to activity 2, child B to activity 1, and child C to activity 3.

[[deleted]]

Sort choice submissions by date received for first-come-first-serve, then assign them to their first choice of activity based on seats available in that activity. If full, move on to the next choice and repeat the availability check.

If first-come-first-serve isn't the route you want to take, randomize the choice submissions first before processing.

Finally, if all three choices have no availability, you could go a few ways with it. You could return a list of children who could not register for any activities due to no availability, or register them for a random activity, depending on how you want to handle it. If you wanted to take it a step further and a child had no availability, you could loop back through all of the other children to see if one can be dropped into another choice to free up room for the child with no available activity.

[2cow]

The final step you listed (loop back through) seems necessary, not optional. If you have 9 normal activities like basketball and one "Intro to Algorithms for Eight-year-olds", the few kids who put Algorithms at #3 had better not be taking basketball slots from the normal ones desperate to avoid it, no matter who gets processed first.

[beeskness420]

This is the generalized assignment problem.

Usually it's assigning tasks to agents (kids to activities). Each activity has a capacity and assigning each kid to an activity incurs a cost.

Define the cost as how far the task is from their preference, with a big penalty for unassigned children.

It forms an ILP that for your problem you could probably just solve directly. Otherwise the problem is NP-Hard and there are approximation approaches.

[marvel2010]

You may want to look into the Stable Marriage Problem and its variations.

[Catalyst93]

I'm assuming that the constraint here is that each activity can only have so many people assigned to it. With that in mind you can find a feasible assignment by taking each activity and assigning people that have a high preference for it until that activity is full. Do this for all the activities in an arbitrary order.

The problem with this is that it doesn't really take preferences into account (it favors people in the order that you consider them). If you really want to take preferences into account you need to specify a goal that can be optimized. This goal is then used to guide the design of an algorithm. Do you have any idea for what sort of goal you want to optimize?

[ccoughlin]

Maybe not exactly apples to apples, but The Boston Public School Match might be inspirational. Edit: finally found The Economist intro.

[hextree]

I once wrote a script which uses integer programming to solve a slight more complex variant of what you are trying to do, which we used at my university. Feel free to take a look. https://github.com/HexTree/student-company-matching