A dynamic load-balancing scheme for the parcel hub-scheduling problem

In this paper, a dynamic load-balancing algorithm (DLBA) was proposed to solve the parcel hub-scheduling problem (PHSP), which is a combinatorial optimization problem commonly found at a parcel consolidation terminal in the parcel delivery industry (PDI). The problem consists of processing a large number of inbound trailers at a much smaller number of unload docks. The parcels in the inbound trailers must be unloaded, sorted and transferred to the load docks, and loaded onto the outbound trailers. Because the transfer operation is labor intensive and the PDI operates in a time-sensitive environment, the unloading, sorting, transferring, and loading of the parcels must be done in such a way as to minimize the timespan of the transfer operation. A DLBA that considered the state of the system was proposed and evaluated to schedule the inbound trailers to the unload docks. The performance of the algorithm was compared to the performance of an efficient static load-balancing algorithm (SLBA) and to an existing lower bound. An experimental analysis shows that the DLBA offers solutions that are 8.6% better than the solutions offered by the SLBA for large-size problems and that the average computational time is only 1.34 min for the DLBA compared to 15.04 min for the SLBA. (C) 2009 Elsevier Ltd. All rights reserved.