Problema debitării optime - enunț și dificultăți

Enunț

Dându-se o placă rectangulară mare și mai multe plăci rectangulare mai mici se cere debitarea plăcilor mici, din placă mare, astfel încât pierderea generată să fie minimă.

Restricții

1. Este permisă sau nu rotirea, cu 90 grade, a pieselor mici.

2. Tăieturile se pot efectua doar orizontal sau vertical dintr-un capăt în altul al plăcii care se debitează (tăieturi de tip ghilotină).

Dificultați si soluții

Problema optimizarii este o problemă extrem de dificilă. Ea aparține clasei de probleme Nedeterminist Polinomial Complete (NP-Complete) [1], [2]. Din păcate, pentru toate problemele din aceasta clasă, nu se cunosc algoritmi exacți și rapizi care să le rezolve (vezi [1], [2]).

Avem 3 opțiuni principale:

1. Folosirea unui algoritm exact care furnizează soluția optimă în toate cazurile.

În acest caz trebuie investigate toate posibilitățile de amplasare a pieselor pe placă. Asta înseamnă că timpul de execuție al acestui algoritm crește exponențial cu dimensiunea datelor de intrare. Spre exemplu, dacă timpul necesar optimizării a 10 bucați este 1 secundă, atunci timpul optimizării a 20 de bucăți poate fi 1000 secunde, iar timpul necesar decupării a 30 de bucăți poate fi 1000000 secunde.... iar timpul necesar optimizării a 1000 de bucăți nu poate fi exprimat în secunde pentru că nu putem să îl scriem pe o pagină!!!!

Atenție însă: Timpul de execuție este direct dependent de calculatorul pe care rulați! Un calculator 286 (la nivelul anului 1990) nu se compară cu un Pentium 4 (anul 2005). Diferența de viteză este semnificativă. Din păcate această creștere în performanțe nu se prea simte în cazul în care avem de-a face cu un algoritm exponențial. Spre exemplu pe un Pentium 4 putem optimiza în 1 secundă ceea ce optimizăm în 10 secunde pe un calculator 286. Dar dacă încercăm să optimizăm 1000 de piese folosind un algoritm exponențial atunci calculatorul nostru P4 va rula până la sfârșitul Universului și nici atunci nu va termina!

Atenție!!! Pe piața de soft există astfel de programe! Verificați viteza de optimizare înainte de a cumpăra!

2. Folosirea unui algoritm foarte rapid.

Dacă algoritmul este rapid atunci calitatea soluției obținute nu este foarte bună în toate cazurile. Spre exemplu putem să optimizăm 1000000 de bucăți în 1 secundă, dar asta de obicei înseamnă că nivelul de optimizare este slab rezultând pierderi mari și amplasări neoptime.

În acest caz sunt folosiți așa zișii euristici care sunt de fapt niste algoritmi care dau rezultate bune pe niște cazuri particulare, dar care eșuează lamentabil pe niște date care nu se încadrează în "tipare".

Atenție!!! Pe piața de soft există astfel de programe! Verificați calitatea de optimizare înainte de a cumpăra!

3. Varianta de compromis.

Varianta cea mai des întâlnită este de a face un compromis între timpul de execuție si calitatea soluției obținute.

O soluție foarte des utilizată este explorarea a cât mai multe posibile configurații (dispuneri ale pieselor pe placă) și apoi alegerea celei mai bune dintre ele. Și aici există multe probleme. Unele soluții sunt foarte slabe și de aceea nu merită să fie explorate. Din nou trebuie făcut un compromis între soluțiile explorate și cele nexplorate.

De obicei programele din această categorie au un parametru extra: Nivelul de Optimizare. Acest parametru spune cam câte soluții sunt explorate înainte de a fi afișată cea mai bună soluție găsită. Dacă nivelul de optimizare este mic atunci soluția este gasită repede, dar nu este de obicei foarte bună. Dacă nivelul de optimizare este ridicat atunci timpul necesar găsirii unei soluții este mare, dar calitatea acesteia este de obicei bună.

Programul Cutting Optimization Pro explorează în mod inteligent acest spațiu al configurațiilor și apoi afișează cea mai bună soluție găsită.

Referințe

[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.



Legături

Înapoi la index

Cutting Optimization pro - pagina web

Optimal Programs - pagina web