Combining single objective dispatching rules into multi-objective ensembles for the dynamic unrelated machines environment

Dispatching rules (DRs), which are simple constructive methods that incrementally build the schedule, represent the most popular method for solving dynamic scheduling problems. These DRs were usually designed for optimising a single criterion and work poorly when solving multi-objective (MO) problems. In recent years, we have seen an increase of research dealing with automated design of DRs using genetic programming (GP), which has enabled the application of several evolutionary MO optimisation methods to create DRs for MO problems. However, for each considered MO problem new DRs need to be evolved, which can be computationally expensive. Motivated by this, we propose a novel methodology to combine existing DRs evolved for optimising individual criteria into ensembles appropriate for optimising multiple criteria simultaneously. For this purpose, we adapt the existing simple ensemble construction (SEC) method to construct ensembles of DRs for optimising MO problems. The method is evaluated on several MO scheduling problems and compared with DRs evolved by NSGA-II and NSGA-III. The obtained results show that for most problems the proposed method constructed ensembles that significantly outperform DRs developed with standard MO algorithms. Furthermore, we propose the application of evolved MO rules and ensembles on problems with a smaller number of criteria and demonstrate that with such a strategy similar or better performance is achieved compared to evolving DRs for such problems directly, which demonstrates theif reusability and generalisation potential.

Automated summary

Dispatching rules (DRs) are popular methods for solving dynamic scheduling problems, but they perform poorly for multi-objective (MO) problems. Recent research has focused on using genetic programming (GP) to automatically design DRs for MO problems. However, evolving new DRs for each MO problem can be computationally expensive. To address this, we propose a methodology to combine existing DRs for optimizing individual criteria into ensembles suitable for optimizing multiple criteria simultaneously. The method outperforms standard MO algorithms in terms of performance and can be applied to problems with a smaller number of criteria.