Economics at your fingertips  

Energy-aware lot sizing problem: Complexity analysis and exact algorithms

Christophe Rapine, Guillaume Goisque and Ayse Akbalik

International Journal of Production Economics, 2018, vol. 203, issue C, 254-263

Abstract: The single-item lot sizing problem under a periodic energy limitation is considered in this paper. Identical and parallel capacitated machines constitute the production system, each one consuming a certain amount of energy when being switched on, when reserved, and when producing. We consider a cost for starting-up the machines, a reservation cost to keep the machines ready for production, in addition to classical lot sizing costs, such as, joint setup cost, unit production cost and unit holding cost, all being time-dependent. Besides the classical lot sizing decisions of how much and in which periods to produce, we have to decide the number of machines to switch on and to switch off in each period. We show that this problem is NP-hard even under restricted conditions. In contrast, assuming stationary energy parameters, we propose two polynomial time dynamic programming algorithms to solve the problem to optimality. The first algorithm is proposed for the case with null setup cost, null reservation cost and null reservation energy consumption, and runs in O(M5T4) time, with M being the number of machines and T the number of periods. We show that we can extend this algorithm to solve the generalized version of the problem in time complexity O(M6T6).

Keywords: Lot sizing problem; Energy; Capacitated parallel machines; Polynomial time algorithm; Complexity (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed

Downloads: (external link)
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:

Access Statistics for this article

International Journal of Production Economics is currently edited by R. W. Grubbström

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

Page updated 2018-11-10
Handle: RePEc:eee:proeco:v:203:y:2018:i:c:p:254-263