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

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

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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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)