UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times

De Araujo, SA; De Reyck, B; Degraeve, Z; Fragkos, I; Jans, R; (2015) Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times. INFORMS Journal on Computing , 27 (3) pp. 431-448. 10.1287/ijoc.2014.0636. Green open access

[thumbnail of De_Reyck.INFORMS_JoC_Paper-2.pdf] Text
De_Reyck.INFORMS_JoC_Paper-2.pdf
Available under License : See the attached licence file.

Download (1MB)

Abstract

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 state-of-the-art approaches found in the literature. Finally, we design a branch-and-price-based heuristic and report computational results. The heuristic scheme compares favorably or outperforms other approaches.

Type: Article
Title: Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times
Open access status: An open access version is available from UCL Discovery
DOI: 10.1287/ijoc.2014.0636
Publisher version: http://dx.doi.org/10.1287/ijoc.2014.0636
Language: English
Keywords: lot sizing; column generation; Lagrange relaxation; branch and price; heuristics
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > UCL School of Management
URI: https://discovery.ucl.ac.uk/id/eprint/1456213
Downloads since deposit
205Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item