An Ant Colony Optimization-Simulated Annealing Algorithm for Solving a Multiload AGVs Workshop Scheduling Problem with Limited Buffer Capacity
Zishi Wang, Yaohua Wu
Abstract
In this paper, we address a multiload AGVs workshop scheduling problem with limited buffer capacity. This has important theoretical research value and significance in the manufacturing field in considering the efficient multiload AGVs widely used today, and in the limited buffer area in production practice. To minimize the maximum completion time, an improved ant colony optimization-simulated annealing algorithm based on a multiattribute dispatching rule is proposed. First, we introduce a multiattribute dispatching rule, which combines two attributes, delivery completion time and input queue through dynamic weights that are determined by the information about the system, using the multiattribute dispatching rule to construct the initial solution. Then, with the ant colony optimization-simulated annealing algorithm as the basic framework, we propose a method for calculating transfer probability based on the multiattribute dispatching rule, which obtains heuristic information through the proposed rule. Further, we propose a path branch mechanism and dynamic equilibrium mechanism, aiming to efficiently construct the ant path and dynamically adjust ant path distribution. We propose a key job strategy and design a 2-opt neighborhood search method based on key jobs. Data experiments demonstrate the multiattribute dispatching rule is superior over other heuristic dispatching rules; the algorithm improvement strategies proposed are effective when used simultaneously or separately. Further, the proposed algorithm in this paper is superior over other heuristic algorithms and adapts to all kinds of instances.