Physical Sciences and Mathematics Commons^™

An Optimization Approach To A Geometric Packing Problem, Bradley Paynter

All Dissertations

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 …