D-CIS Publication Database


Type of publication:Proceedings
Entered by:JdJ
TitleStraightforward heuristics vs. evolutionary algorithms in dynamic scheduling (abstract only)
Bibtex cite ID
Booktitle OR 2011 Zürich
Year published 2011
Keywords Dynamic Systems;Metaheuristics;Robust Optimization
In highly dynamic scheduling, change events occur long before the scheduling horizon is reached. The scheduler is driven by change. The complexity of these problems cannot be described in terms of NP-hardness, as no exact optimal solution exists for a dynamic problem. Nevertheless, search space explosions are common. In addition, search time is very limited, since the environment requires immediate solutions. Each problem solving approach will therefore employ heuristics in some sense. The heuristics may be in the algorithm (e.g., metaheuristics), in narrowing down the search space, or in enhancing the fitness functions (e.g., by preferring robust schedules). Evolutionary algorithms (EA) are often applied metaheuristics, both in static and dynamic environments. They have innate robust tendencies, being able to adapt to changing environments. However, we argue they are of limited use in highly dynamic problems. As revised schedules preferably stay close to the original, there is no need for broad sampled neighbourhoods such as provided by EAs. Furthermore, schedules in dynamic environments have a great internal coherence, which an EA is prone to break. Lastly, in such problems, the time to perform EA computations simply is not there. The optimisation approach needed in such environments often involves load balancing, which can be performed by exchanging tasks between machines or queues. Therefore, more straightforward element-swapping heuristics such as k-opt search, will prove more valuable. Elevator dispatching was used as a case study in this research. It is a typical example of a highly dynamic scheduling problem. Experiments using real world passenger data show that EAs are outperformed by k-opt search, even when search time was unlimited.
de Jong, Jeroen
Total mark: 5