Resource constrained assignment problems with flexible customer demand

This dissertation considers classes of problems that seek to make profitable demand fulfillment decisions with limited available resources. This general problem scenario has been given much consideration over recent decades. In this work, we add to this body of research by considering less explored problem variants that allow decision makers to exploit demand flexibility to increase profit. We first consider a generalization of the capacitated facility location with single-sourcing constraints. Each customer must be assigned to a procured facility, and the level at which the customer's demand is fulfilled (a decision variable) must be determined, subject to falling within pre-specified limits. A customer's revenue is nondecreasing in its resource consumption, according to a general revenue function, and a fixed cost is incurred for each resource procured. We provide an exact branch-and-price algorithm that solves both this problem and a special case in which resource procurement is not considered. Our approach identifies an equally interesting class of pricing subproblems. We discuss how this class of problems can be solved with generalized revenue functions and offer efficient algorithms for solving instances with specially structured revenue functions that correspond to common pricing structures. Our extensive computational study compares the performance of our exact algorithm to that of well-known commercial solvers and demonstrates the advantages of our algorithmic approach for various categories of problem instances. Since real-world scenarios often result in large-scale problem sizes, we consider novel heuristic approaches for both the generalization of the capacitated facility location problem and a particular special case, which can be viewed as an extension of the well-known Generalized Assignment Problem (GAP). We first develop a class of heuristic solution methods for the variant without resource procurement decisions. Our approach is motivated by a rigorous study of the linear relaxation of the model. We show that our class of heuristics is asymptotic optimality in a probabilistic sense under a broad stochastic model. Improvement procedures are discussed and a thorough computational study confirms our theoretical results. We then provide fast and practically implementable optimization-based heuristic solution methods for the generalized class of facility location problems with resource procurement decisions. Our procedure is designed for very large-scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems. Finally, we consider a separate class of assignment problems with non-linear resource consumption and non-traditional capacity constraints. The model is applicable to manufacturing scenarios in which products with common production characteristics share setup times or some element of fixed resource consumption. The additional capacity constraints account for real-world restrictions that may result from environmental guidelines, transportation resource limitations, or limited warehouse storage space. We propose a branch-and-price algorithm for this class of problems that requires a unique reformulation of our problem, as well as a study of a new class of knapsack problems. A computational study demonstrates the appeal of our approach over commercial solvers for various problem instances.