Task scheduling for transport and pick robots in logistics: a comparative study on constructive heuristics
Authors:
Open Access
- 16 December 2021
- journal article
- research article
- Published by Springer Nature in Autonomous Intelligent Systems
- Vol. 1 (1) , 1-13
Abstract
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.Keywords
Funding Information
- National Natural Science Foundation of China (U1813206)
- National Key R&D Program of China (2020YFC2007500)
- Science and Technology Commission of Shanghai Municipality (20DZ2220400)
This publication has 35 references indexed in Scilit:
- Routing open shop and flow shop scheduling problemsEuropean Journal of Operational Research, 2011
- Time-extended multi-robot coordination for domains with intra-path constraintsAutonomous Robots, 2010
- A contribution and new heuristics for open shop schedulingComputers & Operations Research, 2010
- Heuristic constructive algorithms for open shop scheduling to minimize mean flow timeEuropean Journal of Operational Research, 2008
- On number problems for the open shop problem2007
- The routing open-shop problem on a network: Complexity and approximationEuropean Journal of Operational Research, 2006
- On the open-shop problem with preemption and minimizing the average completion timeEuropean Journal of Operational Research, 2004
- A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot SystemsThe International Journal of Robotics Research, 2004
- Classical and new heuristics for the open-shop problem: A computational evaluationEuropean Journal of Operational Research, 1998
- On the number of feasible schedules of the open-shop-problem-an application of special latin rectanglesOptimization, 1992