Parallel machine scheduling with multiple unloading servers

We study a parallel machine scheduling problem with multiple unloading servers. After a machine completes processing one job, an unloading server is needed to remove the job from the machine. Only after unloading, the machine is available for processing the next job. The model is motivated by the milk run operations of a logistics company that faces limited unloading docks at the warehouse. Our interest is to minimize the total completion time of the jobs. We show that the shortest-processing-time-first (SPT) algorithm has a worst-case bound of 2. We also develop other improved heuristic algorithms as well as a branch-and-bound algorithm to solve the problem. Computational experiments show that our algorithms are efficient and effective.