Strategy for scheduling with preference constraints

[nomadreid]

TL;DR Summary

I am not a programmer, so I am not looking for coding, but rather a general strategy for instructions for a programmer to set up a scheduling program which will schedule, say, 11 teachers, with 12 different preference criteria (some binary, some multiple values), and some teachers having seniority over others. More details in main text.

A computer program that was supposed to handle this was bought and tried, and it made a mess of it, so the idea is that perhaps it would be easier to give a strategy to someone (computer savvy, but an amateur, not a professional ) to program (not requiring too much power of the computer on which it is run).

The ideas I have so far are unfortunately vague -- if I had a more concise idea, I would not be asking here.

Numbers 10, 12 are used as examples; the real values will be close to them.

A brute force scheduling would be to make a 11 by 12 table, with teachers 1 through 10 listed in order of seniority, and list the options/constraints (choice of class [whereby also if a teacher has taught a class before, this would give her a bump up in the seniority for getting her choice ] which campus (out of two), 4 days or 2 days a week, time of day, etc. , and then slosh through it by hand. But there lies madness. Somehow making up a tree based on seniority and option importance, or a bubble sorting, or something (matrices? No idea how that would work), would be a better idea. Or any other suggestion.

One could give an example (but not in code, please) with a toy situation, say three teachers and three options, or something to that effect. Any links to freely available sites with ideas or methods (not products) would also be appreciated.

If the question is too vague, or belongs in another rubric, then I will gratefully accept any action by a moderator. Thanks.

 

[Vanadium 50]

First, you've provided no evidence that a solution matching your constraints exists. If you have two math classes at the same time and only one math teacher, no amount of moving things around will help.

Second, you need to decide how to tell if one solution is better than another. If A gets her first choice in Option X, and B gets his first choice in Option Y, is that better or worse than the reverse? This is a completely separate issue than finding the optimal solution - if somone hands you two schedules, you need some way to say which is better. It doesn't sound like you have that.

Third, you need to decide if you need the absolutely optimal solution or just one that is close to it. The firtst is harder and more work. The second requires you to determine how close is close enough.

 

[nomadreid]

Thanks for these starting considerations, Vanadium 50. I will think about them and figure out some criteria for tie-breakers. I should have mentioned that an optimal solution is not necessary: some of the decisions can be done by hand.

So, supposing that there is some condition or mechanism that breaks any tie, how would I proceed from there?

 

[Vanadium 50]

I don't think your problem is a lack of tie breakers. It's a lack of an overall metric - how do you tell if Proposal X is better or worse than Proposal Y?

 

[nomadreid]

Hm, yes. I will have to consider that, and when I come up with a solution, I will post again. Thanks again for the guidance, Vanadium 50!

 

[Vanadium 50]

To give an example, suppose I could quantify "badness" somehow. If I had an option with five teachers with a badness of "2" is that better or worse than one with four with a badness of 1 and one with a badness of 6? Of 5? Of 7?

Ultimately, you will need to decide whether to trade a slightly bad option for someone with high priority for a very bad option for someone with low priority. You need to decide how to handle that. That's a "political" decision - the algorithm won't do it for you.

 

[nomadreid]

Good example. I will need to figure out how to reduce a 12-tuple to a single number. As you say, there is a certain amount of "executive decision" here before the program can be set up. As I am not the one with these executive powers, I will bring these points up with the ones that do. After I get their answer in a couple of days, I will be able to be more precise. Many thanks, you are a great help!

 

[nomadreid]

Ah, apologies for saying that I would post again in a couple of days, and then not doing it, but after I made those very good points raised by Vanadium50, and pointing out that every partial order on a set can be extended to a linear order on the same set, those with the executive powers decided apparently to go back to doing it by hand, essentially first reducing the variables by reducing the problem to the cases where there is a conflict, and then making subjective choices. Sigh.

 

[Vanadium 50]

Well, I can't say I am surprised. "Let the computer do it" only works if "it" is well defined.

A few comments: you have multiple stakeholders. One way to set up your scoring function is to give each stakeholder a number of "points" to deploy as he or she wishes - i.e. prefers to teach at Campus 1, prefers to teach Algebra, does not want an 8AM class etc. If you like, more seniority might mean more points. Mary might want to work at Campus 2 and not care about anything else, so that's where all her points go. Bob has a weak preference for Campus 1 so might only assign that a point or two.

Issues like "fairness" in Message #6 can be incorporated into the score - the standard deviation of "badness" across teachers could be incorporated into the global score.

This is not easy.

If you had that, you need to find the optimal solution. I am assuming that most of your universe of solutions are valid. That may not be true -a solution that has a teacher teaching hours 1, 3, 5 and 7 at one campus and 2, 4, 6 and 8 at the campus on the far end of town is logically possible but not a valid solution. I am assuming the problem is to find a close-to-optimal solution, not a valid one.

Here is what I would do. Start with a trial solution. Swap two elements at random. If the solution is better, keep it. If not, stick with the original. Now swap two more elements. Same thing - keep going until the solution stops improving or you think enough time has been spent. That's your answer.

To improve on that, you might want to try multiple starting points. One might be last years' schedule.

 

[nomadreid]

Thanks, Vanadium50. I have passed on your excellent comments to the decision-makers, and will follow it up with them as much as they will let me. By the way, if I am not mistaken, your suggestion sounds like Nash equilibrium.

 

[Vanadium 50]

I don't think it's a Nash equilibrium. I don't think it's even necessarily an equilibrium. It's an algorithm that tries to be "pretty good", "pretty fast" and "pretty simple", but not try and be optimal in any category. Implementing something like the simplex algorithm would likely give better solutions, at a cost in complexity. Running longer would give a better solution, at a cost in time, and so on.

It does share certain features with voting systems, which answer a very similar question:L "given the preferences of N individuals, what is the preference of the group as a whole?" And like voting systems, it shares some of their pathologies. For example, insincere voting. Sally has a strong preference for Campus 2, but everybody else has a strong preference for Campus 1. She has no incentive to use her points to get her preferred campus because other people are using their points to avoid it - she's better off using her points elsewhere. Similarly, Fred has a strong preference for Campus 1, but is so low on the totem pole that he knows if he throws all of his points there, he still will end up on Campus 2- so why use any of them?

But we're not looking at how to run a major world government. We're setting up a schedule for a dozen people for fifteen weeks. How much effort do we need tgo put in this?

Another way to look at it is is like this. The advantage of a computer is that it can score a trial solution very quickly. Probably of order a billion per hour. If I look at a billion solutions at random and pick the best one, I am probably pretty close to optimal. And the algorithm I described is better than random.

 

[nomadreid]

Thanks, Vanadium50. I forgot to say that your idea in the earlier post of assigning preference values to the different options sounded a bit like the system used for selection of the Secretary General of the United Nations. I think that is an excellent suggestion, and I hope that the powers-that-be understand the merit of the suggestion. Even a pencil-and-paper brute force method would benefit from preference values.

Insincere voting could theoretically be a factor, but it is doubtful that it would be significant in this case. Of course, one should never judge underestimate the scheming that might go on.

As you say, we are not trying to set up a world government, and unless there is a clear set of values and some way to choose between different solutions, then a computer program would be more trouble than it is worth. Therefore, although my original question centered on creating a program, the suggestions and analysis you have offered should be (if the persons involved listen) valuable despite the absence of a computer (except maybe to keep track of who-wants-what).