Geração de colunas para o problema de dimensionamento de lotes de produção com limitações de capacidade / Column generation heuristics for capacitated lotsizing problem

AUTOR(ES)

Tamara Angélica Baldo

DATA DE PUBLICAÇÃO

2009

RESUMO

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

ASSUNTO(S)

capacitated lot sizing problem problema de dimensionamento de lotes decomposição de dantzig-wolfe heurística lagrangiana lagrangian-based heuristics column generation algorithms geração de colunas dantzig-wolfe decomposition

Documentos Relacionados

• AN ALGORITHM WITH COLUMN AND CUT GENERATION FOR THE CAPACITATED VEHICLE ROUTING PROBLEM
• On stabilizing column generation for cutting stok problem
• Local branching aplicado ao problema de dimensionamento de lotes
• Uma heurística GRASP para o problema de dimensionamento de lotes com múltiplas plantas
• Novas heurísticas para o problema de geração de escalas de jogos para torneios esportivos