A Dual Ascent and Column Generation Heuristic for the Discrete Lotsizing and Scheduling Problem with Setup Times

Dirk Cattrysse, Marc Salomon, Roelof Kuik and Luk N. Van Wassenhove
Additional contact information
Dirk Cattrysse: Katholieke Universiteit Leuven, IB, Celestijnenlaan 300A, B-3001 Leuven-Heverlee, Belgium
Marc Salomon: Rotterdam School of Management, Erasmus University, P.O. Box 1738, NL-3000 DR Rotterdam, The Netherlands
Roelof Kuik: Rotterdam School of Management, Erasmus University, P.O. Box 1738, NL-3000 DR Rotterdam, The Netherlands
Luk N. Van Wassenhove: INSEAD, Boulevard de Constance, F-17305 Fontainebleau Cedex, France

Management Science, 1993, vol. 39, issue 4, 477-486

Abstract: In this paper the Discrete Lotsizing and Scheduling Problem (DLSP) with setup times is considered. DLSP is the problem of determining the sequence and size of production batches for multiple items on a single machine. The objective is to find a minimal cost production schedule such that dynamic demand is fulfilled without backlogging. DLSP is formulated as a Set Partitioning Problem (SPP). We present a dual ascent and column generation heuristic to solve SPP. The quality of the solutions can be measured, since the heuristic generates lower and upper bounds. Computational results on a personal computer show that the heuristic is rather effective, both in terms of quality of the solutions as well as in terms of required memory and computation time.

Keywords: column generation; heuristics; set partitioning; lotsizing with setup times (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (35)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.39.4.477 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:39:y:1993:i:4:p:477-486

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().