Genetic algorithm based hybrid approaches to solve the capacitated lot sizing problem with setup carryover and backordering

Lot sizing studies aim at determining the periods where production takes place and the quantities to be produced in order to satisfy the customer demand while minimizing the total cost. Having an important impact on the efficiency of production and inventory systems, lot sizing problem is one of the most challenging production planning problems. Due to their applications in production planning, lot sizing problems have been studied for many years with different features. Among these problems, The Capacitated Lot Sizing Problem (CLSP) has received a lot of attention from researchers. The primary aim of this Ph.D. study is to propose novel Genetic Algorithm (GA) based hybrid approaches for solving the CLSP with three extensions, i.e. setup times, setup carryover and backordering. In this thesis, the capacitated lot sizing problem with setup carryover and backordering is solved in two stages. In the first stage, two novel hybrid approaches are proposed for solving the capacitated lot sizing problem with setup times and setup carryover (CLSPC). These two hybrid approaches combine a meta-heuristic, i.e. GA, with a Mixed Integer Programming (MIP) based heuristic, i.e. the Fix-and-Optimize heuristic, in two different ways. In the first methodology, i.e. sequential hybridization, the Fix-and-Optimize heuristic is performed after the GA. The second methodology involves a different hybridization scheme where the Fix-and-Optimize heuristic is embedded into the GA. As an alternative to a random initial population, a novel initialization scheme which consists of problem specific information and randomness is proposed. Moreover, in order to sustain the feasibility during the search of GA, several repair operators are proposed. Lastly, the performances of proposed hybrid approaches are evaluated on various sets of problems from published literature. In the second stage, the CLSPC is extended to include the backorder option, called capacitated lot sizing problem with setup carryover and backordering. For solving the capacitated lot sizing problem with setup carryover and backordering, eight hybrid approaches are proposed. These approaches are modified versions of the hybrid approaches developed for solving the CLSPC. Unlike the hybrid approaches proposed in the first stage, in these hybrid approaches, the Fix-and-Optimize heuristic is implemented with different decomposition schemes. An extensive experimental analysis is carried out to compare the performances of the proposed hybrid approaches to the pure GAs using various problem instances. Moreover, the robustness of the performances of the proposed approaches under different parameter values is examined.