A polyhedral approach to a production planning problem

Miguel Constantino

Annals of Operations Research, 2000, vol. 96, issue 1, 75-95

Abstract: Production planning in manufacturing industries is concerned with the determination of the production quantities (lot sizes) of some items over a time horizon, in order to satisfy the demand with minimum cost, subject to some production constraints. In general, production planning problems become harder when different types of constraints are present, such as capacity constraints, minimum lot sizes, changeover times, among others. Models incorporating some of these constraints yield, in general, NP-hard problems. We consider a single-machine, multi-item lot-sizing problem, with those difficult characteristics. There is a natural mixed integer programming formulation for this problem. However, the bounds given by linear relaxation are in general weak, so solving this problem by LP based branch and bound is inefficient. In order to improve the LP bounds, we strengthen the formulation by adding cutting planes. Several families of valid inequalities for the set of feasible solutions are derived, and the corresponding separation problems are addressed. The result is a branch and cut algorithm, which is able to solve some real life instances with 5 items and up to 36 periods. Copyright Kluwer Academic Publishers 2000

Keywords: production planning; valid inequalities; cutting plane algorithm (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018963805173 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:96:y:2000:i:1:p:75-95:10.1023/a:1018963805173

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018963805173

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().