Date of Award

5-2012

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science

Advisor

Shier, Douglas R

Committee Member

Adams , Warren P

Committee Member

Dean , Brian C

Committee Member

Warner , Daniel D

Abstract

We investigate several geometric packing problems (derived from an industrial setting) that involve fitting patterns of regularly spaced disks without overlap. We first derive conditions for achieving the feasible placement of a given set of patterns and construct a network formulation that, under certain conditions, allows the calculation of such a placement. We then discuss certain related optimization problems (e.g., fitting together the maximum number of patterns) and broaden the field of application by showing a connection to the well-known Periodic Scheduling Problem. In addition, a variety of heuristics are developed for solving large-scale instances of these provably difficult packing problems. The results of extensive computational testing, conducted on these heuristics, are presented.

Share

COinS