1. Introduction

In this paper, we consider a single period, multi-product, stochastic inventory problem with substitution and setup costs. We allow a one-way downward substitution structure in that demand for product j may be satisfied only by using stock of those products i with i [less than or equal to] j. This downward substitution structure occurs in several practical settings such as semiconductor chips (see Hsu and Bassok, 1999) where a faster processor can be substituted for a slower processor, memory chips (Leachman, 1987) and in the steel industry (Wagner and Whitin,

1958). Our motivation for studying this problem came from alternative modes of customization tried at IBM. Swaminathan and Tayur (1998) considered one of the alternatives which involved storing semi-finished inventory called vanilla boxes and then customizing the product after receiving the order. Another approach involved storing inventory of cadillac boxes which contain all (or most of) the features and then removing features (or giving them free) based on the actual demand realized. This latter approach corresponds to a multi-product inventory problem with downward substitution and setup costs under stochastic demand. The setup costs represent product-specific tooling and equipment costs for production or testing and managerial effort for handling the increased product variety.

In this paper, we present a model, properties and an effective solution methodology that exploits the problem structure and utilizes a combination of optimization techniques including network flows, dynamic programming and infinitesimal perturbation analysis. We also obtain qualitative and managerially relevant insights through a computational study. We focus on a single period problem corresponding to short (fast) cycle products. However, our approach may be applied to a multi-period problem in which the product set selection decision is made once at the beginning and cannot be revised later. In our model, there are N products and each product has a continuous stochastic non-negative demand with finite mean. Costs include setups, production, overage, stockout and substitution. There are three sets of decisions:

D1: which products to produce;

D2: how much to produce; and

D3: how to allocate products to satisfy realized demand.

Different versions of the substitution problem have been studied in the past (see literature review in Section 2). However, to the best of our knowledge, none of the earlier work has considered multiple (more than two) products, stochastic demand, setup costs and product substitution in an integrated model. As shown in Herer and Rashit (1997), even for a two product problem with setup costs, it is not easy to characterize the optimal regions of initial inventory values for which no products, both products or only one product is produced. Hence, we focus on developing fast and effective heuristic solution methodologies for the multi-product problem.