Re: Scheduling problem
- From: tristram.scott@xxxxxxxxxxxx (Tristram Scott)
- Date: Mon, 23 Jan 2006 09:35:24 GMT
Paul Skoczylas <pauls@xxxxxxxxxxxxxxxxxxx> wrote:
> "Mike Daniels" <mikedaniels567@xxxxxxxxxxx> wrote in message
> news:5970470f298c7ed9cf1839210@xxxxxxxxxxxxxxxxxx
>> Hi Paul
>>
>> Nice little problem, your wife gave you!
>> I used ILOG\OPLStudio to solve it ... but first some hints about your
>> problem.
>> Monte Carlo (trial and error) does not work. Your solution-space is of
>> 6^40!!! - of course quickly reduced through the constraints.
>
> Yeah, I figured that out real quick! One computer running for about 18
> hours ran 435 million cases, and didn't find any valid cases--98.6% failed
> on the first rule tested (can't be in the same station twice in a day). The
> remainder all failed on the second rule tested (no two groups at the same
> station at the same time).
>
> So I wrote a slightly smarter case generator, which guarantees that four of
> the nine things I'm checking are passed. As many as 0.1% are making it all
> the way to the ninth test, but failing there. Oh well, I'm going to let it
> run overnight and see what happens.
>
> This gets into an area that I know nothing about--and I'm sure that Matlab
> isn't the best tool for it, but when your only tool is a hammer, everything
> looks like a nail! :-)
>
> Frustrating that I could spend half an hour to write a small Excel
> spreadsheet with some VBA code that allowed me to generate a valid case by
> hand in a few minutes, while my (admittedly very poor) program in Matlab
> spends the better part of a day and comes up with zilch.
>
> Thanks!
>
> -Paul
MATLAB is surely a better hammer than Excel, for everything except doing
the accounts. The fact that you managed to run 435 million cases in just
18 hours is surely strong evidence of this.
The problem as you describe it can be tackled by an integer programming
method, which I believe is what Mike has used. However, by hand you can
get a long way towards a solution by just working throygh a few of the
constraints sensibly, as you have found.
If you want to code this by hand (i.e. without an IP solver) then the
easiest method I can think of would be to use a branch and bound approach.
As Mike mentioned, vast areas of your search space can easily be ruled out.
Once you have violated one of the constraints there is no need to be
checking all of the other constraints, and there is no pint in trying all
those variations on the same theme which will also violate the same
constraint in the same way.
Branch and Bound is discussed in almost every Operations Research text.
--
Dr Tristram J. Scott
Energy Consultant
.
- References:
- Scheduling problem
- From: Paul Skoczylas
- Re: Scheduling problem
- From: Mike Daniels
- Re: Scheduling problem
- From: Paul Skoczylas
- Scheduling problem
- Prev by Date: ICA, LDA and Kernel Algo's matlab code for Face Recognition
- Next by Date: Re: Is pcoded file safe to distribute?
- Previous by thread: Re: Scheduling problem
- Next by thread: Re: Scheduling problem
- Index(es):
Relevant Pages
|
