Re: Assignmnet problem with rules

In article <1140980468.953929.11130@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Ayende Rahien" <ayende@xxxxxxxxx> wrote:

Hi,
I know that you probably rehashed the subject many time here, but
googling doesn't give me any good info on the subject.
I need to find a good enough solution to the following problem:
Assign an employee to a shift with rules.

I've a set of employees and a set of shifts. Assigning an employee to a
shift change the results of rules for the whole system. So I can't just
use normal wieghts to find it.

That sounds like an "NP-Complete" problem. That will give you something
to look up.

I started out thinking about trying something like:
- Assign Employee to Shift
- Check system state
- If good, continue
- If bad, mark this combination as bad and move to next employee
- drop all bad states that were recorded before this step.
- Keep going until I run out of shifts, employees or valid states.
- If I found a solution (all shifts are assigned), finish
- If solution not found, back one step, mark it as invalid, and keep
trying.

The problem with this appraoch is that it would probably take too long.
(Normal workload would be about 100 - 300 employees with ~500 shifts
to assign.
I got some fixed assignments that helps me here, but I would appriciate
any pointers.

Can you compare two states and tell which is better than the other? If
so, then I would do something where employee's are seeded into shifts,
then start swapping employees and see if the solution is better or worse
(if worse, swap them back.) The longer the program runs, the better the
solution will probably be. This is a basic hill-climbing approach.


--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
.

Relevant Pages

  • Re: Assignmnet problem with rules
    ... Assign an employee to a shift with rules. ... Assigning an employee ... Keep going until I run out of shifts, ... easy to find some of it by searching the web and reading books. ...
    (comp.programming)
  • Re: Racial Profiling
    ... Peace favor your sword, ... once an Employee was off shift they were required to leave the premises. ... Well, one evening (I was working two 12 hour shifts at that site, from ...
    (rec.martial-arts)
  • Re: Assigmnet problem with rules
    ... The genome map is the 500 shifts. ... Each postion can take an index used to get an employee for a list. ... Assigning an employee to a ... If solution not found, back one step, mark it as invalid, and keep ...
    (comp.ai.genetic)
  • RE: Employee Schedule DB
    ... Each employee works a random 3 on two off schedule..an advanced programmer ... could probably write the expression to automate the random rotation, ... "Kate" wrote: ... > shifts, 7 days a week. ...
    (microsoft.public.access.tablesdbdesign)
  • RE: assigning all employee with first name start with D rev N docu
    ... then the employeewill tell the admins about it and the admins will ... pick the employee from a drop down ... I use the query below in the Update Training Records form to display the ... it seems like the program is automatically assigning every employee with ...
    (microsoft.public.access.formscoding)