Files in this item

FilesDescriptionFormat

application/pdf

application/pdfDATE-DISSERTATION-2016.pdf (7MB)
(no description provided)PDF

Description

Title:Theoretical and computational advances in finite-size facility placement and assignment problems
Author(s):Date, Ketan Hemant
Director of Research:Nagi, Rakesh
Doctoral Committee Chair(s):Nagi, Rakesh
Doctoral Committee Member(s):Chen, Xin; Jacobson, Sheldon; Sreenivas, Ramavarapu
Department / Program:Industrial&Enterprise Sys Eng
Discipline:Industrial Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Facility location
Finite size facility
Dominance
High performance computing (HPC)
Graphics processing units (GPU)
Compute unified device architecture (CUDA)
Linear Assignment Problem
Quadratic Assignment Problem
Abstract:The goal of this research is to develop fundamental theory and exact solution methods for the optimal placement of multiple, finite-size, rectangular facilities in presence of existing rectangular facilities, in a plane. Applications of this research can be found in facility layout (re)design in manufacturing, distribution systems, services (retail outlets, hospital floors, etc.), and printed circuit board design; where designing an efficient layout can save millions of dollars in operational costs. Main difficulty of this optimization problem lies in its continuous non-convex/non-concave feasible space, which makes it tough to escape local optimality. Through this research, novel approaches will be proposed which can be used to distill this continuous space into a finite set of candidate solutions, making it amenable to search for the global optimum. The first two parts of this research deal with establishing a unified theory for the finite-size facility placement problem and establishing the theory of dominance for pruning the sub-optimal solutions. Traditionally, the facility location/layout problems are modeled as the Quadratic Assignment Problem (QAP), which is strongly NP-hard. Also, for getting strong lower bounds in the dominance procedure, we may need to solve an instance of the NP-hard Quadratic Semi-Assignment Problem (QSAP). To this end, the third part of this research deals with investigating parallel and High Performance Computing (HPC) methods for solving the Linear Assignment Problem (LAP), which is an important sub-problem of the QAP. The final part of this research deals with investigating parallel and HPC methods for obtaining strong lower bounds and possibly solving large QAPs. Since QAP is known to be a computationally intensive problem, it should be noted that large in this context means problem instances with up to 30 facilities and locations.
Issue Date:2016-11-28
Type:Thesis
URI:http://hdl.handle.net/2142/95355
Rights Information:Copyright 2016 Ketan Hemant Date
Date Available in IDEALS:2017-03-01
Date Deposited:2016-12


This item appears in the following Collection(s)

Item Statistics