Back to search

Georgia Institute of Technology

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

Abstract

dc:description.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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Siebert Sandoval, Matias Ignacio
Advisors dc:contributor.advisor
  • Ahmed, Shabbir
  • Nemhauser, George L.
Committee members dc:contributor.committeemember
  • Garcia, Renan
  • Singh, Mohit
  • Toriello, Alejandro

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/62735

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Siebert Sandoval, Matias Ignacio. Topics in network optimization: The Steiner tree problem and semiconductor manufacturing. Doctoral thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/62735