Economic lot-sizing problem with remanufacturing option: complexity and algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

4 Citations (Scopus)


In a single item dynamic lot-sizing problem, we are given a time horizon and demand for a single item in every time period. The problem seeks a solution that determines how much to produce and carry at each time period, so that we will incur the least amount of production and inventory cost. When the remanufacturing option is included, the input comprises of number of returned products at each time period that can be potentially remanufactured to satisfy the demands, where remanufacturing and inventory costs are applicable. For this problem, we first show that it cannot have a fully polynomial time approximation scheme (FPTAS). We then provide a pseudo-polynomial algorithm to solve the problem and show how this algorithm can be adapted to solve it in polynomial time, when we make certain realistic assumptions on the cost structure. We finally give a computational study for the capacitated version of the problem and provide some valid inequalities and computational results that indicate that they significantly improve the lower bound for a certain class of instances.
Original languageEnglish
Title of host publicationMachine Learning, Optimization, and Big Data
Subtitle of host publicationSecond International Workshop, MOD 2016, Volterra, Italy, August 26-29, 2016, Revised Selected Papers
EditorsPanos M. Pardalos, Piero Conca, Giovanni Giuffrida, Giuseppe Nicosia
Place of PublicationCham, Switzerland
Number of pages12
ISBN (Print)9783319514680, 9783319514697
Publication statusPublished - 25 Dec 2016


  • lot-sizing problem
  • production cost
  • inventory cost
  • polynomial time


Dive into the research topics of 'Economic lot-sizing problem with remanufacturing option: complexity and algorithms'. Together they form a unique fingerprint.

Cite this