Polynomial-time solvable cases of the capacitated multi-echelon shipping network scheduling problem with delivery deadlines

We consider the problem of operations scheduling for a capacitated multi-echelon shipping network with delivery deadlines. Over the network, semi-finished goods are shipped from origins to many demand points through a capacitated network consisting of shipping links and capacitated processing centers. The shipping operations are performed by a fleet of transporters which require time to travel from one location to another. Each demand point has a specified shipment quantity and a deadline for delivery. The problem is to find a feasible operation schedule to minimize the shipping and penalty cost. This problem is a computationally difficult one because of its inherent combinatorial nature. We report three polynomial-time solvable cases of this problem with (a) identical order quantities; (b) designated suppliers; and (c) divisible customer order sizes. These results reveal some interesting properties of the problem, and can be used to facilitate the design of fast heuristics for operations scheduling of capacitated shipping networks.