A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems

In this paper, we propose a simple but efficient heuristic that combines construction and improvement heuristic ideas to solve multi-level lot-sizing problems. A relax-and-fix heuristic is firstly used to build an initial solution, and this is further improved by applying a fix-and-optimize heuristi...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2015-10, Vol.21 (5), p.687-717
Main Authors: Toledo, Claudio Fabiano Motta, da Silva Arantes, Márcio, Hossomi, Marcelo Yukio Bressan, França, Paulo Morelato, Akartunalı, Kerem
Format: Article
Language:English
Subjects:
Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Computer science
Decomposition
Genetic algorithms
Heuristic
Integer programming
Management Science
Manufacturing
Mathematical programming
Mathematics
Mathematics and Statistics
Methods
Operations Research
Operations Research/Decision Theory
Order quantity
Problem solving
Production planning
Scheduling
Statistical analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we propose a simple but efficient heuristic that combines construction and improvement heuristic ideas to solve multi-level lot-sizing problems. A relax-and-fix heuristic is firstly used to build an initial solution, and this is further improved by applying a fix-and-optimize heuristic. We also introduce a novel way to define the mixed-integer subproblems solved by both heuristics. The efficiency of the approach is evaluated solving two different classes of multi-level lot-sizing problems: the multi-level capacitated lot-sizing problem with backlogging and the two-stage glass container production scheduling problem (TGCPSP). We present extensive computational results including four test sets of the Multi-item Lot-Sizing with Backlogging library, and real-world test problems defined for the TGCPSP, where we benchmark against state-of-the-art methods from the recent literature. The computational results show that our combined heuristic approach is very efficient and competitive, outperforming benchmark methods for most of the test problems.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-015-9295-0