| In this dissertation, we developed optimization models and algorithms for sourcing problems arising in supply chain management. We focused on problems in which a set of retailer demands needs to be assigned to either a set of production or storage facilities or a set of production resources in a dynamic environment. However, we first studied a much more general class of assignment problems (AP) in which we assume that the cost functions associated with assignments are separable in the agents, but otherwise arbitrary. We developed three solution methodologies for solving (AP), including a greedy heuristic, a very large-scale neighborhood search improvement algorithm, and a branch-and-price algorithm. We next studied three specific applications of (AP). In the first application, we considered the assignment of retailers to facilities over a discrete time horizon under dynamic demands and with a linear cost structure in the presence of constraints such as production capacity, throughput capacity, inventory capacity, and perishability. In the second application, we considered a continuous-time model in which the retailers face a constant demand rate, while each facility faces fixed-charge production costs. We derived a decreasing net revenue property that is satisfied by the optimal solution to (the linear relaxation of) an important subproblem, called the pricing problem, for a particular class of (AP). This class encompasses many variants of this application, including cases with production and inventory capacities, and cases with capacity expansion opportunities. In the third application we considered a manufacturer that has flexibility in meeting its demands, that is, each of its customers will accept product quantities within a specified range. We considered three different kinds of strategies, where we can stock raw materials only but produce just-in-time; stock only end products but acquire raw materials just-in-time; or stock both raw materials and end products. The pricing problem for this application is closely related to the so-called knapsack problem with expandable items, which we studied in detail and for which we developed new solution approaches. We performed extensive tests for all applications, and concluded that the developed heuristics usually produce very high quality solutions in limited time. |
