Collaborative optimization of task scheduling and multi-agent path planning in automated warehouses

Complex & Intelligent Systems - Tập 9 Số 5 - Trang 5937-5948 - 2023
Honglin Zhang1, Yaohua Wu1, Jinchang Hu2, Yanyan Wang1
1Faculty of Control Science and Engineering, Shandong University, Jinan, China
2School of Business, Shandon Normal University, Jinan, China

Tóm tắt

AbstractTask scheduling (TS) and multi-agent-path-finding (MAPF) are two cruxes of pickup-and-delivery in automated warehouses. In this paper, the two cruxes are optimized simultaneously. Firstly, the system model, task model, and path model are established, respectively. Then, a task scheduling algorithm based on enhanced HEFT, a heuristic MAPF algorithm and a TS- MAPF algorithm are proposed to solve this combinatorial optimization problem. In EHEFT, a novel rank priority rule is used to determine task sequencing and task allocation. In MAPF algorithm, a CBS algorithm with priority rules is designed for path search. Subsequently, the TS-MAPF algorithm which combines EHEFT and MAPF is proposed. Finally, the proposed algorithms are tested separately against relevant typical algorithms at different scales. The experimental results indicate that the proposed algorithms exhibited good performance.

Từ khóa


Tài liệu tham khảo

Brucker P, Krämer A (1996) Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. Eur J Oper Res 90(2):214–226

Roodbergen L (2007) Design and control of warehouse order picking: A literature review. European Journal of Operational Research, 2007.

Wang Y, Liu Z, Huang K, et al (2020) Model and solution approaches for retrieval operations in a multi-tier shuttle warehouse system. Computers & Industrial Engineering, 141(Mar.):106283.1–106283.9.

Dujuan W, Jiaqi Z, Xiaowen W, Cheng TCE, Yunqiang Y, Yanzhang W (2019) Integrated production and multiple trips vehicle routing with time windows and uncertain travel times. Comput Oper Res 103(2019):1–12

Xiaochang L, Dujuan W, Yunqiang Y, Cheng TCE (2023) Robust optimization for the electric vehicle pickup and delivery problem with time windows and uncertain demands. Comput Oper Res 151(2023):106119

Yunqiang Y, Yongjian Y, Dujuan W, Cheng TCE, Chin-Chia W (2018) Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents. Nav Res Logist 2018(65):393–409

Ma H, Su S, Simon, D, Fei M (2015) Ensemble multi-objective biogeography-based optimization with application to automated warehouse scheduling. Engineering Applications of Artificial Intelligence, 44(SEP.), 79–90.

Peng, Y, Peng, Y (2015) Integrated optimization of storage location assignment and sequencing in multi-shuttle automated storage/retrieval systems under modified multi-command cycle. 2015 IEEE International Conference on Information and Automation (ICIA) IEEE.

Hu H, Li Z, Hu H, Chen J, Ge J, Li C, et al (2018) Multi-objective scheduling for scientific workflow in multicloud environment. Journal of Network and Computer Applications, 114(JUL.), 108–122.

Wu Q, Ishikawa F, Zhu Q, Xia Y, Wen J (2017) Deadline-constrained cost optimization approaches for workflow scheduling in clouds. IEEE Transactions on Parallel and Distributed Systems, PP (12), 1–1.

Tong Z, Deng X, Chen H, Mei J, Liu H (2019) QL-HEFT: a novel machine learning scheduling scheme base on cloud computing environment. Neural Computing and Applications.

Zhang H, Wu Y, Sun Z (2021) EHEFT-R: multi-objective task scheduling scheme in cloud computing. Complex & Intelligent Systems, 1–8.

Sun Z, Gu C, Zhang H, Huang H (2021) T2FA: A Heuristic Algorithm for Deadline-constrained Workflow Scheduling in Cloud with Multicore Resource. 2021 IEEE 14th International Conference on Cloud Computing (CLOUD), 345–354.

Dujuan W, Yugang Y, Yunqiang Y, Cheng TCE (2021) Multi-agent scheduling problems under multitasking. Int J Prod Res 59(12):3633–3663

Stern R. Multi-agent path finding - an overview. Ben Gurion University of the Negev, Be'er Sheva, Israel.

Čáp M, Novak P, Kleiner A, Selecky M (2015) Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Trans Autom Sci Eng 12(3):835–849

Čáp M (2017) Centralized and Decentralized Algorithms for Multi-Robot Trajectory Coordination.

Sharon G, Stern R, Felner A, Sturtevant N. R (2015) Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219(feb.), 40–66.

Ma H, Koenig S (2016) Optimal target assignment and path finding for teams of agents. International Foundation for Autonomous Agents and Multiagent Systems.

Kulak O, Sahin Y, Taner, & M., E. (2012) Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms. Flex Serv Manuf J 24(1):52–80

Van Gils T, Ramaekers K, Braekers K et al (2018) Increasing order picking efficiency by integrating storage, batching, zone picking, and routing policy decisions. Int J Prod Econ 197(3):243–261

Ma H, Koenig S. AI buzzwords explained. AI Matters, 2017.