Optymalizacja rozkroju

W poprzednim artykule, znajdował się krótki wstęp do problemu optymalizacji rozkroju. Było dużo teorii, trochę informatyki i matematyki. Teraz chciałbym się zająć stroną praktyczną tego problemu. Tak więc opowiem trochę o programie do optymalizacji rozkroju TonCut. A dokładnie, opiszę krok po kroku proces optymalizacji od strony użytkownika, czyli z Twojego punktu widzenia.

Przejdźmy więc do zadania. Mamy dwa arkusze o wymiarach 3200 x 2250. Na tych arkuszach mamy rozmieścić następujące formatki:

 Tabela 1 – Wielkości formatek

Na rys. 1 znajduje się wersja dla wzrokowców, bo ja na przykład patrząc na te liczby powyżej – nic nie widzę. No dobrze, skoro już to widzimy możemy przejść do optymalizacji. Osoby chcące sprawdzić swoje umiejętności w rozmieszczaniu formatek na arkuszach, mogą teraz spróbować swoich sił i rozwiązać ręcznie powyższe zadanie.

Rys. 1 – Formatki z tabeli 1

Po włączeniu programu TonCut, oczom ukazuje się okienko jak na rys. 2. Po lewej stronie mamy listy formatek i arkuszy. Domyślnie, aktywna jest zakładka formatek. Więc klikając myszką przycisk Dodaj u dołu ekranu, możemy dodać nową formatkę.

Rys. 2 – Główne okno programu TonCut

Po wciśnięciu tego przycisku pojawi się małe okienko. (rys. 3). Zawiera ono trzy pola obowiązkowe, które trzeba wypełnić. Tak więc wpisujemy pierwszą formatkę: szerokość 350, wysokość 850 i ilość 8. Po wpisaniu każdej wartości należy nacisnąć klawisz Enter i dodatkowo, na koniec, aby zatwierdzić kilka razy Enter. Nic więcej nie trzeba robić. Po zatwierdzeniu, okienko się zamyka i znów jesteśmy w oknie głównym. Aby dodać kolejną formatkę znów wciskamy klawisz Dodaj. Jak już mamy wprowadzone formarki, przechodzimy do zakładki arkusze. Te wprowadza się analogicznie do formatek.

Rys. 3 – Dodawanie nowej formatki

Jak już wprowadzimy wszystkie formatki i arkusze, powinniśmy zapisać zestaw na dysk. Służą do tego opcje Zachowaj i Zachowaj jako w menu Plik. Opcja Zachowaj zapisuje zestaw formatek i arkuszy na dysku w aktualnie otwartym pliku. Jeśli nie otwieraliśmy jeszcze żadnego pliku, to jest ona równoważna z opcją Zachowaj jako. Ta z kolei zanim zapisze dane na dysk, prosi o wskazanie nazwy pliku.

Szybkie wprowadzanie danych o formatkach i arkuszach.

Kiedy jesteśmy w głównym oknie programu, możemy bardzo szybko, za pomocą klawiatury, wprowadzać dane. Tak więc, aby rozpocząć wpisywanie danych należy wcisnąć przycisk + lub Insert na klawiaturze. Jest to równoznaczne, z wciśnięciem przycisku Dodaj za pomocą myszki. Teraz wpisujemy szerokość i Enter, wysokość i Enter, ilość i Enter. N koniec, jeśli dane są poprawne wciskamy Enter aby zatwierdzić. Czynność powtarzamy, aż wszystkie pozycje zostaną wprowadzone. Jeśli chcemy usunąć jakąś pozycję, to za pomocą strzałek ustawiamy zaznaczenie na niej i wciskamy klawisz – lub Delete na klawiaturze. Aby zmienić dane pozycji, ustawiamy zanzaczenie na niej i wciskamy Enter.

Aby przejść do listy formatek należy nacisnąć Alt+1, a do listy arkuszy Alt+2.

Zanim przystąpimy do optymalizacji należy ustawić opcje wyszukiwania. Wybieramy z menu Wyszukiwanie»Konfiguracja, lub klikamy przycisk Zmień, znajdujący się po prawej stronie okna głównego, połączony z napisem „Konfiguracja”. Okno konfiguracji wygląda tak jak na rysunkach 4.1 i 4.2. W tej chwili interesują nas tylko dwie pozycje: Kryterium odzysku i Minimalna szerokość cięcia. Kryterium odzysku pełni rolę informacyjną i decyduje o tym, jak będzie traktowany odpad, tzn. czy nadaje się do ponownego użycia, czy nie. Minimalna szerokość wykroju jest bardzo ważną wartością. Informuje program o tym, jaką minimalną odległość jest w stanie uzyskać operator lub maszyna pomiędzy dwoma równoległymi cięciami. Jeśli ta wartość będzie ustawiona na zero, może się zdarzyć, że operator będzie musiał odciąć kawałek szkła o szerokości 1mm. Tak więc, bezwzględnie należy tę wartość ustawić. Pozostałe opcje są nam w tej chwili zbędne i powinny być wyłączone.

Rys. 4.1 – Okno konfiguracji

Rys. 4.2 – Okno konfiguracji

Na zakładce Profile wyszukiwania mamy metody wyszukiwania. W tej chwili powinny zostawimy domyślne ustawienia. Więcej o nich opowiem w następnej części tego artykułu.

Kiedy już wszystko mamy, możemy przystąpić do optymalizacji. Aby rozpocząć proces wyszukiwania, należy wcisnąć przycisk Start, w prawym górnym rogu okna głównego. Po wciśnięciu tego przycisku zawartość okna się zmieni (rys. 5).  Po lewej stronie widzimy wygląd wybranego arkusza. Arkusze możemy wybierać za pomocą czterech przycisków u dołu. Jeśli w czasie wyszukiwania, wybierzemy ostatni arkusz, będziemy widzieli jak program znajduje coraz lepsze kombinacje. W prawym górnym rogu, widzimy statystykę wybranego arkusza. Poniżej statystyki znajdują się dwie zakładki. Na każdej zakładce znajduje się lista – na pierwszej – formatek, a na drugiej – arkuszy. Pozycje zaznaczono na zielono, znajdują się na aktualnie wybranym arkuszu. Poniżej tabel znajdują się zakładki, odpowiedzialne za zawartość kolumny Ilość:

• Wszystkie – wyświetla to samo, co w oknie głównym, czyli wszystkie formatki i arkusze.
• Użyte – wyświetla formatki i arkusze dotychczas użyte we wszystkich arkuszach.
• Pozostałe – wyświetla różnice pomiędzy wszystkimi i użytymi.
• Użyte na arkuszu – wyświetla formatki i arkusze użyte na aktualnie wybranym arkuszu.

Pod zakładkami widzimy informacje o postępie wyszukiwania:

• Ilość kombinacji sprawdzonych podczas optymalizacji aktualnego arkusza.
• Całkowity czas wyszukiwania.
• Postęp optymalizacji.

W prawym dolnym rogu znajdują się dwa przyciski.

• Następny arkusz – program przerywa optymalizację aktualnego arkusza, pozostawia aktualny stan jako ten najlepszy i przechodzi do optymalizacji następnego.
• Przerwij – Kończy proces wyszukiwania.

Podczas oglądania wyników optymalizacji możemy kursor myszki przesunąć na podgląd arkusza (lewa strona). Wtedy na podglądzie zostanie podświetlony wybrany element i dodatkowo pod arkuszem zostanie wyświetlona informacja na jego temat. Jeśli na podglądzie klikniemy jakąś formatkę to na liście, po prawej stronie zostanie ona podświetlona.

Wyniki zależą od konfiguracji, ale przy ustawieniu 15mm minimalnej odległości pomiędzy cięciami, otrzymałem następujące wyniki:

• Arkusz 1: 1,97% odpadu,
• Arkusz 2: 6,19% odpadu, plus 2,40% do ponownego użycia.

Duży odpad przy drugim arkuszu wynika z tego, że po prostu jest za mało formatek.

Rys. 5 – Wygląd okna podczas wyszukiwania

To na tyle w tym odcinku. Następnym razem napiszę jak drukować i zapisywać wyniki w programie do optymalizacji rozkroju TonCut.

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.