Genetic algorithms for complex, real-time scheduling

Abstract

Real-time scheduling of large-scale problems in complex domains presents a number of difficulties for search and optimization techniques, including: large and complex search spaces; dynamically changing problems; and a variety of problem-dependent constraints and preferences. Genetic algorithms are well suited to such problems due to their adaptability and their effectiveness at searching large spaces. We have used genetic algorithms to solve real-world problems in areas such as field service scheduling, air crew scheduling and transportation scheduling. We discuss key aspects of our approach including: domain-specific chromosome representation and genetic operators; multi-objective evaluation function; heuristic initialization of the population; dynamic rescheduling; and cooperative interaction with human operators.