A Hybrid Approach with BRKGA and Data Mining for the Early/Tardy Scheduling Problem

This paper introduces a novel hybrid genetic algorithm combined with data mining to solve a version of the early/tardy scheduling problem in which no unforced idle time may be inserted in a sequence. The chromosome representation of the problem is based on random keys and we use the Biased Random-Key Genetic Algorithm (BRKGA) to establish an order in which jobs are scheduled. A data mining component gathers data from the evolutionary steps of BRKGA and suggests chromosomes based on past observations. In this way, we address a key challenge in BRKGA - the exploration of solutions near an individual gene - by leveraging data-driven insights to refine and enhance the search space. Comparative analysis reveals that our hybrid algorithm significantly benefits from the pattern recognition capabilities of data mining, leading to improved scheduled efficiency. The results of a series of computational experiments underscore the potential of this hybrid approach that, although requiring slightly longer computational times, is better than the previous baseline BRKGA algorithm in terms of solution quality.