Bin-packing problem

master's thesis

• Author: Fran Stanić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Mario Bukal (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-07-07, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Opisani su i analizirani osnovni egzaktni, heuristički i aproksimativni algoritmi za Bin-packing problem u jednoj i dvije dimenzije. Za Bin-packing problem u tri dimenzije dan je kratak pregled algoritama koji se koriste. Implementirana je programska podrška za rješavanje 1D i 2D problema opisanim algoritmima. Također je implementiran algoritam za pakiranje slika (tekstura) u jednu veću (engl. \textit{texture atlas}), koja može rasti po potrebi. Takvo pakiranje slika često se koristi u razvoju videoigara, jer poboljšava performanse prikazivanja slika. Implementirani algoritmi evaluirani su na nasumično generiranim instancama problema, a rezultati su prezentirani te je na osnovu njih napravljena usporedba performansi algoritama.

Abstract (english)

Basic exact, heuristic, and approximation algorithms for one and two-dimensional Bin-Packing are described and analyzed. For three-dimensional Bin-Packing problem a short overview of existing algorithms is given. Software for solving 1D and 2D instances with the described algorithms is provided. An algorithm for packing smaller images (textures) into a larger, resizable image (texture atlas) is implemented. Such packing of images is often used in video game development, as it speeds up the rendering process. An evaluation of implemented algorithms on randomly generated problem instances is given, accompanied by the comparative analysis of the performances of the tested algorithms.

• Keywords: Bin-Packing; optimizacija; umjetni imunološki sustav; 1D; 2D; Korf; NP-potpunost
• Keywords (english): Bin-Packing; optimization; artificial immune system; AIS; 1D; 2D; Korf; NP-completeness
• Language: croatian
• URN:NBN: urn:nbn:hr:168:573204
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 12:05:45