Reformulation, linearization, and a hybrid iterated local search algorithm for economic lot-sizing and sequencing in hybrid flow shop problems

Abstract We study an integrated economic lot-sizing and sequencing problem (ELSP) in the hybrid flow shop manufacturing setting with unlimited intermediate buffers in a finite planning horizon. The ELSP entails making two simultaneous decisions regarding (i) the manufacturing sequences of products, and (ii) their production quantity. The objective is to minimize the total cost, consisting of inventory holding and set-up costs. To solve this problem, we first develop a novel mixed-integer nonlinear programming (MINLP) model that improves an existing MINLP model in the literature. We then present a novel linearization technique that transforms these two MINLP models into effective mixed-integer linear programming (MILP) models. Additionally, we develop an effective algorithm that hybridizes the iterated local search algorithm with an approximate function. We conduct comprehensive experiments to compare the performance of MILPs+CPLEX with that of MINLPs+BARON. Additionally, our proposed algorithm is compared with four existing metaheuristic algorithms in the literature. Computational results demonstrate that our novel MINLP formulation and its linearized variant significantly improve the solvability and optimality gap of an existing MINLP formulation and its linearized variant. We also show that our new hybrid iterated local search algorithm substantially improves computational performance and optimality gap of the mathematical models and the existing algorithms in the literature, on large-size instances of the problem.