Topics in network optimization: The Steiner tree problem and semiconductor manufacturing

Abstract

This thesis covers two very different topics related to problems defined on graphs. The first is a fundamental graph optimization problem called the Steiner tree problem. The second is an applied problem in semiconductor manufacturing. In the first part of this thesis, we propose a new approach to solve the Steiner tree problem when the number of terminal nodes is fixed. The Steiner tree problem is a classical network design problem. We are given a graph G = (V,E), a set of terminal nodes R, subset of V, and a non-negative cost vector for the edges in E. The problem is to find the minimum weight tree in G that spans all nodes in R. We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is integral so that it can be solved as a linear program. However, the number of IPs grows exponentially with the number of terminals in the Steiner tree. As a consequence, we are able to solve the Steiner tree problem by solving a polynomial number of LPs, when the number of terminals is fixed. To address the latter issue, we propose a local-search based algorithm to solve the problem for big instances. First, we propose a dynamic programming algorithm to solve each IP efficiently. Then, we provide a characterization of the neighborhood of each IP. Finally, we propose a simulated annealing framework to solve the problem. We present computational results for a large set of instances in the SteinLib library, comparing our proposed approach with state-of-the-art algorithms to solve the directed version of the Steiner tree problem. We study over 800 instances from the SteinLib library, and we show that the solution quality of the proposed approach surpasses the quality of the solution of the state-of-the-art algorithms. In the second part of this thesis, we study the semiconductor manufacturing problem, which is a highly complex and dynamic re-entrant process where wafers go through several processing steps, entering the same group of machines multiple times. We propose a fluid model lot dispatching policy that iteratively optimizes lot selection based on current work-in-progress (WIP) distribution of the entire system. A fluid model is an approximation technique used to model and study the dynamics of a stochastic queuing network framework. Furthermore, we propose to split the decision policies into two phases in order to include travel time information into the dispatching and targeting decisions. We provide simulation results for a prototype facility that show that our proposed policies outperform commonly used dispatching rules in throughput, machine utilization, and machine target accuracy.