Lagrangean relaxation method for the multiregion dynamic capacity expansion problem with discrete expansion size

Abstract

Consider the problem of determining a schedule of capacity expansions for m producing regions and a schedule of shipment from the regions to n markets so as to meet the market demands over a T-planning horizon. In this thesis we present a mixed integer programming model for this sort of the multiregion dynamic capacity expansion problem, where expansion sizes are assumed to be discrete. The objective of the model is to minimize the discounted capacity expansion and shipment cost over the planning horizon subject to demand and capacity constraints. We use the Lagrangean relaxation method to decompose our problem into the subproblem of each region. A subgradient procedure is used to select the Lagrange multipliers that maximize the lower bound produced by the relaxation. The heuristic algorithm of this thesis improves on feasible solutions by eliminating unnecessary overcapacities. Computational results are given for 33 test problems.