Lagrangean based lower bounds for a multi-plant lot-sizing problem with capacity constraints

Samuel Deleplanque (1) , Safia Kedad-Sidhoum (2) , Alain Quilliot (1)

1 LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes
2 RO - Recherche Opérationnelle

The paper addresses a multi-item, multi-plant lot-sizing problem with capacity restrictions. A set of facilities (plants) is available for producing some items. For each period of a discrete planning horizon, a demand is de ned for each pair of item and plant. The problem consists in producing all the demands such that the total production, inventory, setup and transfer costs is minimized. Setup production times are considered as well as capacity constraints on the production. Moreover, transfers between plants are allowed, however, the total transferred quantity between each pair of plants is upper bounded as well as the total inventory at each plant for a given period. The problem considered is NP-hard. We quote the work of Sambivasan and Yahya that describes some Lagrangean-based heuristics to solve a relaxed version of the problem where no transfer and storage capacities are considered. In the present work, we propose a Lagrangean lower bound on the optimal cost value of the problem based on the decomposition of the problem into Facility Location and Multi-Commodity Flow problems.

Mots clés: multi-plant; lot-sizing; capacity constraints; Lagrangean-based heuristics; Multi-Commodity Flow

Domaines: Algorithme et structure de données [cs.DS]; Recherche opérationnelle [math.OC]

Samuel Deleplanque, Safia Kedad-Sidhoum, Alain Quilliot. Lagrangean based lower bounds for a multi-plant lot-sizing problem with capacity constraints. International Symposium on Combinatorial Optimization 2012, Sep 2012, Oxford, United Kingdom. ⟨hal-00742184⟩