Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

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

Toledo, Claudio Fabiano Motta and Arantes, Márcio da Silva and Hossomi, Marcelo Yukio Bressan and França, Paulo Morelato and Akartunali, Kerem (2015) A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems. Journal of Heuristics, 21 (5). pp. 687-717. ISSN 1572-9397

Text (Toledo-etal-JOH-2015-A-relax-and-fix-with-fix-and-optimize-heuristic-applied-to-multi-level)
Toledo_etal_JOH_2015_A_relax_and_fix_with_fix_and_optimize_heuristic_applied_to_multi_level.pdf - Accepted Author Manuscript

Download (2MB) | Preview


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.