Problem pakovanja u prostoru
Ovaj članak možda zahteva čišćenje i/ili prerađivanje kako bi se zadovoljili standardi kvaliteta Vikipedije. Problem: Potrebno je dodati unutrašnje veze. |
Problem pakovanja u prostoru podrazumeva pakovanje objekata različitih zapremina u konačno mnogo kontejnera sa ciljem da se minimizuje broj potrebnih kontejnera za skladištenje datih objekata. U teoriji složenosti ovaj problem se klasifikuje kao NP-težak problem. Postoje različite varijacije ovog problema, 2D Pakovanje, Linearno pakovanje, Pakovanje u odnosu na težinu, Pakovanje u odnosu na cenu itd. Oblasti u kojima se primenjuje rešenje ovog problema su: Popunjavanje kontejnera, Utovar u kamion sa zadatim težinskim ograničenjem, Pronalaženje optimalnog rasporeda predmeta u prostoru sa zadatim uslovima balansa itd.
Iako je problem klasifikovan kao NP-težak (što znači da za velike instance problema ne postoji egzaktni algoritam polinomijalne složenosti koji daje optimalno rešenje, osim ako P = NP) razvijeno je mnoštvo heuristika koje pronalaze zadovoljavajuća rešenja (bliska optimalnom, koja zadovoljavaju sve kriterijume pakovanja) u polinomijalnom vremenu. Većina opisanih heuristika koriste sortiranje kao krucijalni korak u algoritmu i time se postiže logaritamska složenost u odnosu na broj objekata .
Formalna definicija problema
urediProblem pakovanja u prostoru se definiše na sledeći način, dato je elemenata (kvadrova) i neograničen broj identičnih kontejnera dimenzija . Dimenzije -tog objekta, , definišu se sa . Pretpostavka je da se objekti ne mogu rotirati. Cilj je upakovati objekata tako da su ispunjeni sledeći uslovi:
- Svaka postavka predmeta mora biti ortogonalna (paralelna u odnosu na osu)
- Svaki objekat se mora nalaziti u potpunosti unutar kontejnera
- Za svaka dva objekta unutar istog kontejnera važi da se ne seku
- Potrebno je minimizovati broj potrebnih kontejnera
Pristup rešavanju problema
urediJedan od glavnih problema koji se javljaju prilikom proučavanja ovog problema je kako na efikasan način odabrati poziciju objekta unutar prostora (kontejnera) tako da se pozicioniranjem objekta na odabrano mesto ne naruše ograničenja (balansa, redosleda, itd.) Performanse kao i kvalitet dobijenog rešenja algoritama koj se koristi za pakovanje objekata u velikoj meri zavisi od strategije za odabir tačaka koje određuju poziciju objekta. Heuristika koja je u dosadašnjem istraživanju proizvela najbolje rezultate, kako po pitanju efikasnosti tako i po kvalitetu krajnjih rešenja, uvodi koncept Ekstremnih tačaka koje predstavljaju skup potencijalnih pozicija na koje je moguće smestiti tekući objekat u odnosu na tekuću konfiguraciju.
Primenom prethodno opisane strategije dobijaju se kvalitetna rešenja približna optimalnom ali se takođe primećuju i nedostaci. Naime prilikom umetanja objekata dolazi do fragmentisanja prostora na ispunjen prostor (prostor koji zauzima trenutna konfiguracija objekata) i rezidualni prostor (prostor koji je slobodan za umetanje preostalih objekata). Moguće je da se prilikom umetanja objekta prostor fragmentiše tako da rezidualni prostor zapreminski može da prihvati tekući objekat ali ne postoji ni jedna ekstremna tačka u rezidualnom prostoru koja zadovoljava uslov da se nakon smeštanja objekta na njenu poziciju može izbeći presek sa nekim od objekata u trenutnoj konfiguraciji. Što čini umetanje tekućeg objekta nemogućim.
Prilikom rešavanja problema pakovanja u prostoru neophodno je dakle razmotriti dva suštinska podproblema:
- Kako odabrati skup tačaka koje predstavljaju potencijalne pozicije objekta koji je potrebno spakovati?
- Kako učiniti da rezidualni prostor bude što bolje iskorišćen?
Heuristika umetanja korišćenjem ekstremnih tačaka
urediHeuristika umetanja korišćenjem ekstremnih tačaka je konstruktivna heuristika koja umeće objekte redom, jedan po jedan u odnosu na zadatu sekvencu objekata dok svi objekti nisu umetnuti u prostor (kontejner). Ova heuristika je trenutno najbolja u ovom domenu. Koncept ekstremnih tačaka posmatra prostor kao listu ekstremnih tačaka, gde svaka tačka predstavlja potencijalnu poziciju za umetanje novog objekta. Prazan prostor (kontejner) se posmatra kao lista koja sadrži samo jednu ekstremnu tačku . Umetanje novog objekta povlači zauzimanje jedne ekstremne tačke iz liste i uvođenje konstantnog broja novih tačaka. Slika 1(a) i 1(b) ilustruju uvođenje 2 odnosno 6 ekstremnih tačaka umetanjem novog objekta za (redom) 2D i 3D slučaj.
Za zadatu sekvencu objekata opisana heuristika pokušava da umetne objekat na ekstremnu tačku u postojećem prostoru. Ukoliko ne postoji ekstremna tačka koja zadovoljava kriterijume, instancira se novi prostor (kontejner) i objekat se umeće na poziciju . Postupak se ponavlja dok se ne umetnu svi objekti. Prirodno može postojati podskup skupa ekstremnih tačaka koji zadovoljava uslove umetanja u tom slučaju potrebno je odabrati strategiju za odabir neke od potencijalnih tačaka. Neke od strategija su: Najmanje euklidsko rastojanje, Odabir prve tačke koja zadovoljava kriterijume, itd.
Heuristika za defragmentisanje prostora
urediGlavni cilj kod problema pakovanja u prostoru je dobijanje gustih konfiguracija čime se postiže visoka iskorišćenost datog prostora za pakovanje. Konstrukcijom gustih konfiguracija objekata prirodno se smanjuje broj potrebnih kontejnera za smeštanje objekata iz sekvence. Heuristika za defregmentisanje prostora u suštini pokušava da postavi objekat na poziciju , ukoliko je pozicija zauzeta (na poziciji se nalazi neki od objekata iz trenutne konfiguracije) heuristika translira sve objekte maksimalno u odnosu na koordinatni početak kako bi se napravilo mesto za novi objekat. Prilikom implementiranja ovog postupka prvo je potrebno utvrditi da li ovjekat i može da se postavi na poziciju a zatim i mora biti postavljen na poziciju .
Da bi se navedeni postupak sproveo posmatraju se geometrijska svojstva objekata, za svaki objekat se posmatra njegova projekcija na i osu. Postupak je dovoljno opisati za jednu od osa za preostale se postupak sprovodi analogno. Za sbaki objekat posmatra se njegova projekcija na osu označena sa , skup projekcija nazivaće se skup krajnjih tačaka. Postupak se može definisati na sledeći način zamišljajući vertikalnu liniju koja se kreće zdesna ulevo:
- Sortirati skup od krajnjih tačaka, levi krajevi se porede ukoliko su desni jednaki.
- Vertikalna linija u svakom trenutku definiše skup intervala koji se nalaze potpuno levo od objekta , gde je pozicija vertikalne linije.
- Vertikalna linija ažurira graničnu vrednost koja predstavlja najveću vrednost desnog kraja za sve intervale iz
- Kada vertikalna linija skenira ažurira se
- Kada vertikalna linija skenira ažurira se
Vidi još
urediReference
uredi- Vazirani, Vijay V. (2003), Approximation Algorithms, Berlin: Springer, ISBN 978-3-540-65367-7
- Yue, Minyi (oktobar 1991), „A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm”, Acta Mathematicae Applicatae Sinica, 7 (4): 321—331, ISSN 0168-9673, S2CID 189915733, doi:10.1007/BF02009683
|contribution=
ignorisan (pomoć) - Dósa, György (2007), „The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9”, Ur.: Chen, Bo; Paterson, Mike; Zhang, Guochuan, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science, 4614/2007, Springer Berlin / Heidelberg, str. 1—11, ISBN 978-3-540-74449-8, ISSN 0302-9743, doi:10.1007/978-3-540-74450-4
- Xia, Binzhou; Tan, Zhiyi (2010), „Tighter bounds of the First Fit algorithm for the bin-packing problem”, Discrete Applied Mathematics, 158 (15): 1668—1675, ISSN 0166-218X, doi:10.1016/j.dam.2010.05.026
|contribution=
ignorisan (pomoć) - Garey, Michael R.; Johnson, David S. (1985), „A 71/60 theorem for bin packing*1”, Journal of Complexity, 1: 65—106, doi:10.1016/0885-064X(85)90022-6
|contribution=
ignorisan (pomoć) - Yue, Minyi; Zhang, Lei (jul 1995), „A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm”, Acta Mathematicae Applicatae Sinica, 11 (3): 318—330, ISSN 0168-9673, S2CID 118263129, doi:10.1007/BF02011198
|contribution=
ignorisan (pomoć) - Fernandez de la Vega, W.; Lueker, G. S. (decembar 1981), „Bin packing can be solved within 1 + ε in linear time”, Combinatorica, Springer Berlin / Heidelberg, 1 (4): 349—355, ISSN 0209-9683, S2CID 10519631, doi:10.1007/BF02579456
|contribution=
ignorisan (pomoć) - Lewis, R. (2009), „A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing” (PDF), Computers and Operations Research, 36 (7): 2295—2310, S2CID 1577334, doi:10.1016/j.cor.2008.09.004
- Silvano Martello and Paolo Toth (1990), Knapsack Problems Algorithms and Computer Implementations.
- Michael R. Garey and David S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. . 1979. ISBN 978-0-7167-1045-5. Nedostaje ili je prazan parametar
|title=
(pomoć) A4.1: SR1. str. 226.
- David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
- Lodi A., Martello S., Monaci, M., Vigo, D. (2010) Two-Dimensional Bin Packing Problems. In V.Th. Paschos (Ed.), “Paradigms of Combinatorial Optimization”, Wiley/ISTE. str. 107-129
- Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
- Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011), „Sharing-Aware Algorithms for Virtual Machine Colocation”, Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367—378