GRASP with path-relinking for the multi-plant capacitated lot sizing problem

Mariá C. V. Nascimento(mariahicmc.usp.br)
Mauricio G. C. Resende(mgcrresearch.att.com)
Franklina M. B. Toledo(franicmc.usp.br)

Abstract: This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition to this, the paper addresses applications of the proposed heuristics for the special case of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.

Keywords: Lot sizing, multi-plant, parallel machines, GRASP, path-relinking.

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Report TD-7B46YC, AT&T Labs Research, Florham Park, NJ, January 2008.

Download: [PDF]

Entry Submitted: 01/22/2008
Entry Accepted: 01/22/2008
Entry Last Modified: 01/22/2008

Modify/Update this entry