Suggest me an algorithm: optimize employee allocation (maybe Dynamic Programming?)

Hi all,

I´m looking for an optimization algorithm, perhaps it would be Dynamic Programming but I´m not sure. I ask you to be understanding because English is not my primary language plus I´m an amateur programmer :)

Basically, I need to optimize my teacher workforce, having as constraints the maximum weekly working hours for each teacher, and the amount of hours for each specific discipline (say, 60 hours for Mathematics).

First, let me explain about the school.

The school has the 3 working shifts: morning, afternoon and night. Each shift has its classroom amounts, say 4 classrooms at morning, 5 by afternoon and 2 classrooms by night.

We must provide teachers for each classroom, for specific disciplines. Say each classroom needs 30 hours of Math and 20 hours of Science. We have 2 classrooms at night so 30x2 = 60 Math hours and 20x2 = 40 Science hours at night.

Now let me explain about teachers.

Each teacher can work at most 30 weekly hours (or less, if all other classes already have a teacher). Each teacher has their own specific working shift constraints: some may work only at mornings, or morning and night, and every other possible combinations you can think of. Also, some teachers are allowed to work on several disciplines: some may teach, for instance, Math on morning shift and Science on afternoon shift. Others may teach only Math by night.

Finally, on to the problem…

Given the several classrooms and the available teachers (and their teaching permissions), how to optimally allocate them, in such a way that we provide teaching hours for every class and maximize the amount of hours every teacher work?

For Example: John Doe may teach Math and Science, only by morning and afternoon. He may work only for 30 hours a week. The school needs 30 Math hours and 30 Science hours. So, considering the other teachers, how to optimally allocate teacher John Doe so that he works the maximum possible amount of hours AND we make optimal use of working hours from other teachers?

I program on PERL language, and MS EXCEL VBA and MS ACCESS VBA, and have some knowledge on LINUX. But I´m open to other languages, if it is needed.

Any suggestions? I´m interested on anything, from freeware and open source to commercial packages.

I would greatly appreciate any help.

Re: Suggest me an algorithm: optimize employee allocation (maybe Dynamic Programming?

This is a constraint-satisfaction problem with optimization. Due to the nature of the problem most of the solutions you will probably generate will be approximately optimal (rather than absolutely optimal). Constraint-satisfaction problems can often be solved efficient by a min-conflicts procedure, which is a form of local beam search. Namely:

Code:

`(1) Generate a random population of teacher allocations (say 100 different random allocations)`

(2) Iterate until a member of the population satisfies all your constraints:

(2a) For each allocation, calculate which swap between any two teachers will minimize

conflicts with your constraints

(2b) Make the minimum conflicting swap

(2b) Continue iterating

(3) When exiting the loop, you'll have a solution that meets all your constraints. This is ONE

solution. Try running the program a few more times to generate a few more and then

choose the BEST solution found as the actual allocation.

I'm not sure if that will efficiently find solutions or not. It may depend on the complexity of your constraints. This guess is based on a solution to the Eight Queens Puzzle described in Russel & Norvig's Artificial Intelligence: A Modern Approach (2nd Ed), Chapter 5.

Hope that points you in the right direction! Good luck!

Re: Suggest me an algorithm: optimize employee allocation (maybe Dynamic Programming?

@BioPhysEngr: thanks for your reply!

I´m currently studying your pseudocode and looking for the book you mentioned. Don´t you have some implementation of the code so I could test it?

I do have one question about your solution: could I say this method is brute force, since I´ll be trying every possible combination of allocations?

Thanks again!

As a newbie on the topic, I thought there could be some benefit from using Dynamic Programming. From what I´ve read about DP, it would be enough to optimize each sub-problem, one by one. So, optimally allocating each teacher and "backtracking" it in the end, we get the optimal allocation for the school.

Does that make sense?

Re: Suggest me an algorithm: optimize employee allocation (maybe Dynamic Programming?

Actually, the (possible) solution I described *is* a form of dynamic programming and is *not* merely brute forcing the solution. At step (2a) only all pairwise swaps are being calculated. This will take on the order of n^2 calculations (actually it's the handshaking problem: it takes n(n-1)/2 comparisons) on each cycle through the loop. A brute force solution would simply consider *all possible assignments* and then choose the right one. A simple example:

If you had 3 workers - Alice (A), Bob (B), and Carl (C) - at needed to cover Monday, Tuesday and Wednesday with exactly one worker, the allocations for the three days could be (writing them as triples of letters saying the order they work in):

ABC, ACB, BAC, BCA, CAB, CBA

Which is n! ("n factorial") possible cases. A brute force algorithm would consider each and select the one which optimized some set of criteria. For small n, this is possible, but if you had 20 workers instead you'd have to consider 20! = 2,432,902,008,176,640,000 cases; you can't deal with that many cases even on a very fast computer. The solution I described would instead (random) start with one and then calculate all possible SWAPS and then choose the one that maximizes the quality of the solution... for example:

(0) Start with ABC as a candidate solution. Ask three questions:

(1) Is the current candidate solution an ACTUAL solution? Yes -> We're done! Report it.

(2) Which is better? Swapping the days "Alice and Bob work on", "Swapping the days Alice and Carl" work on or "Swapping the days Bob and Carl work on".

(3) Whichever is the best of those, pick it as the new 'starting' candidate solution and go back to (0).

It doesn't LOOK like we're doing a lot less work when we only have n=3, but if we had 20 teachers, we could only need to consider 20(20-1)/2 = 190 swaps at each iteration. It's a heuristic solution that helps home in on a good solution by checking a set of small changes we could make to some candidate solution we are currently looking at in order to move towards a solution. Does that make sense?

As an aside: Now that I think about this, I answered another question on dynamic programming and used an example of how to schedule people. The thread is: http://www.codeguru.com/forum/showthread.php?t=507276. I guess I must have been subconsciously thinking about your question. That is another general dynamic programming technique - called backtracking - used to solve these sorts of problems. If you happened to have access to Norvig's book (linked in my original post), he mentions 8-queens can be solved by backtracking too. Backtracking is kind of like brute forcing, but using some intelligence to abort thinking about certain solutions once it becomes clear that they can not succeed thereby speeding up calcualtion time enormously.

Re: Suggest me an algorithm: optimize employee allocation (maybe Dynamic Programming?

Hi all,

so, BioPhysEngr, I would like to thank your efforts once more.

As I´m an amateur programmer, I now understand how the algorithm you suggested works but it´ll take a lot of time for me to program it. Not to mention I´m a PERL programmer; and as we all know, PERL is not as fast as C/C++ is.

You algorithm did helped me to understand how to theoretically solve the problem, but the issue is I don´t have the skills and the time to solve this.

After some research on optimisation subject to constraint, as you suggested, I found a freeware that may suit my needs. If it does suit, it would really save development time.

It is called the CACP project, and can be found at http://csp.bracil.net/cacp/

Among others, it solves the 8 Queens puzzle and also the Car Sequencing puzzle, which I found very similar to my problem.

If you could, please take your time and check out the algorithms it uses. I´m not really sure it will help, but seems promising.

Re: Suggest me an algorithm: optimize employee allocation (maybe Dynamic Programming?

Oh, interesting. Apparently this is a named problem called the **Nurse Scheduling Problem**.

The software you linked to looks like it might be worth a go. My main concern is that you might have some difficulty translating your problem into the language that program will require (which is to say nothing bad about you; learning a new syntax can take time). It's free though (I think) so if you have some time to play with it, I'd go for it to see if it meets your needs.

If you wanted to go with something commercial you might think about: http://www.mimosasoftware.com/. It's a little expensive (500 Euro), but you said you might be open to commercial solutions. To be honest, if you have sufficient budget, I would go with a commercial solution like this. It will probably work well and - if it doesn't - you'll have someone to turn to for customer support. On some reflection, if I had been thinking with my *how can I help solve this person's problem* brain instead of my *oh yay, a dynamic programming problem to solve* brain, I would have suggested pre-built software right away. Always better to use already-built software than to write your own from the ground up.

Re: Suggest me an algorithm: optimize employee allocation (maybe Dynamic Programming?

@BioPhysEngr: Thanks, your help was invaluable!

I now am aware what I´m dealing with. I´ll probably stick with this freeware package at least for a while, until I learn the EaCL syntax, as you mentioned.

If I manage to write a functional code, I´ll publish it in this forum as a form to help people with a similar problem.

See y´all!