A polynomial time approximation scheme for the scheduling problem in the AGV system
Xinrui Li, Chaoyang Wang, Hao Hu, Yanxue Liang
Abstract
Logistics warehouses face the challenge of fulfilling large bulk pick orders limit in a given time, as the information of logistics orders is different and timeliness. Therefore, in automated warehouses, it is imperative to improve the efficiency and intelligence of order picking by robotic systems. However, the existing automated guided vehicle (AGV) system has only a few fixed functions (such as order sorting and transportation, etc.), which cannot be changed in time according to actual needs. Meanwhile, the scheduling algorithm has only mass heuristics results and a few approximate algorithm results. In this paper, we build a new AGV system, including two kinds of shelves and four kinds of stations, where the system can add new station types according to the actual situation. We establish the equivalent relationship between the order group picking task in this system and the multi-stage hybrid flow shop scheduling problem, without considering the order group transfer process between stations. Furthermore, we propose a polynomial time approximation scheme (PTAS) for the scheduling problem in this system which has been proved to be strongly NP-hard [13].
BibTeX
@inproceedings{iros2022_apolynomialtimea,
title = {A polynomial time approximation scheme for the scheduling problem in the AGV system},
author = {Xinrui Li and Chaoyang Wang and Hao Hu and Yanxue Liang},
booktitle = {IROS 2022},
year = {2022}
}