Feature transformations for improving the performance of selection hyper-heuristics on job shop scheduling problems

Abstract

Solving Job Shop (JS) scheduling problems is a hard combinatorial optimization problem. Nevertheless, it is one of the most present problems in real-world scheduling environments. Throughout the recent computer science history, a plethora of methods to solve this problem have been proposed. Despite this fact, the JS problem remains a challenge. The domain it- self is of interest for the industry and also many operations research problems are based on this problem. The solution to JS problems is overall beneficial to the industry by generating more efficient processes. Authors have proposed solutions to this problem using dispatch- ing rules, direct mathematical methods, meta-heuristics, among others. In this research, the application of feature transformations for the generation of improved selection constructive hyper-heuristics (HHs) is shown. There is evidence that applying feature transformations on other domains has produced promising results; Also, no previous work was found where this approach has been used for the JS domain. This thesis is presented to earn the Master’s degree in Computer Science of Tecnolo ́gico de Monterrey. The research’s main goals are: (1) the assessment of the extent to which HHs can perform better on JS problems than single heuristics, and that they are not specific to the instances used to train them; and (2), the degree to which HHs generated with feature transformations are revamped. Experiments were carried out using instances of various sizes published in the literature. The research involved profiling the set of heuristics chosen, ana- lyzing the interactions between the heuristics and feature values throughout the construction of a solution, and studying the performance of HHs without transformations and by using two transformations found in the literature. Results indicate that for the instances used, HHs were able to outperform the results achieved by single heuristics. Regarding feature transforma- tions, it was found that they induce a scaling effect to feature values throughout the solution process, which produces more stable HHs, with a median performance comparable to HHs without feature transformations, but not necessarily better. Results are conclusive in terms of the objectives of this research. Nevertheless, there are several ideas that could be explored to improve the HHs, which are outlined and discussed in the final Chapter of the thesis. The following major contributions are derived from this research: (1) applying a se- lection constructive HH approach, with feature transformations, to the JS domain; (2) the rationale behind the JS subproblem dependance in terms of the solution paths followed by the heuristics, which has a great impact in the training process of the HHs; (3) a method to deter- mine the most suitable parameters to apply feature transformations, which could be extended for other domains of combinatorial optimization problems; and (4) a framework for studying HHs in the Job Shop domain.