Parallel Multi-objective Job Shop Scheduling Using Genetic Programming

摘要

In recent years, multi-objective optimization for job shop scheduling has become an increasingly important research problem for a wide range of practical applications. Aimed at effectively addressing this problem, the usefulness of an evolutionary hyper-heuristic approach based on both genetic programming and island models will be thoroughly studied in this paper. We focus particularly on evolving energy-aware dispatching rules in the form of genetic programs that can schedule jobs for the purpose of minimizing total energy consumption, makespan and total tardiness in a job shop. To improve the opportunity of identifying desirable dispatching rules, we have also explored several alternative topologies of the island model. Our experimental results clearly showed that, with the help of the island models, our evolutionary algorithm could outperform some general-purpose multi-objective optimization methods, including NSGA-II and SPEA-2.