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