Volume 7, Issue 1 -
Spring/Summer 1999

Volume 6, Issue 3
Fall 1998

Volume 6, Issue 2
Spring/Summer 1998

Volume 6, Issue 1
Winter 1998

Volume 5, Issue 4
Fall 1997

Volume 5, Issue 3
Summer 1997

Volume 5, Issue 2
Spring 1997

Volume 5, Issue 1
Winter 1997

Volume 4, Issue 4
Fall 1996

Volume 4, Issue 3
Summer 1996

Volume 4, Issue 2
Spring 1996

Volume 4, Issue 1
Winter 1996

Volume 3, Issue 4
Fall 1995

Volume 3, Issue 3
Summer 1995

Volume 3, Issue 2
Spring 1995

Volume 3, Issue 1
January 1995

Volume 2, Issue 4
October 1994

Volume 2, Issue 3
July 1994

Volume 2, Issue 2
April 1994

Volume 2, Issue 1
January 1994

Volume 1, Issue 4
October 1993

Volume 1, Issue 3
July 1993

Volume 1, Issue 2
April 1993

Volume 1, Issue 1
January 1993

Boeing Scientists use CRPC Research for Just-in-time Manufacturing System

The multidirectional search algorithm, developed by John Dennis and Virginia Torczon (researchers in the CRPC's Optimization group), is now a key component of a new system for solving stock-cutting problems that arise at Boeing's Sheet Metal Center, located in Auburn, WA. Researchers at Boeing Computer Services were asked to develop new software to automate part nesting for just-in-time manufacturing. The 2NA nesting system that resulted uses CRPC-developed optimization technology to significantly reduce material and time required for part nesting.

To cut the thousands of different sheet-metal parts that go into the construction of an airplane, it is necessary to determine a template to describe the path that a tool makes as the part is cut. To minimize waste and expense, it is important to take the templates for a production run and arrange them on sheets of metal in as efficient a manner as possible. The problem of calculating a minimum-waste arrangement of cutting templates is known as the nesting problem.

The problem of finding an optimal configuration is in the class of NP- hard problems, so the researchers at Boeing resorted to heuristic techniques. They developed a two-stage nesting algorithm (hence the name "2NA") to arrive at a solution. The first stage involves clustering parts and uses adaptations of an algorithm from the field of robotics and motion planning and of the multidirectional search algorithm developed by Dennis and Torczon. The second stage uses a fast algorithm for nesting rectangles.

The resulting system was installed at the Auburn facility for testing and evaluation. Significant reductions in time and material have been observed in tests performed so far. Boeing plans to distribute the system to its other sites around the country.

Source: TechNet, Samuel Eldersveld, Boeing Computer Services

Table of Contents