A rescheduling and cost allocation mechanism for delayed arrivals

We propose a solution to the problem of rescheduling a sequence of arrivals that are subject to a delay event at a common destination. Such situations include jobs arriving at a single production facility, aircraft whose landings are postponed, and ships that are inbound to a dock or lightering facility. Each arrival faces a nonlinear cost due to the delay, but the delay costs can be mitigated by allowing the arrivals to be reordered. We optimize the reordering process by designing a Vickrey-Clarke-Groves (VCG) mechanism to construct a payoff matrix describing the amounts necessary to move the currently assigned arrival slots either earlier or later. Using this payoff matrix, we compute the optimal reordering of the arrivals by utilizing the well-known solution to the assignment problem, which maximizes the benefit in a computationally efficient fashion. The VCG mechanism is strategyproof, that is, no arrival has an incentive to misreport the value of moving up or down in the sequence. We also show that participating in the centralized process is to no arrival's disadvantage. Because VCG procedures in general are subject to budget deficits, we provide alternative mechanisms to overcome this difficulty. Finally, we carry out computational experiments demonstrating that the VCG mechanism can be implemented for realistically-sized problem sets and that the cost savings are significant.