Problema debitarii - enunt si dificultati
Enunt
Dandu-se o placa rectangulara mare si mai multe placi rectangulare mai mici se cere decuparea placiilor mici din placa mare astfel incat pierderea rezultata sa fie minima.
Restrictii
1. Este permisa sau nu rotirea cu 90 grade a pieselor mici.
2. Taieturile se pot efectua doar orizontal sau vertical dintr-un capat in altul al placii care se decupeaza (taieturi de tip ghilotina).
Dificultati si Solutii
Problema optimizarii este o problema extrem de dificila. Ea apartine clasei de probleme Nedeterminist Polinomial Complete (NP-Complete) [1], [2]. Din pacate, pentru toate problemele din aceasta clasa, NU exista algoritmi si exacti si rapizi pentru a le rezolva [1], [2].
Avem 3 optiuni principale:
1. Folosirea unui algoritm exact care furnizeaza solutia optima in toate cazurile.
In acest caz trebuie investigate toate posibilitatile de amplasare a pieselor pe placa. Asta inseamna ca timpul de executie al acestui algoritm creste exponential cu dimensiunea datelor de intrare. Spre exemplu, daca timpul necesar optimizarii a 10 bucati este 1 secunda, atunci timpul optimizarii a 20 de bucati poate fi 1000 secunde, iar timpul necesar decuparii a 30 de bucati poate fi 1000000 secunde.... iar timpul necesar optimizarii a 1000 de bucati nu poate fi exprimat in secunde pentru ca nu putem sa il scriem pe o pagina!!!!
Atentie insa: Timpul de executie este direct dependent de calculatorul pe care rulati! Un calculator 286 (la nivelul anului 1990) nu se compara cu un Pentium 4 (anul 2005). Diferenta de viteza este semnificativa. Din pacate acest crestere in performante nu se prea simte in cazul in care avem de a face cu un algoritm exponential. Spre exemplu pe un Pentium 4 putem optimiza in 1 secunda ceea ce optimizam in 10 secunde pe un calculator 286. Dar daca incercam sa optimizam 1000 de piese folosind un algoritm exponential atunci calculatorul nostru P4 va rula pana la sfarsitul Universului si nici atunci nu va termina!
Atentie!!! Pe piata de soft exista astfel de programe! Verificati viteza de optimizare inainte de a cumpara!
2. Folosirea unui algoritm foarte rapid.
Daca algoritmul este rapid atunci calitatea solutiei obtinute nu este foarte buna in toate cazurile. Spre exemplu putem sa optimizam 1000000 de bucat in 1 secunda, dar asta de obicei inseamna ca nivelul de optimizare este slab rezultand pierderi mari si amplasari neoptime.
In acest caz sunt folositi asa zisii euristici care sunt de fapt niste algoritmi care dau rezultate bune pe niste cazuri particulare, dar care esueaza lamentabil pe niste date care nu se incadreaza in "tipare".
Atentie!!! Pe piata de soft exista astfel de programe! Verificati calitatea de optimizare inainte de a cumpara!
3. Varianta de compromis.
Varianta cea mai des intalnita este de a face un compromis intre timpul de executie si calitatea solutiei obtinute.
O solutie foarte des utilizata este explorarea a cat mai multe posibile configuratii (dispuneri ale pieselor pe placa) si apoi alegerea a celei mai bune dintre ele. Si aici exista multe probleme. Unele solutii sunt foarte slabe si de aceea nu merita sa fie explorate. Din nou trebuie facut un compromis intre solutiile explorate si cele nexplorate.
De obicei programele din aceasta categorie au un parametru extra: Nivelul de Optimizare. Acest parametru spune cam cate solutii sunt explorate inainte de a fi afisata cea mai buna solutie gasita. Daca nivelul de optimizare este mic atunci solutia este gasita repede, dar nu este de obicei foarte buna. Daca nivelul de optimizare este ridicat atunci timpul necesar gasirii unei solutii este mare, dar calitatea acesteia este de obicei buna.
Programul Cutting Optimization Pro exploreaza in mod inteligent acest spatiu al configuratiilor si apoi afiseaza cea mai buna solutie gasita.
Referinte
[1]. Garey, M.R., Johnson D.S., Computers and Intractability: A Guide to NP-completeness, Freeman & Co, San Francisco, USA, 1979.
[2]. Cormen, T.H., Leiserson, C.E. Rivest, R. R., Introduction to Algorithms, MIT Press, Cambridge, MA, USA, 1990.
Legaturi