TOPOS – A new constructive algorithm for nesting problems

Abstract. In this paper we present a new constructive algorithm for nesting problems. The layout is built by successively adding a new piece to a partial solution, i.e. to the set of pieces previously nested. Several criteria to choose the next piece to place and its orientation are proposed and tested. Different objective functions are also proposed to evaluate and compare partial solutions. A total of 126 variants of the algorithm, generated by the complete set of combinations of criteria and objective functions, are computationally tested.

The computational experiments are based on data sets published in the literature or provided by other authors. In some cases this new algorithm generates better solutions than the best known (published) solutions.

Zusammenfassung.

In dem vorliegenden Beitrag entwickeln die Autoren ein neues Konstruktionsverfahren für das „Nesting-Problem”, d.h. für ein zweidimensionales Zuschneideproblem mit unregelmäßigen Objekten. Das Schnittmuster wird dadurch gebildet, dass sukzessive zuzuschneidende Objekte (Teile) einer Teillösung angegliedert und damit neue Teillösungen gebildet werden. Verschiedene Kriterien zur Auswahl des jeweils anzuordnenden Teils und seiner Orientierung werden vorgestellt. Außerdem werden verschiedene Zielfunktionen zur Bewertung der Teillösungen herangezogen. Insgesamt ergeben sich so 126 Varianten des Konstruktionsverfahrens, die systematisch anhand von Datensätzen aus der Literatur getestet werden. Für einige Testprobleme stellt das neue Verfahren Lösungen bereit, die besser sind als die besten bisher in der Literatur beschriebenen Lösungen.