Scheduling problem
- From: "Paul Skoczylas" <pauls@xxxxxxxxxxxxxxxxxxx>
- Date: Sun, 22 Jan 2006 07:30:49 GMT
A real world problem my wife gave me.
There are four groups, R Y O G. Each is assigned to one of six workstations
(1-6) in each of two time slots per day. A one week schedule is needed,
where there are five days in a week. Therefore, each group has 10 slots to
fill in the schedule.
The conditions are as follows:
1. No two groups can be at the same workstation at the same time.
2. No group can be at the same workstation in both slots in the same day.
3. No group can be at workstations 1 and 3 in the same day.
4. Each group must have at least two slots per week at station 2.
5. Each group must have at least two slots per week at station 5.
6. Each group must have exactly one slot per week at station 4.
7. Group R must have at least one slot per day at either station 1 or
station 3.
8. Groups Y O G must have at least two slots per week at station 1 or
station 3.
9. Station 3 must be occupied for exactly 3 slots per week.
10. No group can be at Station 6 more than once in a week.
There will therefore be 10 slots used by stations 1,2,5, three slots used by
stations 3,6, and four slots used by station 4. What I've done is use
randperm and reshape to generate a 10x4 matrix containing exactly those
numbers of 1,2,3,4,5,6 (one row for each of the 10 time slots, and one
column for each group). I then feed that into a function which checks it
against each of the rules above and signals if it is valid or not. Valid
schedules are written to a file.
My problem is that I've run millions of cases, and yet to find one that
works this way. Is the probability of a successful case when constructed
like this really that small? If so, can someone suggest a better way?
BTW, I can prove that there are a number of cases which will actually work:
R=[1 2 1 5 1 5 1 2 1 4];
G=[2 1 3 4 5 2 6 1 5 1];
Y=[4 5 2 1 2 6 2 5 3 2];
O=[5 4 5 2 6 1 5 3 2 5];
This is one valid case, I think. I can make a lot more valid cases by
switching the GYO vectors (R is different, since it needs more 1s [or 3s but
I used 1s]), or by switching the entries for any two days for all groups
(e.g. columns 1&2, with columns 3&4), or by inverting the columns for any
given day, for all groups (e.g., switch columns 1 with 2). I found this one
case by playing around by hand.
I know this test cases passes my check function, so I think that function is
working properly. But the random approach has not yet found any successful
cases.
Any ideas?
Thanks,
-Paul
.
- Follow-Ups:
- Re: Scheduling problem
- From: Mike Daniels
- Re: Scheduling problem
- Prev by Date: Problem in using SOLVE function
- Next by Date: specific contour lines
- Previous by thread: Problem in using SOLVE function
- Next by thread: Re: Scheduling problem
- Index(es):
Relevant Pages
|
