Evolutionary Computation for Dynamic Optimization Problems

Shengxiang Yang, Department of Information Systems and Computing, Brunel University, UK

Abstract:

Evolutionary computation encapsulates a class of stochastic optimisation algorithms, generally termed Evolutionary Algorithms (EAs)), which are inspired by principles from natural and biological evolution. EAs have been widely used for optimisation and search problems in many fields. Traditionally, EAs have been applied for static problems. However, many real world optimisation problems are dynamic optimisation problems (DOPs), which are subject to changes over time due to many factors. DOPs pose a serious challenge to traditional EAs since they can not adapt well to a changing environment once converged. DOPs have ttracted a growing interest from the evolutionary computation community in recent years due to the importance in the real-world applications of EAs. This talk will first briefly introduce the concept of DOPs and several benchmark problems for testing EAs, then review the main approaches developed into EAs for DOPs, and describe several detailed approaches developed for EAs for DOPs. After that, this talk will present some work on applying EAs for real-world DOPs and discuss some challenging issues on EAs for DOPs. Finally, some conclusions will be made based on the work presented and the future work on EAs for DOPs will be briefly discussed.

Scheduling Dynamic Job Shops – An Anticipative and a Self-Organization Approach

Juergen Branke, Warwick Business School, University of Warwick, UK

Abstract:

Most practical scheduling problems are dynamic and stochastic: New jobs arrive over time and need to be integrated into the schedule, machines break down, raw material is delivered late, etc. In this talk, we present two quite different approaches to tackle such dynamic scheduling problems. Both utilize evolutionary algorithms, but in very different ways. The first approach is to re-schedule whenever new information becomes available. As we show, it is then advantageous to search for solutions that are not only good with respect to the primary objective (e.g., minimising tardiness), but also flexible and easy to adapt when new information becomes available. Evolutionary algorithms can be modified easily to take this into account. The second approach renounces planning and uses self-organization principles in form of simple priority rules to decide, based on local information, which job should be processed on a machine when this machine becomes available. Such an approach is very popular in practice, but it is quite challenging to design effective priority rules for a particular shop. Here, we demonstrate how evolutionary algorithms can support the design of such priority rules as well as automate the design process.