Anticipation and flexibility in dynamic scheduling

Abstract

Many real-world optimization problems change over time and require frequent re-optimization. We suggest that in such environments, an optimization algorithm should reflect the problem's dynamics and explicitly take into account that changes to the current solution are to be expected. We claim that this can be achieved by having the optimization algorithm search for solutions that are not only good, but also flexible, i.e. easily adjustable if necessary in the case of problem changes. For the example of a job-shop with jobs arriving non-deterministically over time, we demonstrate that avoiding early idle times increases flexibility, and thus that the incorporation of an early idle time penalty as secondary objective into the scheduling algorithm can greatly enhance the overall system performance.

Keywords:

• Job-shop scheduling
• Rescheduling
• Manufacturing flexibility
• Evolutionary algorithm
• Dynamic environment
• Priority rules

Acknowledgements

We would like to thank the anonymous referees for their valuable suggestions and comments.

Notes

Unfortunately, there exist different terminologies to describe changing problems. While many would consider a problem changing over time as ‘dynamic’, in the scheduling community, such a problem is generally named ‘stochastic’ or ‘non-deterministic’. We use both terms in this paper, depending on the context.

Compare (α = 0.0, δ = 0.0) with (α = 0.25, δ = 0.0).

Compare (α = 0.0,δ = 0.0) with (α = 0.375, δ = 0.0).

Compare (α = 0.0,δ = 0.0) with (α = 0.5,δ = 0.0).

See U = 0.7,δ = 0.75, α = 1.0.

Furthermore, since the problem has to be solved on a rolling time horizon with jobs being revealed only over time, even solving each sub-problem to optimality would most likely not produce globally optimal results.