The parcel hub scheduling problem with limited conveyor capacity and controllable unloading speeds. (English) Zbl 1519.90068
Summary: We investigate a specific truck scheduling problem at cross-docks in the postal service industry on an operational level aiming to maximise the number of duly parcels assuming fixed departure times of the outbound trucks. The inbound gates and the conveyors as means of transportation inside the hub constitute the bottleneck resources. As a novel extension, we propose flexible unloading speeds to efficiently utilise the scarce resources. We formalise the problem with a mixed integer program and explicitly incorporate controllable unloading speeds of the inbound trucks. We determine the computational complexity and develop a genetic algorithm to efficiently solve the problem. Our investigation focuses on both the performance of the genetic algorithm and the applicability of the results in a real-world environment by implementing scheduling policies in a simulation model that considers individual parcel interactions. Based on our experimental results, we can state that especially in problem settings with scarce conveyor capacities, our approach to incorporate controllable unloading speeds has the potential of significantly increasing the number of duly parcels.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90B06 | Transportation, logistics and supply chain management |
| 90C11 | Mixed integer programming |
References:
| [1] | Apte, UM; Viswanathan, S., Effective cross docking for improving distribution efficiencies, Int J Logist, 3, 3, 291-302 (2000) · doi:10.1080/713682769 |
| [2] | Artigues, C.; Lopez, P.; Hait, A., The energy scheduling problem: industrial case-study and constraint propagation techniques, Int J Prod Econ, 143, 1, 13-23 (2013) · doi:10.1016/j.ijpe.2010.09.030 |
| [3] | Boysen, N., Truck scheduling at zero-inventory cross docking terminals, Comput Oper Res, 37, 1, 32-41 (2010) · Zbl 1171.90391 · doi:10.1016/j.cor.2009.03.010 |
| [4] | Boysen, N.; Fliedner, M., Cross dock scheduling: classification, literature review and research agenda, Omega, 38, 6, 413-422 (2010) · doi:10.1016/j.omega.2009.10.008 |
| [5] | Boysen, N.; Briskorn, D.; Tschöke, M., Truck scheduling in cross-docking terminals with fixed outbound departures, OR Spectrum, 35, 2, 479-504 (2013) · Zbl 1263.90039 · doi:10.1007/s00291-012-0311-6 |
| [6] | Boysen, N.; Fedtke, S.; Weidinger, F., Truck scheduling in the postal service industry, Transp Sci, 51, 2, 723-736 (2017) · doi:10.1287/trsc.2016.0722 |
| [7] | Carrera S, Chami K, Guimaraes R, et al (2008) Negotiation models for logistic plarform planning and scheduling. In: 11th international workshop on project management and scheduling, pp 43-46 |
| [8] | Cheng, T.; Chen, Z.; Li, CL, Parallel-machine scheduling with controllable processing times, IIE Trans, 28, 2, 177-180 (1996) · doi:10.1080/07408179608966263 |
| [9] | Clausen, U.; Diekmann, D.; Pöting, M., Operating parcel transshipment terminals: a combined simulation and optimization approach, J Simul, 11, 1, 2-10 (2017) · doi:10.1057/s41273-016-0032-y |
| [10] | Corsten, H.; Becker, F.; Salewski, H., Integrating truck and workforce scheduling in a cross-dock: analysis of different workforce coordination policies, J Bus Econ, 90, 2, 207-237 (2020) |
| [11] | Du, J.; Leung, JYT, Minimizing total tardiness on one machine is np-hard, Math Oper Res, 15, 3, 483-495 (1990) · Zbl 0714.90052 · doi:10.1287/moor.15.3.483 |
| [12] | Graham RL, Lawler EL, Lenstra JK, et al (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of discrete mathematics, vol 5. Elsevier, pp 287-326 · Zbl 0411.90044 |
| [13] | Haneyah S, Schutten JM, Fikse K (2014) Throughput maximization of parcel sorter systems by scheduling inbound containers. In: Efficiency and innovation in logistics. Springer, pp 147-159 |
| [14] | Holland, JH, Adaption in natural and artificial systems: an introductory analysis with application to biology, control, and artificial intelligence (1975), Detroit: The University of Michigan Press, Detroit · Zbl 0317.68006 |
| [15] | Jarrah, AI; Johnson, E.; Neubert, LC, Large-scale, less-than-truckload service network design, Oper Res, 57, 3, 609-625 (2009) · Zbl 1233.90067 · doi:10.1287/opre.1080.0587 |
| [16] | Khir, R.; Erera, A.; Toriello, A., Two-stage sort planning for express parcel delivery, IISE Trans, 53, 12, 1353-1368 (2021) |
| [17] | Koné, O.; Artigues, C.; Lopez, P., Event-based milp models for resource-constrained project scheduling problems, Comput Oper Res, 38, 1, 3-13 (2011) · Zbl 1231.90202 · doi:10.1016/j.cor.2009.12.011 |
| [18] | Ladier, AL; Alpan, G., Cross-docking operations: current research versus industry practice, Omega, 62, 145-162 (2016) · doi:10.1016/j.omega.2015.09.006 |
| [19] | Li, Y.; Lim, A.; Rodrigues, B., Crossdocking-jit scheduling with time windows, J Oper Res Soc, 55, 12, 1342-1351 (2004) · Zbl 1088.90026 · doi:10.1057/palgrave.jors.2601812 |
| [20] | McWilliams, DL; McBride, ME, Exploring mathematical approximation for the time spans of transfer operations in parcel transshipment terminals, Comput Ind Eng, 64, 1, 342-356 (2013) · doi:10.1016/j.cie.2012.09.020 |
| [21] | McWilliams, DL; Stanfield, PM; Geiger, CD, The parcel hub scheduling problem: a simulation-based solution approach, Comput Ind Eng, 49, 3, 393-412 (2005) · doi:10.1016/j.cie.2005.07.002 |
| [22] | Mendes, JJ; Gonçalves, JF; Resende, MG, A random key based genetic algorithm for the resource constrained project scheduling problem, Comput Oper Res, 36, 1, 92-109 (2009) · Zbl 1163.90500 · doi:10.1016/j.cor.2007.07.001 |
| [23] | Molavi, D.; Shahmardan, A.; Sajadieh, MS, Truck scheduling in a cross docking systems with fixed due dates and shipment sorting, Comput Ind Eng, 117, 29-40 (2018) · doi:10.1016/j.cie.2018.01.009 |
| [24] | Naber, A.; Kolisch, R., Mip models for resource-constrained project scheduling with flexible resource profiles, Eur J Oper Res, 239, 2, 335-348 (2014) · Zbl 1339.90249 · doi:10.1016/j.ejor.2014.05.036 |
| [25] | Nattaf, M.; Artigues, C.; Lopez, P., Energetic reasoning and mixed-integer linear programming for scheduling with a continuous resource and linear efficiency functions, OR Spectrum, 38, 2, 459-492 (2016) · Zbl 1339.90147 · doi:10.1007/s00291-015-0423-x |
| [26] | Ou, J.; Hsu, VN; Li, CL, Scheduling truck arrivals at an air cargo terminal, Prod Oper Manag, 19, 1, 83-97 (2010) · doi:10.1111/j.1937-5956.2009.01068.x |
| [27] | Qijun Q, Zhang Z, Song X et al (2009) Application research of cross docking logistics in food cold-chain logistics. In: 2009 international conference on information management. Innovation management and industrial engineering. IEEE, pp 236-240 |
| [28] | Rothlauf, F., Design of modern heuristics: principles and application (2011), Berlin: Springer, Berlin · Zbl 1232.68002 · doi:10.1007/978-3-540-72962-4 |
| [29] | Selinka, G.; Franz, A.; Stolletz, R., Time-dependent performance approximation of truck handling operations at an air cargo terminal, Comput Oper Res, 65, 164-173 (2016) · Zbl 1349.90233 · doi:10.1016/j.cor.2014.06.005 |
| [30] | Serrano, C.; Delorme, X.; Dolgui, A., Scheduling of truck arrivals, truck departures and shop-floor operation in a cross-dock platform, based on trucks loading plans, Int J Prod Econ, 194, 102-112 (2017) · doi:10.1016/j.ijpe.2017.09.008 |
| [31] | Shabtay, D.; Steiner, G., A survey of scheduling with controllable processing times, Discret Appl Math, 155, 13, 1643-1666 (2007) · Zbl 1119.90022 · doi:10.1016/j.dam.2007.02.003 |
| [32] | Stephan, K.; Boysen, N., Cross-docking, J Manag Control, 22, 1, 129 (2011) · doi:10.1007/s00187-011-0124-9 |
| [33] | Tadumadze, G.; Boysen, N.; Emde, S., Integrated truck and workforce scheduling to accelerate the unloading of trucks, Eur J Oper Res, 278, 1, 343-362 (2019) · Zbl 1430.90291 · doi:10.1016/j.ejor.2019.04.024 |
| [34] | Theophilus, O.; Dulebenets, MA; Pasha, J., Truck scheduling at cross-docking terminals: a follow-up state-of-the-art review, Sustainability, 11, 19, 5245 (2019) · doi:10.3390/su11195245 |
| [35] | Tootkaleh, SR; Ghomi, SF; Sajadieh, MS, Cross dock scheduling with fixed outbound trucks departure times under substitution condition, Comput Ind Eng, 92, 50-56 (2016) · doi:10.1016/j.cie.2015.12.005 |
| [36] | Tripp C (2021) Dienstleisternetze in der distributionslogistik. In: Distributions-und handelslogistik. Springer, pp 359-421 |
| [37] | Van Belle, J.; Valckenaers, P.; Cattrysse, D., Cross-docking: state of the art, Omega, 40, 6, 827-846 (2012) · doi:10.1016/j.omega.2012.01.005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
