Summary:

Two-dimensional layout is the placement of a set of polygonal pieces on a rectangular sheet of material. It is important especially where expensive materials are used, such as in aircraft, aerospace, automobile, shipbuilding, and apparel manufacturing. In order to maximize efficiency, which is the ratio of area covered by pieces to the total area of the material, the layout must minimize waste without overlapping pieces. A marker is defined in the apparel industry as a layout sheet with fixed width and arbitrary length. It is reported that an experienced human marker maker can probably generate pants markers with efficiencies within 1% of optimal. However, even a small increase in efficiency can have a significant effect on the cost of manufacturing. A large pants manufacturer estimated that a 0.1% average improvement in efficiency will save his company about two million dollars per year. In the long run, research in this field could benefit both the producer and consumer.

While minimizing waste is not a new field in itself, the methods currently under research incorporate the latest in computational geometry. Because of the many factors involved in the layout of nonconvex polygons, it is impossible at this time to find the optimal marker layout with the highest efficiency. The different methods presented in the last few years will be covered in this report.

Previously Proposed Approaches:

• "One piece at a time" method: This theory suggested that the pieces be placed singly in the "container". It was not successful in practice.
• VLSI design: Rectangles and variable length rectilinear wires are used. This does not work for nonconvex polygons.
• Physically based simulation methods:
  1. Spring model: Forces are applied to objects and the rebound force from the collisions determine the layout. It involved too much computational cost.
  2. Contact force: The forces at constant point when constant velocity and force are applied is measured. This method does not work because the pieces get confined in one area.
  3. Velocity-based approach: Mass and forces are "removed" and only velocity is calculated. This method takes a long time.

Li/Milenkovic Method:

These scientists worked to solve the problem of planning motions of the pieces in an already existing layout. They worked under the condition that all polygons can move simultaneously and only the right boundary of the container is moveable. The two resulting algorithms were compaction and separation. Compaction dealt with any motion planning task that stays within the set of non-overlapping configurations. Separation handled tasks that move configurations from an overlapping position to a non-overlapping configuration. The method they came up with incorporated both the velocity-based and position-based models. Position-based model uses no simulations, instead it uses artificial constraints that select a convex feasible subset of the space. This runs in almost real time. Their test beat the human layout efficiency only 60% of the time. However, they noted that starting from a good initial layout can reduce the complexity of marker making and applied their separation algorithm to a database driven marker making method. Database driven system improves the best human made system by finding matching system with similar size and shaped objects in its database of previous human made models.

Daniels Method:

Unlike the previous method, this only deals with translational movements of the objects and not the rotational movements. The difference in this approach is the Daniels worked with systems that had fixed boundaries. Therefore, she concentrated on a common problem of pieces not fitting in a given space. Whereas other methods tried all the different combinations and went on forever, Daniels' approach quickly detected an infeasible problem and stopped running. Her algorithm used geometric techniques on top of mathematical programming techniques. Polygons were fit into better fitting polygons, like rectangles before they were placed. Daniels noticed the best results when the space was pre-packed.

Discussion & Observation:

There is still a lot of work to be done before there can be a fully automated layout system. All the current approaches depend on human experience and optimizes results from the best human layouts. Since manual layouts have been used for such a long time and experience has improved technique to the point near optimum, there is not a strong push to develop fully automated layout systems. Private industry is making independent efforts solely for profits. The government is backing research for the apparel industry but there are so many uses for advances in this particular field.

Future Direction:

The method that seems most promising is the database driven system in conjunction with the separation algorithm. It provides the best results to this date with the potential to improve. Many scientists are realizing that it's not always better to start with a clean slate. Other scientists are studying ways in which artificial intelligence can be used to optimize layout. Again, this depends on past experience. With the use of past experience and new algorithms, layout systems can be extremely practical and efficient. Things to look for in the near future are fully automated layout systems and layout systems for three-dimensional objects.

References