Lot-Sizing with Start-Up Times

François Vanderbeck
Additional contact information
François Vanderbeck: Cambridge University, Engineering Department and Judge Institute of Management Studies, Trumpington St., Cambridge CB2 1AG, United Kingdom

Management Science, 1998, vol. 44, issue 10, 1409-1425

Abstract: Many practical applications of lot-sizing and scheduling problems involve start-up times. Operations research literature contains but few studies of lot-sizing models that take start-up times explicitly into account. Here, we review some of these studies, discuss the models and their complexity, and we propose further models. We consider in particular a single-stage single-mode multi-item lot-sizing model with continuous set-ups and sequence independent start-up times, which we solve using an integer programming column generation algorithm and we develop a dynamic programming procedure for the single-item subproblem that treats the initial stock as a decision variable. We also use cutting planes developed by Constantino for the multi-item polyhedra. By combining column and cut generation, the lower bounds that we obtain before branching are on average less than 2% from an optimal solution. Our algorithm solves instances with 3 to 5 items and 24 periods in an average of 50 seconds on a modern workstation, and problems with 36 periods in an average of 750 seconds. Solutions guaranteed to be within 2% of optimality are obtained in less than 75% of these times.

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.10.1409 (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:44:y:1998:i:10:p:1409-1425

Access Statistics for this article

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