Lot sizing problems with strong set-up interactions

Curtis L. Stowers, Udatta S Palekar

Research output: Contribution to journalArticlepeer-review


We address the problem of coordinated replenishment of products when the products can be produced only in fixed proportion to each other. Such problems commonly arise in the manufacture of sheet/plate metal parts or die-cast parts. The problem is a variant of the well-known Joint Replenishment Problem. We call this problem the Strong Interaction Problem (SIP). After giving a mathematical formulation of the problem, we show that the general problem is NP-hard. An important variant of the problem, in which products are unique to a family, is shown to be polynomially solvable. We present several lower bounds, an exact algorithm and a heuristic for the problem. Computational testing on randomly generated problems suggests that our exact algorithm performs very well when compared with a commercially available integer programming solver. The heuristic method also gives good solutions.

Original languageEnglish (US)
Pages (from-to)167-179
Number of pages13
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number2
StatePublished - 1997

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Lot sizing problems with strong set-up interactions'. Together they form a unique fingerprint.

Cite this