Optymalizacja rozkroju

Algorytmy optymalizacyjne są różne i zwykle stosuje się ich kilka. Ogólnie rzecz biorąc jest tak, że wszystkie kombinacje tworzą drzewo (ramka poniżej). Optymalizacja natomiast zajmuje się odcinaniem niektórych gałęzi. Im wcześniej gałąź zostanie odcięta, tym mniej testów program będzie musiał wykonać.

Tak wygląda drzewo kombinacji. Im wyżej tym więcej kombinacji. Z jednego węzła może wychodzić różna ilość gałęzi, choć zwykle jest ona stała. Kombinację stanowi zbiór węzłów na drodze od korzenia do liścia. Gdzie kolejne węzły to formatki na konkretnych pozycjach.

W przeciwieństwie do człowieka, komputer bardziej lubi, kiedy formatek jest dużo więcej niż może się zmieścić na arkuszu. Ma wtedy większe pole do popisu. Tak więc, przy korzystaniu z programów komputerowych nie warto wykonywać optymalizacji dla kilku formatek – lepiej poczekać na większą ilość. Aktualnie, programy potrafią tak poukładać formatki, że odpad nie będzie przekraczał 3% wielkości arkusza. I trwa to – zwykle – kilka sekund.

Przy optymalizacji pojawiają się też inne problemy. Najważniejsze z nich to sortowanie formatek wg wielkości i/lub wg klienta. Oczywiście można to rozwiązać wprowadzając dodatkowe kryteria do algorytmów. Jednak powoduje to znaczny wzrost wielkości odpadu i to właśnie jest główną przyczyną tego, że bardzo rzadko spotyka się takie możliwości w programach.

Zachęcam więc wszystkie firmy do korzystania z optymalizacyjnych programów komputerowych. Pozwoli to Wam zaoszczędzić dużo czasu i pieniędzy. Moim zdaniem jedynym z najlepszych i najprostszych w użyciu programów tego typu jest TonCut firmy Codeton Software.

Producenci arkuszy (tafle szkła, płyty wiórowe, płyty kamienne, blacha, itp) wytwarzają materiał, o wymiarach znacznie przekraczających potrzeby zwykłych klientów. W momencie otrzymania zlecenia, firma staje przed poważnym problemem. Musi z dużego arkusza wyciąć mniejsze formatki. Doświadczony fachowiec potrafi w głowie poukładać formatki na arkuszu tak, aby odpad był jak najmniejszy. Jednak proszę sobie wyobrazić taką sytuację, że mamy 10 arkuszy i 100 różnych formatek do wycięcia. Żaden człowiek nie jest w stanie ich tak poukładać, aby układ był optymalny, czyli żeby odpad był jak najmniejszy.

Problem jest podobny do kostki rubika. Mamy ułożoną kostkę – każda ściana jest w jednym kolorze. Teraz dowolnie, kilkakrotnie przekręcamy kolory w różnych kierunkach. W wyniku otrzymujemy kostkę z różnokolorowymi ściankami. Ponowne ułożenie, dla niedoświadczonej osoby, jest bardzo trudne. Po prostu jest tyle kombinacji, że trudno jest sobie to wszystko wyobrazić. Tak samo jest z małymi formatkami na dużym arkuszu, zwłaszcza gdy formatek jest dużo więcej niż może się zmieścić na jednej płaszczyźnie. Kombinacji są miliony, a nawet miliardy. Nawet komputer, analizując wszystkie możliwości, nie jest w stanie rozwiązać tego w rozsądnym czasie.

Powróćmy na chwilę do ostatniego przykładu – 100 formatek. Sama próba brania ich pod uwagę w różnej kolejności daje nam 100! (100 silnia) kombinacji, czyli około 9,33×10¹⁵⁷. Liczba jest ogromna. A trzeba jeszcze wziąć pod uwagę, że formatka może być położona w pozycji poziomej lub pionowej, z lewej lub prawej strony. Dodatkowo dochodzi warunek, że arkusz może być cięty tylko po linii prostej – zawsze na dwie części. Tak więc, widać że problem nie jest prosty.

Takiej ilości kombinacji nie jest chyba w stanie przeliczyć żaden komputer na ziemi – w rozsądnym czasie oczywiście. Ale, całe szczęście istnieje dziedzina informatyki, która zajmuje się rozwiązywaniem takich problemów. Chodzi tu o optymalizację. Jak sama nazwa wskazuje, dziedzina ta zajmuje się optymalizacją procesu wyszukiwania. Polega to na tym, że nie są sprawdzane wszystkie kombinacje, ale tylko te, które mogą dać lepszy wynik od aktualnego.