A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem

Cathy Wolosewicz, Stéphane Dauzère-Pérès and Riad Aggoune

European Journal of Operational Research, 2015, vol. 244, issue 1, 3-12

Abstract: This paper presents a novel approach for solving an integrated production planning and scheduling problem. In theory as well as in practice, because of their complexity, these two decision levels are most of the time treated sequentially. Scheduling largely depends on the production quantities (lot sizes) computed at the production planning level and ignoring scheduling constraints in planning leads to inconsistent decisions. Integrating production planning and scheduling is therefore important for efficiently managing operations. An integrated model and an iterative solution procedure were proposed in earlier research papers: The approach has limitations, in particular when solving the planning problem. In this paper, a new formulation is proposed to determine a feasible optimal production plan, i.e. lot sizes, for a fixed sequence of operations on the machines when setup costs and times are taken into account. Capacity constraints correspond to paths of the conjunctive graph associated to the sequence. An original Lagrangian relaxation approach is proposed to solve this NP-hard problem. A lower bound is derived and an upper bound is calculated using a novel constructive heuristic. The quality of the approach is tested on numerous problem instances.

Keywords: Production planning; Lot sizing; Scheduling; Lagrangian relaxation; Heuristic (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715000545
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:ejores:v:244:y:2015:i:1:p:3-12

DOI: 10.1016/j.ejor.2015.01.034

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().