Evolutionary algorithms for optimal scheduling problem in manufacturing

Abstract

This dissertation presents a solution to the integrated job scheduling, AGV dispatching, and conflict-free vehicle routing (CVR) problem in manufacturing environments. The problem is formulated as a flexible job-shop scheduling problem with material handling and conflict-free vehicle routing problem (FJSPMH-CVR), which includes CVR to increase the realism of the problem. The proposed dynamic A* algorithm based on the time window approach can prevent collisions while balancing load between different edges and waypoints. To address the limitations of existing algorithms in providing temporal information about the current status of the constructing solution, a novel decoding method is proposed. This method provides more insightful information that can be used to design an effective CHA algorithm called least AGV waiting time (LAWT), capable of truncating AGV idling time by 33.57%.

Moreover, a dual-layer metaheuristic algorithm called dual-layer hybrid genetic algorithm and particle swarm optimization (DL-HGAPSO) and its single-layer version, SL-HGAPSO, are introduced to address the job scheduling and AGV dispatching problem. The DL-HGAPSO algorithm can explore more parallel AGV dispatching solution spaces corresponding to a single job scheduling result. However, the dual-layer structure of the algorithm leads to a relatively lengthy computational time. In contrast, the SL-HGAPSO algorithm is significantly faster, being 168 times faster than the DL-HGAPSO, but with a slight trade-off in optimality. The proposed methods provide a comprehensive and effective way to address the FJSPMH-CVR problem. The hybridization of the genetic algorithm (GA) and the particle swarm optimization (PSO) techniques used in the DL-HGAPSO and SL-HGAPSO algorithms compensates for each other's weaknesses and leverages their complementary strengths, making them useful in engineering applications.