Title: A comparative study of hybrid approaches for solving capacitated lot sizing problem with setup carryover and backordering

Authors: Hacer Guner Goren; Semra Tunali

Addresses: Department of Industrial Engineering, Pamukkale University, Kinikli Campus, 20070, Denizli, Turkey ' Department of Business Administration, Izmir University of Economics, Sakarya Caddesi, No. 156, 35330, Balcova-Izmir, Turkey

Abstract: The classical capacitated lot sizing problem is shown to be NP-hard for even a single item problem. This study deals with an extended version of this problem with setup carryover and backordering. To solve this computationally difficult lot sizing problem, we propose a number of hybrid meta-heuristic approaches consisting of genetic algorithms and a mixed integer programming-based heuristic. This MIP-based heuristic is combined with two types of decomposition schemes (i.e., product and time decomposition) to generate subproblems. Computational experiments are carried out on various problem sizes. We found that hybrid approaches employing only time decomposition scheme or combination of both time and product decomposition schemes in different forms outperform the other hybrid approaches. Moreover, we investigated the sensitivity of the two best performing approaches to changes in problem-specific parameters including backorder costs, setup times, setup costs, capacity utilisation and demand variability. [Received 2 November 2015; Revised 25 March 2016; Accepted 7 April 2016]

Keywords: capacitated lot sizing problem; CLSP; setup carryover; backordering; hybrid approaches; sensitivity analysis; paired-t test; metaheuristics; genetic algorithms; mixed integer programming; MIP; backorder costs; setup times; setup costs; capacity utilisation; demand variability.

DOI: 10.1504/EJIE.2016.081019

European Journal of Industrial Engineering, 2016 Vol.10 No.6, pp.683 - 702

Available online: 14 Dec 2016 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article