A cross decomposition algorithm for the capacitated dynamic demand coordinated replenishment problem

Inventory and production practitioners frequently confront mathematically complex lot sizing problems. An important application of this nature arises in the context of multi-item lot-sizing/replenishment decisions. In particular, the coordinated replenishment problem models the replenishment decisions for a group of items sharing common resources (e.g. a common supplier, a common mode of transportation, or a common production process). A major setup cost is incurred each time one or more items in a product family are produced, and a minor setup cost is associated with each item replenished. The problem is computationally challenging. Dynamic demand and capacity considerations introduce additional computational burdens. Hence, the goal of the dissertation is to address and resolve the inherent computational challenges of capacitated dynamic demand coordinated replenishment problems.; The problem is modeled using an arborescent network based mixed-integer-programming formulation. A cross decomposition based solution algorithm is developed for computing the optimal solution of the problem. Setting binary decision variables to suitable values results in a primal sub-problem, which in this case, is a transportation problem. The dual sub-problem is obtained by relaxing the demand constraints. The relaxed problem is further decomposed into a conditional knapsack problem one for each production period. Convergence of the optimal algorithm is guaranteed through the use of a Benders master problem.; An important contribution of this dissertation is the development of a cross decomposition based procedure for finding the optimal solution to a coordinated replenishment problem. The caveats of the technique and the handicaps of the proposed relaxation provide valuable insight to researchers and practitioners in approaching other combinatorial problems with similar mathematical structure.; The dissertation also introduces a new class of knapsack problems, called The Conditional Knapsack, with excellent potential applications in logistics, marketing and financial management. A novel solution algorithm—also based on cross decomposition—is developed for this class of problems. The computational challenges hindered by the conditional knapsack problem are investigated. Another significant contribution of the dissertation is the development of an efficient procedure for solving the continuous relaxation of the conditional knapsack problem.; The dissertation reports the results of a computational study consisting of a set of randomly generated problems for the capacitated coordinated replenishment problem and the conditional knapsack problem, and makes recommendations for further research.