A bi-level math-heuristic algorithm for integrated optimization of task scheduling and storage location assignment in automated storage and retrieval systems

Abstract

The operation of high-bay warehouses for semi-finished cut tobacco is crucial in cigarette manufacturing and is primarily responsible for receiving inbound shipments, aging storage, and on-demand outbound delivery. Many local cigarette manufacturers have implemented automated storage and retrieval systems (AS/RSs) to enhance manufacturing efficiency. Nevertheless, the AS/RS systems encounter task scheduling and storage allocation issues. These challenges include the inability to dynamically adjust slotting promptly in response to real-time inventory status and ineffective task scheduling when meeting order deadlines, which limits the operational efficiency and responsiveness of the system. To address these limitations, this study designs a classification-based storage strategy and constructs a mathematical model that combines dynamic programming with integer linear programming to minimize task completion time and latency. A two-layer mathematical programming heuristic algorithm based on an improved dung beetle optimization (IDBO) algorithm and an assignment model is introduced. In the outer layer of this model, inbound tasks strictly follow the first-come, first-served principle. In addition, the IDBO algorithm is employed to optimize the execution sequence of outbound tasks. Moreover, to enhance solution quality, this study combines an improved circle chaotic map, an adaptive t-distribution perturbation strategy, and a competition mechanism. In the inner layer of the proposed model, the movement cost of a stacker crane is modeled as edge weights in a bipartite graph between the tasks and storage locations due to a fixed task sequence. Furthermore, the assignment problem is efficiently solved by the Hungarian algorithm, yielding an optimized task-to-location matching scheme. The simulation results show that the proposed mathematical programming heuristic algorithm outperforms other optimization methods across different order scales. The proposed algorithm provides satisfactory solutions, thereby significantly improving the operational efficiency and order fulfillment capacity of the AS/RS system. This study performs a collaborative optimization of task scheduling and storage location assignment in high-bay warehouses using a bi-level solution strategy. This provides strong support for meeting the production requirements of the cigarette manufacturing industry and other complex warehousing systems, highlighting the significant engineering application value of the proposed method.