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

Claudio Fabiano Motta Toledo, Márcio da Silva Arantes, Marcelo Yukio Bressan Hossomi, Paulo Morelato França, Kerem Akartunali

Research output: Contribution to journalArticle

24 Citations (Scopus)

Abstract

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.
LanguageEnglish
Pages687-717
Number of pages31
JournalJournal of Heuristics
Volume21
Issue number5
Early online date2 Jul 2015
DOIs
Publication statusPublished - Oct 2015

Fingerprint

Lot Sizing
Containers
Scheduling
Optimise
Heuristics
Glass
Backlogging
Production/scheduling
Container
Test Problems
Computational Results
Scheduling Problem
Benchmark
Test Set
Lot sizing
Integer

Keywords

  • lot-sizing
  • heuristics
  • relax-and-fix
  • fix-and-optimize
  • backlogging

Cite this

Toledo, Claudio Fabiano Motta ; Arantes, Márcio da Silva ; Hossomi, Marcelo Yukio Bressan ; França, Paulo Morelato ; Akartunali, Kerem. / A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems. In: Journal of Heuristics. 2015 ; Vol. 21, No. 5. pp. 687-717.
@article{49457401ea4c4fa9be95004d93eec8c5,
title = "A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems",
abstract = "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.",
keywords = "lot-sizing, heuristics, relax-and-fix, fix-and-optimize, backlogging",
author = "Toledo, {Claudio Fabiano Motta} and Arantes, {M{\'a}rcio da Silva} and Hossomi, {Marcelo Yukio Bressan} and Fran{\cc}a, {Paulo Morelato} and Kerem Akartunali",
year = "2015",
month = "10",
doi = "10.1007/s10732-015-9295-0",
language = "English",
volume = "21",
pages = "687--717",
journal = "Journal of Heuristics",
issn = "1381-1231",
number = "5",

}

A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems. / Toledo, Claudio Fabiano Motta; Arantes, Márcio da Silva; Hossomi, Marcelo Yukio Bressan; França, Paulo Morelato; Akartunali, Kerem.

In: Journal of Heuristics, Vol. 21, No. 5, 10.2015, p. 687-717.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Toledo, Claudio Fabiano Motta

AU - Arantes, Márcio da Silva

AU - Hossomi, Marcelo Yukio Bressan

AU - França, Paulo Morelato

AU - Akartunali, Kerem

PY - 2015/10

Y1 - 2015/10

N2 - 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.

AB - 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.

KW - lot-sizing

KW - heuristics

KW - relax-and-fix

KW - fix-and-optimize

KW - backlogging

UR - http://personal.strath.ac.uk/kerem.akartunali/

UR - http://link.springer.com/article/10.1007/s10732-015-9295-0

U2 - 10.1007/s10732-015-9295-0

DO - 10.1007/s10732-015-9295-0

M3 - Article

VL - 21

SP - 687

EP - 717

JO - Journal of Heuristics

T2 - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 5

ER -