The Integrated Production and Transportation Scheduling Problem for a Product with a Short Lifespan

The integrated production and transportation scheduling problem (PTSP) with capacity constraints is common in many industries. An optimal solution to PTSP requires one to simultaneously solve the production scheduling and the transportation routing problems, which requires excessive computational time, even for relatively small problems. In this study, we consider a variation of PTSP that involves a short shelf life product; hence, there is no inventory of the product in process. Once a lot of the product is produced, it must be transported with nonnegligible transportation time directly to various customer sites within its limited lifespan. The objective is to determine the minimum time required to complete producing and delivering the product to meet the demand of a given set of customers over a wide geographic region. This problem is NP–hard in the strong sense. We analyze the properties of this problem, develop lower bounds on the optimal solution, and propose a two–phase heuristic based on the analysis. The first phase uses either a genetic or a memetic algorithm to select a locally optimal permutation of the given set of customers; the second phase partitions the customer sequence and then uses the Gilmore–Gomory algorithm to order the subsequences of customers to form the integrated schedule. Empirical observations on the performance of this heuristic are reported.