Business Commons^™

Period Decompositions For The Capacitated Lot Size Problem With Setup Times, Silvio Alexandre De Araujo, Bert De Reyck, Zeger Degraeve, Ioannis Fragkos, Raf Jans

Research Collection Lee Kong Chian School Of Business

We study the multi-item capacitated lot sizing problem with setup times. Based on two strong reformulations of the problem, we present a transformed reformulation and valid inequalities that speed up column generation and Lagrange relaxation. We demonstrate computationally how both ideas enhance the performance of our algorithm and show theoretically how they are related to dual space reduction techniques. We compare several solution methods and propose a new efficient hybrid scheme that combines column generation and Lagrange relaxation in a novel way. Computational experiments show that the proposed solution method for finding lower bounds is competitive with textbook approaches and …