SOLVING LARGE JOB SHOP SCHEDULING PROBLEMS: USING GRAPH CLASSIFICATION VIA GRAPH NEURAL NETWORKS TO PRE-SEED A GENETIC ALGORITHM FOR MACHINE DISPATCHING RULE OPTIMIZATION

Abstract

The job shop scheduling problem is a difficult problem to solve, and it is also difficult to implement solutions found in research into real shops. In this research, a methodology is proposed to develop schedules for real shops. The methodology utilizes a genetic algorithm to select dispatching rules for each machine cell and accesses these schedules through a simulation optimization framework. The simulation framework allows for the study of random elements including variable job processing times and random machine breakdowns. This creates a robust schedule that is easy to understand, and therefore implement, while scaling to large, real-world job shops. To gain additional efficiencies, a novel methodology is proposed to classify the graphs which represent different types of shop environments, with a graph neural network, to pre-seed the initial population of the genetic algorithm. This process allows the system to leverage pre-existing knowledge of similar shops to reduce the number of generations required to reach a reasonable solution.