Heuristic Ensemble Construction Methods of Automatically Designed Dispatching Rules for the Unrelated Machines Environment

Abstract

Dynamic scheduling represents an important class of combinatorial optimisation problems that are usually solved with simple heuristics, the so-called dispatching rules (DRs). Designing efficient DRs is a tedious task, which is why it has been automated through the application of genetic programming (GP). Various approaches have been used to improve the results of automatically generated DRs, with ensemble learning being one of the best-known. The goal of ensemble learning is to create sets of automatically designed DRs that perform better together. One of the main problems in ensemble learning is the selection of DRs to form the ensemble. To this end, various ensemble construction methods have been proposed over the years. However, these methods are quite computationally intensive and require a lot of computation time to obtain good ensembles. Therefore, in this study, we propose several simple heuristic ensemble construction methods that can be used to construct ensembles quite efficiently and without the need to evaluate their performance. The proposed methods construct the ensembles solely based on certain properties of the individual DRs used for their construction. The experimental study shows that some of the proposed heuristic construction methods perform better than more complex state-of-the-art approaches for constructing ensembles.

Keywords

• genetic programming
• scheduling
• unrelated machines environment
• ensemble learning
• dispatching rules