Learning dispatching rules using random forest in flexible job shop scheduling problems

Abstract

In this paper, we address the flexible job-shop scheduling problem (FJSP) with release times for minimising the total weighted tardiness by learning dispatching rules from schedules. We propose a random-forest-based approach called Random Forest for Obtaining Rules for Scheduling (RANFORS) in order to extract dispatching rules from the best schedules. RANFORS consists of three phases: schedule generation, rule learning with data transformation, and rule improvement with discretisation. In the schedule generation phase, we present three solution approaches that are widely used to solve FJSPs. Based on the best schedules among them, the rule learning with data transformation phase converts them into training data with constructed attributes and generates a dispatching rule with inductive learning. Finally, the rule improvement with discretisation improves dispatching rules with a genetic algorithm by discretising continuous attributes and changing parameters for random forest with the aim of minimising the average total weighted tardiness. We conducted experiments to verify the performance of the proposed approach and the results showed that it outperforms the existing dispatching rules. Moreover, compared with the other decision-tree-based algorithms, the proposed algorithm is effective in terms of extracting scheduling insights from a set of rules.