A Lagrangean heuristic for integrated production and transportation planning problems in a dynamic, multi-item, two-layer supply chain

Abstract

We present a Lagrangean-based decomposition that is used to generate solutions for an integrated production and transportation planning problem in a two-stage supply chain. This supply chain consists of a number of facilities, each capable of producing the final products, and a number of retailers. It is assumed that the retailers' demands are known and deterministic, and that there are production capacity constraints. The problem is formulated as a multi-commodity network flow problem with fixed charge costs which is a NP-hard problem. An alternative formulation is provided whose linear programming relaxation gives tighter lower bounds. The quality of the lower and upper bounds from the Lagrangean decomposition is tested on a large set of randomly generated problems.

Keywords:

• Supply chain
• production planning
• fixed-charge cost
• multi-commodity network flow
• Lagrangean decomposition

Notes

* Refers to problems where subproblems (SP_1k ) are solved using the dynamic programming algorithm.