Approach to Integrated Scheduling Problems Considering Optimal Number of Automated Guided Vehicles and Conflict-Free Routing in Flexible Manufacturing Systems

Abstract

Usually, machine and automated guided vehicle (AGV) scheduling are studied simultaneously. However, previous studies often used a fixed number of AGVs or did not consider routing problems and transportation time. This paper focuses on the machine and AGV scheduling problem in a flexible manufacturing system by simultaneously considering the optimal number of AGVs, the shortest transportation time, a path planning problem, and a conflict-free routing problem (CFRP). To study these problems simultaneously, we propose a genetic algorithm combined with the Dijkstra algorithm that is based on a time window. The tri-string chromosome coding method is designed to ensure that the solutions are feasible after the genetic operator has been applied. Global, local, and random searches are adopted in reasonable proportions to improve the quality and diversity of the initial population. The Dijkstra algorithm based on the time window is embedded into the genetic algorithm to search for the shortest route, detect collisions for multiple vehicles simultaneously, and finally, solve the shortest CFRP. The objective is to minimize the makespan while considering the influence of the number of AGVs. Increasing the number of AGVs has a significant impact on the makespan in the initial stage. However, the makespan tends to stabilize as the number of AGVs reaches some threshold. To balance the relationship between the minimum makespan and the optimal number of AGVs, we set the minimum decrease rate to 5% when determining the minimum makespan and confirming the corresponding number of AGVs to be the optimal value. In this paper, to verify the effectiveness of our approach, we propose two sets of computational experiments. The first set of results shows that the proposed algorithm is as efficient and effective at solving the scheduling problem as the benchmark approaches. The second set of computational experiments indicates that the proposed approach is applicable for solving integrated scheduling problems in flexible manufacturing systems.

Keywords

• Conflict-free routing problem
• genetic algorithm
• Dijkstra algorithm
• optimal number of AGVs
• time window