Task scheduling for transport and pick robots in logistics:a comparative study on constructive heuristics  

作　　者：Hanfu Wang Weidong Chen 

机构地区：[1]Institute of Medical Robotics,Shanghai Jiao Tong University,Shanghai 200240,China [2]Department of Automation,Shanghai Jiao Tong University,Shanghai 200240,China [3]Key Laboratory of System Control and Information Processing,Ministry of Education,Department of Automation,Shanghai Jiao Tong University,Shanghai 200240,China

出　　处：《Autonomous Intelligent Systems》2021年第1期273-285,共13页自主智能系统（英文）

基　　金：This work is supported by the National Natural Science Foundation of China(Grant U1813206);the National Key R&D Program of China(Grant 2020YFC2007500);the Science and Technology Commission of Shanghai Municipality(Grant 20DZ2220400).

摘　　要：We study the Transport and Pick Robots Task Scheduling(TPS)problem,in which two teams of specialized robots,transport robots and pick robots,collaborate to execute multi-station order fulfillment tasks in logistic environments.The objective is to plan a collective time-extended task schedule with the minimization of makespan.However,for this recently formulated problem,it is still unclear how to obtain satisfying results efficiently.In this research,we design several constructive heuristics to solve this problem based on the introduced sequence models.Theoretically,we give time complexity analysis or feasibility guarantees of these heuristics;empirically,we evaluate the makespan performance criteria and computation time on designed dataset.Computational results demonstrate that coupled append heuristic works better for the most cases within reasonable computation time.Coupled heuristics work better than decoupled heuristics prominently on instances with relative few pick robot numbers and large work zones.The law of diminishing marginal utility is also observed concerning the overall system performance and different transport-pick robot numbers.

关 键 词：Multi-robot task allocation Multi-robot system Complex-schedule constraints Heterogeneous robotic order fulfillment system 

分 类 号：TP2[自动化与计算机技术—检测技术与自动化装置]