Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials

Mingyuan Wei, Mingyao Qi, Tao Wu and Canrong Zhang

European Journal of Operational Research, 2019, vol. 277, issue 2, 521-541

Abstract: This study examines the multi-level capacitated lot-sizing problems with a special focus on item replaceability. Two linear programming models are established using different variable definitions and the McCormick envelope. These are further strengthened using some valid inequalities. In large-scale instances, the problem becomes computationally difficult to solve because of its non-deterministic polynomial-time hardness. Therefore, a matching-induced search algorithm to solve the problem is proposed. The algorithm leverages the matching between the rounded relaxation and the incumbent solution values to fix a few binary variables. It also applies the relax-and-fix heuristic to solve the reduced-size problems and progressively improve solution quality. The algorithm is further enhanced by using both the matching information of historical feasible solution values and the distance between the relaxation and incumbent solution values. Extensive computational experiments are conducted to test the efficiency of the models and algorithms. Experimental results show that increasing the number of substitutable items on the bill of materials (BOM) or increasing the overlapping ratios among the BOMs, or both, can effectively reduce the total cost. The proposed enhanced algorithm can perform better than the relax-and-fix and some other heuristics in the literature.

Keywords: Lot-sizing; Replaceable BOM; Production planning; Heuristics; Relax-and-fix (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719302231
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:277:y:2019:i:2:p:521-541

DOI: 10.1016/j.ejor.2019.03.001

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().