A simulated annealing algorithm with neighbourhood list for capacitated dynamic lot-sizing problem with returns and hybrid products

This research addresses the capacitated dynamic lot-sizing problem with returns and hybrid products (CLSP^RH.). The problem is to identify how many of each product type to produce during each period for a hybrid system with manufacturing capacity constraints. The objective of CLSP^RH is to maximise total profit of the production system that consists of new, remanufactured and hybrid products. CLSP^RH is a multi-period CLSP, which is modelled as a mixed-integer nonlinear programming problem. The traditional CLSP is NP-hard, and the nonlinearity of CLSP^RH makes the problem even harder to solve. Therefore, a Simulated Annealing (SA) algorithm with a neighbourhood list (SA_NL) is proposed. By using a list of several neighbourhoods, the SA algorithm is improved. SA_NL is compared to SA, three variants of Genetic Algorithm (GA) and a Variable Neighbourhood Search (VNS) algorithm. The variants of GA are GA with one-point crossover (GA_OP), GA with two-point crossover (GA_TP) and GA with one-point period-based crossover (GA_OPPB). Over all instances, the results show that the proposed SA_NL outperforms SA, VNS, GA_OP, GA_TP and GA_OPPB by 0.54%, 0.34%, 1.92%, 1.78% and 2.92%, respectively.