Automated Guided Vehicle Scheduling Problem in Manufacturing Workshops: An Adaptive Parallel Evolutionary Algorithm

In the realm of scheduling problems, metaheuristics have been widely embraced as superior solutions, appreciated for their ability to generate resolutions for non-deterministic polynomial-time hard (NP-hard) problems swiftly. This paper presents a novel parallel evolutionary algorithm (PEA), which marries metaheuristics and parallel computing to amplify computer performance utilization. Four operators and a restart strategy are incorporated into the proposed PEA to bolster both its global and local search capabilities. An accelerated calculation method for two operators is proposed. The algorithm also features an adaptive method that generates sub-threads and parameters based on computer performance, along with rotation for evaluating solutions. A random search sub-thread is established to update the solution. The algorithm is tested on the workshop automated guided vehicle (AGV) scheduling problem and compared against other optimization algorithms to ascertain its efficacy. The test results overwhelmingly highlight the superior performance of the proposed algorithm.
Note to Practitioners
—The paper introduces a novel parallel evolutionary algorithm (PEA) for scheduling problems, which combines metaheuristics and parallel computing to enhance computer performance utilization. The algorithm incorporates four operators and a restart strategy, along with an accelerated calculation method for two operators. It also includes an adaptive method to generate sub-threads and parameters based on computer performance, as well as rotation for evaluating solutions. A random search sub-thread is established to update the solution. The proposed algorithm is tested on the workshop automated guided vehicle (AGV) scheduling problem, producing superior results compared to other optimization algorithms. Its ability to swiftly generate resolutions for NP-hard problems can greatly benefit industries that rely on efficient scheduling, such as logistics and manufacturing. However, it is important to note that the algorithm has some limitations. Further research is needed to explore its application in different domains and evaluate its performance in more complex scheduling scenarios. Additionally, the algorithm’s scalability and adaptability need to be thoroughly examined to ensure its practicality in real-world settings.