Economic lot sizing for multisupplier, multi-item procurement systems.

Abstract

We consider an assembly facility of a major U.S. manufacturer. Thousands of parts are delivered directly by dozens of suppliers. We address the problem of finding good delivery schedules for all the suppliers simultaneously. We seek to minimize the total inventory holding cost, transportation cost and the cost of unloading the inbound freight at the docks, while satisfying the daily demands for each item. This problem differs from the traditional multi-item scheduling problem in the structure of the ordering cost. We assume that the transportation cost is proportional to the number of trucks shipped in each period. The computation of the number of trucks is a bin-packing problem, where we fit the item containers into trucks. We present a sequential procedure based on a decomposition of the problem into three subproblems. First, we find the best regeneration frequency for each supplier independently based on an aggregate analysis. Then, we generate all the day-of-week combinations consistent with such a frequency. For each combination, we determine the item mix and quantities on each day. As a result, we obtain a set of delivery schedules for each supplier. Finally, we select the best schedule for each supplier, considering the dock capacity constraints and all the suppliers simultaneously. Each step is a solution to an optimization problem. The second step is a simplified version of a multi-item joint replenishment problem with volume-sensitive setup cost. We characterize the solution to this problem and develop a dynamic programming algorithm to solve it. The delivery schedule selection step is a multidimensional multiple choice knapsack problem, for which we develop a surrogate relaxation procedure. The problem is converted to a single-knapsack problem using surrogate multipliers. The solution to the surrogate single-knapsack problem provides a lower bound on the optimal solution and is intelligently converted to a solution to the multiple-knapsack problem. All the steps are tested for both quality of the solution (if not optimal) and computation times. The sequential procedure is shown to outperform several other approximate procedures and is proven to be computationally tractable.