Column generation heuristics for capacitated lotsizing problem

Author(s)

Tamara Angélica Baldo

• Document type: Master's Dissertation
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2009-05-29

Examining board members

Marcos Nereu Arenales; Reinaldo Morabito Neto; Marcos Antonio Pereira

• Advisor: Marcos Nereu Arenales

Abstract

The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms (AU)