Re: Assignmnet problem with rules

Rob Thorpe wrote:
Ayende Rahien wrote:

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.

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.

There are a lot of similar related problems in many fields. As
others have said, this problem is often studied in operational
research and AI. It also occurs in compilers.

There has been a lot written on it in those three areas, it's fairly
easy to find some of it by searching the web and reading books.

If it is a real scheduling problem involving real people, then its
likely that similar scenarios will come up many times. So it may be
useful to keep a cache of solutions to particular problems that the
program has encountered before.

One of the best books on the subject (at least the appropriate
chapter) is Wirths "Algorithms + Data Structures = Programs". All
you have to do is find it. Amazon or B and N might do in their
used book departments.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>


.

Relevant Pages

  • Re: Assignmnet problem with rules
    ... Assign an employee to a shift with rules. ... Assigning an employee to a ... Keep going until I run out of shifts, ... If solution not found, back one step, mark it as invalid, and keep ...
    (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)