Extraction of dispatching rules for single machine total weighted tardiness using a modified genetic algorithm and data mining

摘要

This paper introduces novel heuristics for the resolution of the single machine problem with total weighted tardiness by combining data mining and genetic algorithms. The aim of this approach is to use data mining techniques in order to explore, analyse, and extract knowledge from solutions for single machine scheduling problems. A hybrid genetic algorithm coupled with dispatching rules from literature is proposed to find near-optimal solutions for the single machine problem with total weighted tardiness. Using these solutions, data mining extracts knowledge which is then employed along with three proposed heuristics to solve unprecedented problems. The experiments show the superiority of the proposed approach over other well-known dispatching rules, mimicking the genetic algorithm behaviour while retaining heuristics' advantages, i.e., reduced required processing time, reactivity in dynamic scheduling, and real-time scheduling.