Self-adaptive randomized constructive heuristics for the multi-item capacitated lot-sizing problem

Lai, David, Li, Yijun, Demir, Emrah ORCID: https://orcid.org/0000-0002-4726-2556, Dellaert, Nico P. and van Woensel, Tom 2022. Self-adaptive randomized constructive heuristics for the multi-item capacitated lot-sizing problem. Computers and Operations Research 147 , 105928. 10.1016/j.cor.2022.105928

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (837kB)

Abstract

The Capacitated Lot-Sizing Problem (CLSP) and its variants are important and challenging optimization problems. Constructive heuristics are known to be the most intuitive and fastest methods for finding good feasible solutions for the CLSPs and therefore are often used as a subroutine in building more sophisticated exact or metaheuristic approaches. Classical constructive heuristics, such as period-by-period heuristics and lot elimination heuristics, are widely used by researchers. This paper introduces four perturbation strategies to the period-by-period and lot elimination heuristics to further improve the solution quality. We propose a new procedure to automatically adjust the parameters of the randomized period-by-period (RPP) heuristics. The procedure is proved to offer better solutions with reduced computation times by improving time-consuming parameter tuning phase. Combinations of the self-adaptive RPP heuristics with Tabu search and lot elimination heuristics are tested to be effective. Computational experiments provided high-quality solutions with a 0.88% average optimality gap on benchmark instances of 12 periods and 12 items, and an optimality gap within 1.2% for the instances with 24 periods and 24 items.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Business (Including Economics)
Publisher:	Elsevier
ISSN:	0305-0548
Date of First Compliant Deposit:	27 June 2022
Date of Acceptance:	20 June 2022
Last Modified:	28 Dec 2023 16:45
URI:	https://orca.cardiff.ac.uk/id/eprint/150805

Actions (repository staff only)

Edit Item