A matheuristic approach for the multi-level capacitated lot-sizing problem with substitution and backorder

Abstract

The lot-sizing problem aims at determining the products to be produced and their quantities for each time period, which is a difficult problem in production planning. This problem becomes even more complicated when practical aspects such as limited production capacity, bill of materials, and item substitution are considered. In this paper, we study a new variant of the lot-sizing problem, called the multi-level capacitated lot-sizing problem with substitution and backorder. Unlike previous studies, this variant considers substitutions at both the product and component levels, which is based on the real needs of manufacturers to increase planning flexibility. Backorders are allowed, but should be delivered within a certain time limitation. We formulate this problem using a mathematical programming model. A matheuristic approach is proposed to solve the problem. This first generates an initial feasible solution using a relax-and-fix algorithm, and then improves it using a hybrid fix-and-optimise algorithm. The proposed algorithm is calibrated with a full factorial design of experiments, and its efficiency is well validated. Finally, through extensive numerical experiments, we analyse the properties of this new lot-sizing problem, such as the effect of substitution options, and the influence of backorder time limitation, and provide several useful managerial insights for manufacturing companies to save costs in production planning.

KEYWORDS:

• Lot-sizing problem
• substitution
• backorder
• matheuristic
• fix-and-optimise
• relax-and-fix

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The instance data that used in this paper are openly available in https://github.com/ZhuangHaoCheng/MLCLSPSB_Instance.

Additional information

Funding

This research was partially supported by the National Key R&D Program of China [grant number 2018YFB1700600], National Natural Science Foundation of China [grant number 71971090,71821001], Shanghai Pujiang Program [grant number 21PJ1413300], and the Tongji University Fundamental Research Funds for the Central Universities.

Notes on contributors

Hu Qin

Hu Qin received the Ph.D. degree from the City University of Hong Kong, Hong Kong, in 2011. He is currently a Professor with the School of Management, Huazhong University of Science and Technology. His current research interests are in the fields of algorithms and artificial intelligence, including various topics in operations research, such as vehicle routeing problem, freight allocation problem, container loading problems, and transportation problems.

Haocheng Zhuang

Haocheng Zhuang received B.S. degree from School of Management, Huazhong University of Science and Technology, Wuhan, China, 2020. He is currently pursuing the Ph.D. degree with the School of Management, Huazhong University of Science and Technology. His work focuses on the combinatorial optimisation problems in the production and logistics.

Chunlong Yu

Chunlong Yu is an Assistant Professor in the school of mechanical engineering at Tongji University, Shanghai, China. He received a B.Sc. degree from Tongji University, a M.Sc. and a Ph.D. degree from Politecnico di Milano, Milan, Italy. His current research interests are in production planning and scheduling, simulation optimisation, and data-driven modelling of manufacturing systems.

Jiliu Li

Jiliu Li is a Professor with the school of management, Northwestern Polytechnical University, China. He received a B.Sc. in mechanical design, manufacture and automation, a Ph.D. in management science and engineering. His current research interests are in transportation systems design and management, exact algorithm design and analysis, logistics optimisation, operations research. He is the author and co-author of some journal articles in these fields, such as journals IJOC, TS, TRB, and CIE.