Theoretical and computational advances in finite-size facility placement and assignment problems

Date, Ketan Hemant

Permalink

https://hdl.handle.net/2142/95355 Copy

Description

Title

Theoretical and computational advances in finite-size facility placement and assignment problems

Author(s)

Date, Ketan Hemant

Issue Date

2016-11-28

Director of Research (if dissertation) or Advisor (if thesis)

Nagi, Rakesh

Doctoral Committee Chair(s)

Nagi, Rakesh

Committee Member(s)

• Chen, Xin
• Jacobson, Sheldon
• Sreenivas, Ramavarapu

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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.

Graduation Semester

2016-12

Type of Resource

text

Permalink

http://hdl.handle.net/2142/95355

Copyright and License Information

Copyright 2016 Ketan Hemant Date

Owning Collections