A zero-inventory production and distribution problem with a fixed customer sequence

In this paper, we study the zero-inventory production and distribution problem with a single transporter and a fixed sequence of customers. The production facility has a limited production rate, and the delivery truck has non-negligible traveling times between locations. The order in which customers may receive deliveries is fixed. Each customer requests a delivery quantity and a time window for receiving the delivery. The lifespan of the product starts as soon as the production for a customer’s order is finished, which makes the product expire in a constant time. Since the production facility and the shipping truck are limited resources, not all the customers may receive the delivery within their specified time windows and/or within product lifespan. The problem is then to choose a subset of customers from the given sequence to receive the deliveries to maximize the total demand satisfied, without violating the product lifespan, the production/distribution capacity, and the delivery time window constraints. We analyze several fundamental properties of the problem and show that these properties can lead to a fast branch and bound search procedure for practical problems. A heuristic lower bound on the optimal solution is developed to accelerate the search. Empirical studies on the computational effort required by the proposed search procedure comparing to that required by CPLEX on randomly generated test cases are reported.