Learning decomposition sequence heuristics for scheduling

Solving scheduling problems optimally is computationally intractable and thus has impelled the research of heuristic components that can solve these problems near-optimally in a reasonable amount of time. This research explores the use of machine learning and artificial intelligence learning within decomposition components when generating solutions to scheduling problems. The goal is to improve the time and solution quality of the shifting bottleneck algorithm. Here the shifting bottleneck's prioritization heuristic is replaced with a knowledge base. The focus is to minimize makespan as a result of workcenter based decompositions that translate to a sequence of machines that minimize the maximum completion time. From jobshop and flowshop specifications, different techniques generating control and decision attributes are used to induce rules that can decompose new scheduling problems into sequences of sub-problems. In learn mode, the framework updates the knowledge base with heuristic rules specifying criteria for the order of machine selections to generate a prioritization of bottleneck machines. In solution mode, components of the framework utilize the heuristic rules to order the bottleneck machines for schedule generation. Relevant surveys are provided and the framework described, including solution and time quality, as well as scalability of the investigated approaches. Finally, conclusions and future work discussed.