Scheduling Application

[IanWright]

I'm just wondering if anyone could give me any starters here....

I have a need to create a simple scheduling application, that will choose from a pool of avaliable people and assign them to a particular day of the month to carry out a certain task along with various assistants. Basically it's generating a rota for activities once a week which require a number of people (leaders and assistants).

There are also a few requirements, people don't have full avaliablity over that range, some people must work with other people, and some people should not be assigned at all on the same day (e.g. both sets of parents). Finally if at all possible, the relative disitribution should be fairly even, so no one is on much more than anyone else.

The program I need need only be very simple, but unfortunately I think the background problem isn't quite so simple and I'm not quite sure how to solve it. I have done some routing and scheduling before using Ant Colony Optimisation and think that that may work (though I don't fully understand the phermone updating process) however it may be a little overkill, so I'm just wondering if anyone can offer a slightly simpler starter/base algorithm suggestion that I can work from?

Thanks

Ian

[RedSon]

Here are some additional scheduling disciplines. Do any of these work for you?

http://en.wikipedia.org/wiki/Schedul...ng_disciplines

[IanWright]

Here are some additional scheduling disciplines. Do any of these work for you?

http://en.wikipedia.org/wiki/Schedul...ng_disciplines

RedSon, I don't believe any of them will as they all appear to be dealing with CPU allocation or network transmission and be heavily dependent on time between jobs and overall processing times...

I suppose rota generation may be a more suitable description, but I'm not entirely sure hence my original question.

[JosAH]

The program I need need only be very simple, but unfortunately I think the background problem isn't quite so simple and I'm not quite sure how to solve it.

You're right: rostering problems are the hardest NPC problems together with
a few other problems (e.g. capacitated vehicle routing problems). I personally
have never seen a robust heuristic that could solve a 'medium complicated'
rostering problem.

The feasible approaches are genetic algorithms or simulated annealing. The
latter approach is a bit simpler to implement: find a solution, any solution,
possiblty infeasible and assign a cost function to your solutions. Threat
infeasibilities as having a very high cost factor.

Given the current solution find another solution, possibly worse than the current
solution. Given the total cost of the current solution compute a 'chance' that
you will take an uphill step; if the step is a downhill step always take it. Google
for 'Boltzmann temperature' for details. Repeat this process until you're stuck. If the
last solution is acceptible in terms of the cost function stop, otherwise apply a
form of tabu search and start from that new solution again.

kind regards,

Jos

[IanWright]

You're right: rostering problems are the hardest NPC problems together with
a few other problems (e.g. capacitated vehicle routing problems). I personally
have never seen a robust heuristic that could solve a 'medium complicated'
rostering problem.

The feasible approaches are genetic algorithms or simulated annealing. The
latter approach is a bit simpler to implement: find a solution, any solution,
possiblty infeasible and assign a cost function to your solutions. Threat
infeasibilities as having a very high cost factor.

Given the current solution find another solution, possibly worse than the current
solution. Given the total cost of the current solution compute a 'chance' that
you will take an uphill step; if the step is a downhill step always take it. Google
for 'Boltzmann temperature' for details. Repeat this process until you're stuck. If the
last solution is acceptible in terms of the cost function stop, otherwise apply a
form of tabu search and start from that new solution again.

kind regards,

Jos

Thanks Jos,

I'll take a look into this and followup if I have any difficulties.

:)