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

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]