The presence of substitution among multiple similar products plays an important role in inventory management. It has been observed in the literature that incorporating the impact of substitution among products can substantially improve the profit and reduce the understock or overstock risk. This thesis focuses on exploring and exploiting the impact of substitution on inventory management problems by theoretically analyzing mathematical models and developing efficient solution approaches. To that end, we address four problems. In the first problem, we study different pricing strategies and the role of substitution for new and remanufactured products. Our work presents a two-stage model for an original equipment manufacturer (OEM) in this regard. A closed-form one-to-one mapping of product designs onto the optimal product strategies is developed, which provides useful information for the retailer. Our second problem is a multi-product newsvendor problem with customer-driven demand substitution. We completely characterize the optimal order policy when the demand is known and reformulate this nonconvex problem as a binary quadratic program. When the demand is stochastic, we formulate the problem as a two-stage stochastic program with mixed integer recourse, derive several necessary optimality conditions, prove the submodularity of the profit function, develop polynomial-time approximation algorithms, and show their performance guarantees. Our numerical investigation demonstrates the effectiveness of the proposed algorithms and, furthermore, reveals several useful findings and managerial insights. In the third problem, we study a robust multi-product newsvendor model with substitution (R-MNMS), where both demand and substitution rates are uncertain and are subject to cardinality-constrained uncertainty set. We show that for given order quantities, computing the worst-case total profit, in general, is NP-hard, and therefore, address three special cases for which we provide closed-form solutions. In practice, placing an order might incur a fixed cost. Motivated by this fact, our fourth problem extends the R-MNMS by incorporating fixed cost (denoted as R-MNMSF) and develop efficient approaches for its solution. In particular, we propose an exact branch-and-cut algorithm to solve small- or medium-sized problem instances of the R-MNMSF, and for large-scale problem instances, we develop an approximation algorithm. We further study the effects of the fixed cost and show how to tune the parameters of the uncertainty set. / Doctor of Philosophy / In a multi-product supply chain, the substitution of products arises if a customer's first-choice product is out-of-stock, and she/he have to turn to buy another similar product. It has been shown in the literature that the presence of product substitution reduces the assortment size, and thus, brings in more profit. %and reduce the inventory level. However, how to quantitatively study and analyze substitution effects has not been addressed in the literature. This thesis fills this gap by developing and analyzing the profit model, and therefore, providing judicious decisions for the retailer to make in order to maximize their profit. In our first problem, we consider substitution between new products and remanufactured products. We provide closed-form solutions, and a mapping that can help the retailer in choosing optimal prices and end-of-life options given a certain product design. In our second problem, we study multi-product newsvendor model with substitution. We first show that, when the probability distribution of customers' demand is known, we can tightly approximate the proposed model as a stochastic integer program under discrete support. Next, we provide effective solution approaches to solve the multi-product newsvendor model with substitution. In practice, typically, there is a limited information available on the customers' demand or substitution rates, and therefore, for our third problem, we study a robust model with a cardinality uncertainty set to account for these stochastic demand and substitution rates. We give closed-form solutions for the following three special cases: (1) there are only two products, (2) there is no substitution among different products, and (3) the budget of uncertainty is equal to the number of products. Finally, similar to many inventory management problems, we include a fixed cost in the robust model and develop efficient approaches for its solution. The numerical study demonstrates the effectiveness of the proposed methods and the robustness of our model. We further illustrate the effects of the fixed cost and how to tune the parameters of the uncertainty set.

In this thesis, we study three applications of dynamic resource allocation: the first two consider dynamic lead-time quotation in make-to-order (MTO) systems with substitutable products and order cancellations, respectively; and the third application is a manpower allocation problem with job-teaming constraints. Matching supply and demand for manufacturing and service industries has been a fundamental focus of operations management literature, which concentrated on optimizing or improving supply-side decisions since demand has generally been assumed to be exogenously determined. However, recent business trends and advances in consumer behavior modeling have shown that demand for goods and services can clearly be shaped by various decisions that a firm makes, such as price and lead-time. In fact, competition between companies is no longer mainly based on price or product features; lead-time is one of the strategic measures to evaluate suppliers. In MTO manufacturing or service environments that aim to satisfy the customers' unique needs, lead-time quotation impacts the actual demand of the products and the overall profitability of the firm. In the first two parts of the thesis, we study the dynamic lead-time quotation problem in pure MTO (or service) systems characterized by lead-time sensitive Poisson demand and exponentially distributed service times. We formulate the problem as an infinite horizon Markov decision process (MDP) with the objective of maximizing the long-run expected average profit per unit time, where profits are defined to specifically account for delays in delivery of the customer orders. We study dynamic lead-time quotation problem in two particular settings; one setting with the possibility of demand substitution and another setting with order cancellations. The fundamental trade-off in lead-time quotation is between quoting short lead-times and attaining them. In case of demand substitution, i.e., in presence of substitutable products and multiple customer classes with different requirements and margins, this trade-off also includes capacity allocation and order acceptance decisions. In particular, one needs to decide whether to allocate capacity to a low-margin order now, or whether to reserve capacity for potential future arrivals of high-margin orders by considering customer preferences, the current workload in the system, and the future arrivals. In the case of order cancellations, one needs to take into account the probability of cancellation of orders currently in the system and quote lead-times accordingly; otherwise quotation of a longer lead-time may result in the loss of customer order, lower utilization of resources, and, in turn, reduced in profits. In Chapter 2, we study a dynamic lead-time quotation problem in a MTO system with two (partially) substitutable products and two classes of customers. Customers decide to place an order on one of the products or not to place an order, based on the quoted lead-times. We analyze the optimal profit and the structure of the optimal lead-time policy. We also compare the lead-time quotes and profits for different quotation strategies (static vs. dynamic) with or without substitution. Numerical results show that substitution and dynamic quotation have synergetic effects, and higher benefits can be obtained by dynamic quotation and/or substitution when difference in product revenues or arrival rates, or total traffic intensity are higher. In Chapter 3, we study a dynamic lead-time quotation problem in a MTO system with single product considering the order cancellations. The order cancellations can take place during the period that the order is being processed (either waiting or undergoing processing), or after the processing is completed, at the delivery to the customer. We analyze the behavior of optimal profit in terms of cancellation parameters. We show that the optimal profit does not necessarily decrease as cancellation rate increases through a numerical study. When the profit from a cancelled order, arrival rate of customers, or lead-time sensitivity of customers are high, there is a higher probability that optimal profit increases as cancellation rate increases. We also compare the cancellation scenarios with the corresponding no-cancellation scenarios, and show that there exists a cancellation scenario that is at least as good in terms of profit than a no-cancellation scenario for most of the parameter settings. In Chapter 4, we study the Manpower Allocation Problem with Job-Teaming Constraints with the objective of minimizing the total completion time of all tasks. The problem arises in various contexts where tasks require cooperation between workers: a team of individuals with varied expertise required in different locations in a business environment, surgeries requiring different composition of doctors and nurses in a hospital, a combination of technicians with individual skills needed in a service company. A set of tasks at random locations require a set of capabilities to be accomplished, and workers have unique capabilities that are required by several tasks. Tasks require synchronization of workers to be accomplished, hence workers arriving early at a task have to wait for other required workers to arrive in order to start processing. We present a mixed integer programming formulation, strengthen it by adding cuts and propose heuristic approaches. Experimental results are reported for low and high coordination levels, i.e., number of workers that are required to work simultaneously on a given task.