18.8.12

Robust scheduling

This has been puzzling me recently: When we are making schedules, for simplicity we mostly assume that there is no uncertainty involved. Now, I don't want to imply that no research has been done, the Pinedo's book contains several chapters;  but in real-world applications, everything seems to be deterministic.
Of course sometimes you don't mind - when scheduling school classes, you can be pretty sure that a good deterministic schedule will work fine. On the other hand, sometimes ignoring uncertainty is just impossible and this has been recognized - in airline operations for instance, disruptions occur all the time.

In manufacturing, the situation seems as bleak as in aviation industry, even though manifestations of uncertainty may be less spectacular and perhaps because of this, the uncertainty aspect is less stressed. In my current manufacturing OR adventure, I have encountered in principle two related views on uncertainty:
  1. Handling disruption is what manufacturing managers are for. Scheduling tools can help (among other things) to make sure that day-to-day planning and scheduling is done appropriately when nothing weird happens.
  2. The factory should have certain amount of well-managed buffers (e.g. overtime possibilities, surplus stocks) which can help them get back to normal when an unexpected event occurs.
 Now from a view of "advanced planning & scheduling champion", it is hard to passively accept such views. I want to plan in a way which at least implicitly reflects my recognition of uncertainty - this can mean making schedules insensitive to small changes ("robust scheduling"). Ideally one could, based on the past data, say which parts of the schedule touch volatile resources and hence need more insensitivity and which parts can be assumed rather stable.
As for the buffers, a question is how to put the phrase "well-managed" in more concrete terms. Given my amount of such and such uncertainty, what is my "optimal" amount of such and such buffers?

Now this is an area I want to learn about, so I can't flood you with a discussion of existing approaches... Still, I know there is this "robust scheduling" stuff. Incorporating uncertainty directly, e.g. by taking processing times to be random variables, seems just too complex to swallow, at least for systems with more than 2 machines...Still, under the label of Stochastic optimization one can find, among other approaches, simulation of possible scenarios - a schedule is made for each - and from these what-if schedules, a final schedule can be obtained by taking kind-of-expected-value. The idea of running a scheduling algorithm  for each scenario seems off-putting from the computer-time perspective; still, the concept seems attractive.
Well, enough said for today...

No comments: