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

Hanfu Wang, Weidong Chen

Autonomous Intelligent Systems ›› 2021, Vol. 1 ›› Issue (1) : 17. DOI: 10.1007/s43684-021-00017-9

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

Author information +
History +

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

Multi-robot task allocation / Multi-robot system / Complex-schedule constraints / Heterogeneous robotic order fulfillment system

Cite this article

Download citation ▾
Hanfu Wang, Weidong Chen. Task scheduling for transport and pick robots in logistics: a comparative study on constructive heuristics. Autonomous Intelligent Systems, 2021, 1(1): 17 https://doi.org/10.1007/s43684-021-00017-9

References

[1]
WangH., ChenW., WangJ.. Coupled task scheduling for heterogeneous multi-robot system of two robot types performing complex-schedule order fulfillment tasks. Robot. Auton. Syst., 2020, 131(2):103560 https://doi.org/10.1016/j.robot.2020.103560
CrossRef Google scholar
[2]
KorsahG. A., StentzA., DiasM. B.. A comprehensive taxonomy for multi-robot task allocation. Int. J. Robot. Res., 2013, 32(12):1495-1512 https://doi.org/10.1177/0278364913496484
CrossRef Google scholar
[3]
NunesE., MannerM., MiticheH., GiniM.. A taxonomy for task allocation problems with temporal and ordering constraints. Robot. Auton. Syst., 2017, 90: 55-70 https://doi.org/10.1016/j.robot.2016.10.008
CrossRef Google scholar
[4]
GerkeyB. P., MatarićM. J.. A formal analysis and taxonomy of task allocation in multi-robot systems. Int. J. Robot. Res., 2004, 23(9):939-954 https://doi.org/10.1177/0278364904045564
CrossRef Google scholar
[5]
Y. Zhang, L. E. Parker, in Proceedings - IEEE International Conference on Robotics and Automation. Multi-robot task scheduling (IEEE, 2013), pp. 2992–2998. https://doi.org/10.1109/ICRA.2013.6630992.
[6]
M. G. Lagoudakis, M. Berhault, S. Koenig, P. Keskinocak, A. J. Kleywegt, in 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 1. Simple auctions with performance guarantees for multi-robot task allocation, (2004), pp. 698–705. https://doi.org/10.1109/iros.2004.1389434.
[7]
LiuZ., WangH., ChenW., YuJ., ChenJ.. An incidental delivery based method for resolving multirobot pairwised transportation problems. IEEE Trans. Intell. Transp. Syst., 2016, 17(7):1852-1866 https://doi.org/10.1109/TITS.2015.2508783
CrossRef Google scholar
[8]
ThakoorO., GargJ., NagiR.. Multiagent UAV routing: a game theory analysis with tight price of anarchy bounds. IEEE Trans. Autom. Sci. Eng., 2020, 17(1):100-116 https://doi.org/10.1109/TASE.2019.2902360
CrossRef Google scholar
[9]
Bernardine DiasM., ZlotR., KalraN., StentzA.. Market-based multirobot coordination: A survey and analysis. Proc. IEEE, 2006, 94(7):1257-1270 https://doi.org/10.1109/JPROC.2006.876939
CrossRef Google scholar
[10]
H. Wang, M. Rubenstein, Shape Formation in Homogeneous Swarms Using Local Task Swapping. IEEE Trans. Robot. (2020). https://doi.org/10.1109/TRO.2020.2967656.
[11]
GombolayM. C., WilcoxR. J., ShahJ. A.. Fast scheduling of robot teams performing tasks with temporospatial constraints. IEEE Trans. Reliab., 2018, 34(1):220-239 https://doi.org/10.1109/TRO.2018.2795034
[12]
GarattoniL., BirattariM.. Autonomous task sequencing in a robot swarm. Sci. Robot., 2018, 3(20):0430 https://doi.org/10.1126/scirobotics.aat0430
CrossRef Google scholar
[13]
JonesE. G., DiasM. B., StentzA.. Time-extended multi-robot coordination for domains with intra-path constraints. Auton. Robot., 2011, 30(1):41-56 https://doi.org/10.1007/s10514-010-9202-3
CrossRef Google scholar
[14]
UchoaE., PecinD., PessoaA., PoggiM., VidalT., SubramanianA.. New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res., 2017, 257(3):845-858 https://doi.org/10.1016/j.ejor.2016.08.012
CrossRef Google scholar
[15]
M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Fifth Edition (Springer, 2016). https://doi.org/10.1007/978-3-319-26580-3.
[16]
ChernykhI., KononovA., SevastyanovS.. Efficient approximation algorithms for the routing open shop problem. Comput. Oper. Res., 2013, 40(3):841-847 https://doi.org/10.1016/j.cor.2012.01.006
CrossRef Google scholar
[17]
L. R. Abreu, J. O. Cunha, B. A. Prata, J. M. Framinan, A genetic algorithm for scheduling open shops with sequence-dependent setup times. Comput. Oper. Res.113: (2020). https://doi.org/10.1016/j.cor.2019.104793.
[18]
MejíaG., YuraszeckF.. A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times. Eur. J. Oper. Res., 2020, 285(2):484-496 https://doi.org/10.1016/j.ejor.2020.02.010
CrossRef Google scholar
[19]
AnandE., PanneerselvamR.. Literature review of open shop scheduling problems. Intell. Inf. Manag., 2015, 7(1):33-52 https://doi.org/10.4236/iim.2015.71004
[20]
BräselH., HennesH.. On the open-shop problem with preemption and minimizing the average completion time. Eur. J. Oper. Res., 2004, 157(3):607-619 https://doi.org/10.1016/S0377-2217(03)00249-2
CrossRef Google scholar
[21]
AverbakhI., BermanO., ChernykhI.. The routing open-shop problem on a network: Complexity and approximation. Eur. J. Oper. Res., 2006, 173(2):531-539 https://doi.org/10.1016/j.ejor.2005.01.034
CrossRef Google scholar
[22]
BräselH., HermsA., MörigM., TautenhahnT., TuschJ., WernerF.. Heuristic constructive algorithms for open shop scheduling to minimize mean flow time. Eur. J. Oper. Res., 2008, 189(3):856-870 https://doi.org/10.1016/j.ejor.2007.02.057
CrossRef Google scholar
[23]
AndresenM., BräselH., MörigM., TuschJ., WernerF., WilleniusP.. Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop. Math. Comput. Model., 2008, 48(7-8):1279-1293 https://doi.org/10.1016/j.mcm.2008.01.002
CrossRef Google scholar
[24]
LowC., YehY.. Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated. Robotics and Computer-Integrated Manufacturing, 2009, 25(2):314-322 https://doi.org/10.1016/j.rcim.2007.07.017
CrossRef Google scholar
[25]
WangH., ChenW., WangJ.. Heterogeneous multi-agent routing strategy for robot-and-picker-to-good order fulfillment system. Adv. Intell. Syst. Comput., 2019, 867: 237-249 https://doi.org/10.1007/978-3-030-01370-7_19
[26]
ScholzA., SchubertD., WäscherG.. Order picking with multiple pickers and due dates – Simultaneous solution of Order Batching, Batch Assignment and Sequencing, and Picker Routing Problems. Eur. J. Oper. Res., 2017, 263(2):461-478 https://doi.org/10.1016/j.ejor.2017.04.038
CrossRef Google scholar
[27]
NaderiB., Fatemi GhomiS. M. T., AminnayeriM., ZandiehM.. A contribution and new heuristics for open shop scheduling. Comput. Oper. Res., 2010, 37(1):213-221 https://doi.org/10.1016/j.cor.2009.04.010
CrossRef Google scholar
[28]
BräselH., TautenhahnT., WernerF.. Constructive heuristic algorithms for the open shop problem. Computing, 1993, 51(2):95-110 https://doi.org/10.1007/BF02243845
CrossRef Google scholar
[29]
BräselH., HarborthM., TautenhahnT., WilleniusP.. On the set of solutions of the open shop problem. Ann. Oper. Res., 1999, 92: 241-263 https://doi.org/10.1023/A:1018938915709
CrossRef Google scholar
[30]
H. Bräsel, in Perspectives on Operations Research. Matrices in Shop Scheduling Problems (DUV, 2007), pp. 17–41. https://doi.org/10.1007/978-3-8350-9064-4_2.
[31]
H. Bräsel, M. Kleinau, in System Modelling and Optimization. On number problems for the open shop problem (Springer, 2007), pp. 145–154. https://doi.org/10.1007/bfb0113281.
[32]
YuW., LiuZ., WangL., FanT.. Routing open shop and flow shop scheduling problems. Eur. J. Oper. Res., 2011, 213(1):24-36 https://doi.org/10.1016/j.ejor.2011.02.028
CrossRef Google scholar
[33]
MathewN., SmithS. L., WaslanderS. L.. Planning paths for package delivery in heterogeneous multirobot teams. IEEE Trans. Autom. Sci. Eng., 2015, 12(4):1298-1308 https://doi.org/10.1109/TASE.2015.2461213
CrossRef Google scholar
[34]
KamraN., KumarT. K. S., AyanianN.. Combinatorial problems in multirobot battery exchange systems. IEEE Trans. Autom. Sci. Eng., 2018, 15(2):852-862 https://doi.org/10.1109/TASE.2017.2767379
CrossRef Google scholar
[35]
McIntireM., NunesE., GiniM.. Iterated multi-robot auctions for precedence-constrained task scheduling. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (AAMAS ’16), 2016 Richland International Foundation for Autonomous Agents and Multiagent Systems 1078-1086 http://dl.acm.org/citation.cfm?id=2936924.2937082
[36]
GuéretC., PrinsC.. Classical and new heuristics for the open-shop problem: A computational evaluation. Eur. J. Oper. Res., 1998, 107(2):306-314 https://doi.org/10.1016/S0377-2217(97)00332-9
CrossRef Google scholar
[37]
BräselH., KleinauM.. On the number of feasible schedules of the open-shop-problem—an application of special latin rectangles. Optimization, 1992, 23(3):251-260 https://doi.org/10.1080/02331939208843762
CrossRef Google scholar
[38]
P. Samuelson, W. Nordhaus, Economics, McGraw-Hill Education; 19th edition (April 8, 2009), (2010).
Funding
national natural science foundation of china(U1813206); national key r&d program of china(2020YFC2007500); science and technology commission of shanghai municipality(20DZ2220400)

Accesses

Citations

Detail

Sections
Recommended

/