Job Shop Scheduling Using Genetic and Heuristic Exchange Algorithms for AGVs

Solving a job shop scheduling problem (JSSP) entails allocating entire jobs to machines to minimize the processing time. Generally, the transit time between machines is not considered in the conventional JSSP because it is shorter than the processing time. In a real production environment, however, the transit time of an autonomous ground vehicle (AGV) is long due to the need to solve random problems, such as finding an indirect route or avoiding collisions. Moreover, AGVs sometimes need to transport the job on directional roads with upstream and downstream constraints. Therefore, we present an AGV job scheduling algorithm considering the transit time. This study considers not only the transportation times of the jobs from one machine to another but also collisions on limited roads, similar to in a real environment. A near-optimal job sequence was obtained by combining the genetic algorithm (GA) with simulation and was comparing this with the traditional method. Additionally, this paper presents heuristics that deal with deadlocks in the process of combining JSSP and simulation. The combination of GA and heuristics was tested using various simulations. © ICROS 2022.