I have worked on some manufacturing planning and scheduling problems.
What I have found is:
1) Evolutionary algorithms work great for manufacturing *planning*
problems where the horizon and number of orders is huge. These are far,
far bigger and complex than *scheduling*. Deterministic search
algorithms will need huge amounts of memory and processing time for
planning problems, but EAs are more readily adaptable to implementation
limitations.
EAs also work wonderfully if you want to implement a solution relatively
quickly and develop it by iterative prototyping. The flexibility of
separating search from ranking the goodness of candidate solutions is
extremely powerful when developing industrial solutions. Often users
find out that what they thought were requirements really don't make
sense if they can separate themselves from all their historical
assumptions and their worries about how an algorithm performs search.
Being able to change the objective function quickly to try things out is
extremely valuable.
2) EAs won't produce the detailed quality of schedule that mixed integer
programming can provide, but they are much quicker to implement and far
more adaptable to ongoing release changes. I have worked on flow
problems where the scheduling constraints were so many and so extremely
interdependent on orders (even from a past schedules) that the best EA
solutions were still suboptimal (often that's why planning over the
larger time horizon is key, as well as scheduling). There were very few
soft constraints and very little tolerance for high WIP (work in
progress/process) - products would be useless or damaged if WIP measures
were too high, expensive equipment would run suboptimally, and so on.
You can fine-tune your EA so that it starts out searching globally and
narrows down focus to local search at the end (either by dynamically
changing modifiers and modifier weights and parameters; or buying runing
sequences or populations of different kinds of EAs to accomplish the
same thing). This can do amazingly well and then you can even run some
kind of repair algorithm after that. Still, my experience is that
someone who really knows how to do mixed-integer programming can beat
even a great EA hands down, but they need a system with a fast CPU and
Megs/Gigs of RAM. And the users have to be able to specify exactly what
they want and need *upfront*, before algorithm design begins.
One can produce an EA in a few weeks and be ready to start fine-tuning.
Experienced MIP programmers took months because they had to be able to
specify far more details on "how" to produce a good solution. They also
needed a long fine-tuning stage because they had huge performance and
memory problems and had to partition the problem (and redo lots of
programming and testing). For well-designed EA software, this is easily
managed by tweaking parameters.
In subsequent releases, there were features that could only be added to
the EA solution, often because of time to implement. Or because users
wanted to play around with multiple objectives or constraints that were
very difficult and/or time-consuming to add to the MIP approach. In that
case, users didn't care that EA results were not optimal -- getting
"good enough" results was just fine. I don't think this would apply to
your case however as there's less tolerance for violation of constraints.
3) To answer your question: in my opinion, the best solution is probably
to use both algorithms. Start out with an EA. Get something up and going
and see what kind of schedules are produced. Fine-tune EA algorithm
search performance while also refining user requirements and
expectations (always an evolving target...). Once you know exactly what
users really want, you can implement a MIP solution. In the meantime,
the EA is available.
In working on manufacturing problems, I was fortunate to be in an
environment where the synergy between the EA and MIP algorists was quite
remarkable. Each was able to improve one's own algorithm by observing
the other's approach. With some more time, I think we could have
implemented an awesome solution that combined both methods, but in the
timeframe we had, that wasn't possible.
We were able to determine where each algorithm had it's strengths and
weaknesses and the tradeoff pattern between algorithms. Our product
manager was really great on describing when each of the solutions
worked best so that users had a choice.
I don't know if it helps, but that's my two cents for the day!
Wendy
To be more precise, I would be interested in more details, such as
1) What is the time horizon (2 weeks, 1 month?)
2) How many orders on average per schedule? Are they distributed fairly
evenly over the schedule time horizon?
3) Has any planning already been done to produce the orders for the
schedule input? How much variation is acceptable from the plan? How much
variation from the previous schedule?
4) More details on resources (load restrictions, setup times,...),
number of shifts, and all the stuff needed to define objectives, hard
and soft constraints.
5) What kind of system, memory limits, and runtime limits?
--
Wendy Williams
wendy@magma.ca
David wrote:
>Hi guys,
>
>I am newbie to this mailing list and certainly in an urgent need for
>directions on particular scheduling problem...
>
>I am currently working on a job shop scheduling process for a parallel 2
>stage oven-furnace kind of material flow.
>
>I am undecided on what approach should I use to solve the problem. I am
>thinking of using either dynamic programming, integer programming or EA
>to solve. I wonder anyone here has previous experience on solving job
>shop scheduling problems before.
>
>
>I would appreciate all suggestions and comments
>Many thanks for your time and attention !!
>
>
>P/S: More details on the problem at hand can be forwarded on request.
>
>Regards
>David
>
>
>
>
>