Three essays on resource allocation problems: Inventory management in assemble-to-order systems and online assignment of flexible resources.

摘要

This dissertation addresses two multiple resource allocation problems in operations management: an inventory management problem in an assemble-to-order (ATO) manufacturing system and a dynamic resource allocation problem. The first essay considers a multi-component, multi-product (ATO) system that uses an independent base-stock policy for inventory replenishment. We formulate a two-stage stochastic integer program with recourse to determine the optimal base-stock policy and the optimal component allocation policy for the system. We show that the component allocation problem is a general multidimensional knapsack problem (MDKP) and is NP-hard. Therefore we propose a simple, order-based component allocation rule. Intensive testing indicates that our rule is robust, effective, and that it significantly outperforms existing methods. We use the sample average approximation method to determine the optimal base-stock levels. In the second essay, we exclusively concentrate on the component allocation rule proposed for the ATO system, and study its analytical properties and computational effectiveness. Although our heuristic is primarily intended for the general MDKP, it is remarkably effective also for the 0–1 MDKP. The heuristic uses the effective capacity, defined as the maximum number of copies of an item that can be accepted if the entire knapsack were to be used for that item alone, as the criteria to make item selection decisions. Instead of incrementing or decrementing the value of each decision variable by one unit in each iteration, as other heuristics do, our heuristic adds decision variables to the solution in batches. This unique feature of the new heuristic over-comes the inherent computational inefficiency of other general MDKP heuristics for large-scale problems. Finally, in the third essay of the dissertation, we study a dynamic resource allocation problem, set up in a revenue management context. An important feature of our model is that the resources are flexible. Each customer order can potentially be satisfied using any one of the capable resources, and the resources differ in their level of flexibility to process different demand types. We focus on the acceptance decisions of customer demands, and the assignment decisions of resources to accepted demands. We model the revenue maximization problem as a stochastic dynamic program, which is computationally challenging to solve. Based on our insights gained from the analysis of special cases of the problem, we propose several approximate solutions; roll-out, threshold, newsboy and dynamic randomization heuristics. Through an extensive simulation study, we verify that these heuristics are indeed effective in solving the problem, and are near-optimal for many problem instances.