Combining hyper-heuristics to evolve ensembles of priority rules for on-line scheduling

Combining metaheuristics is a common technique that may produce high quality solutions to complex problems. In this paper, we propose a combination of Genetic Programming (GP) and Genetic Algorithm (GA) to obtain ensembles of priority rules to solve a scheduling problem, denoted (1,Cap(t)parallel to Sigma T-i), on-line. In this problem, a set of jobs must be scheduled on a single machine whose capacity varies over time. The proposed approach interleaves GP and GA so that a GP is in charge of evolving single priority rules and a GA is executed after each iteration of the GP to evolve ensembles from the rules produced by the GP in this iteration, at the same time as the GP evolves the next generation of rules. Therefore, the ensembles are obtained in an anytime fashion. In the experimental study, we compare the proposed approach to a previous one in which the GP was firstly run to evolve a large pool of candidate priority rules, and then the GA was run to obtain ensembles from that pool of rules. The results of this study revealed that the ensembles produced by the interleaved combination of GP and GA are better than those obtained by the sequential combination of GP and GA. So, these results, together with the ensembles being available earlier, make this approach more appropriate to the on-line requirements of the scheduling problem.

Automated summary

This paper proposes a combination of Genetic Programming and Genetic Algorithm to solve an online scheduling problem. The experimental results show that this approach produces better ensembles compared to the previous one and is available earlier.