We address a variant of the Joint Replenishment Problem, in which the products can only be produced in fixed proportions to each other. Such problems occur commonly in the manufacture of sheet metal and die-cast parts and some chemical products. We call it the Strong Interaction Problem (SIP). The general instance of the problem is NP-complete while single nest instances are polynomially solvable. We establish the boundary at which the problem becomes hard. We also present an exact algorithm for solving the problem using a variable redefinition approach. Computational testing on randomly generated problems indicates that our algorithm is several orders of magnitude faster than solution of the problems without reformulation using existing algorithms and commercial software.
|Original language||English (US)|
|Number of pages||14|
|Journal||IIE Transactions (Institute of Industrial Engineers)|
|State||Published - Jan 1 2001|
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering