IFORS2014

A MIP-Based Dual Bounding Technique for the Irregular Nesting Problem

Invited abstract in session HA-21: Cutting and Packing 1, stream Cutting and Packing.

Area: 20. Production Management & Supply Chain Management

Thursday, 8:30-10:00
Room: Room 006

Authors (first author is the speaker)

1. Ryan J. O'Neil
Department of Systems Engineering and Operations Research, George Mason University
2. Karla Hoffman
Department of Systems Engineering and Operations Research, George Mason University

Abstract

Optimal placement of irregular shapes with no overlap in a minimized bounding box is a common manufacturing problem. Exact techniques solve this problem using Integer Programs built from geometric data of the shape pairs. These models use constraints based on the No-Fit Polygon to eliminate overlap, but convergence time can be excessive, due to loose primal-dual bounds. We present a new technique to compute dual bounds by allowing small amounts of overlap. This uses fewer binary variables than NFP-based models and can be used iteratively to find optimal layouts.

Keywords

Status: accepted


Back to the list of papers