Exact methods for single-item capacitated lot sizing problem with alternative machines and piece-wise linear production costs

Ayse Akbalik and Bernard Penz

International Journal of Production Economics, 2009, vol. 119, issue 2, 367-379

Abstract: In this paper, we study a special case of the capacitated lot sizing problem (CLSP), where alternative machines are used for the production of a single-item. The production cost on each machine is assumed to be piece-wise linear with discontinuous steps (step-wise costs). The over-produced finished products can be stored in an unlimited storage space to satisfy future demand. The aim is to achieve optimal production planning without backlogging. This problem can be seen as an integration of production and transportation activities in a multi-plant supply chain structure, where finished goods are sent directly from the plants to the distribution center using capacitated vehicles. For this problem, which we show to be NP-hard, we propose an exact pseudo-polynomial dynamic programming algorithm which makes it NP-hard in the ordinary sense. We also give three mixed integer linear programming (MILP) formulations that we have found in the literature for the simplest case of the CLSP. These formulations are adapted to the multi-machine case with a step-wise cost structure, to which some valid inequalities have been added to improve their efficiency. We then compare the computational time of the dynamic program to that of one MILP which we selected among MILP formulations based on its lower computational time and its lower and upper bound quality.

Keywords: Single-item; capacitated; lot; sizing; problem; Alternative; machines; Step-wise; production; costs; Dynamic; programming; Mixed; integer; linear; programming (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925-5273(09)00090-5
Full text for ScienceDirect subscribers only

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:eee:proeco:v:119:y:2009:i:2:p:367-379

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().