Rješavanje problema pakiranja

završni rad

• Naslov (engleski): Bin Packing Problem
• Autor: Samuel Lucić
• Mentor: Marko Čupić (mentor)
• Član povjerenstva: Marko Čupić (predsjednik povjerenstva)
• Član povjerenstva: Fran Jelenić (član povjerenstva)
• Član povjerenstva: Filip Karlo Došilović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem pakiranja spremnika je optimizacijski problem koji pripada problemima grupiranja. To su problemi gdje je cilj grupirati elemente nekog skupa. U ovom radu koristit ćemo grupirajući genetski algoritam. To je inačica genetskog algoritma čiji su operatori i način kodiranja prilagođeni problemima grupiranja. Pokazat ćemo hibridizirani pristup koji koristi različite heuristike i algoritme lokalne pretrage. Izvršit ćemo testiranja za oba pristupa. Skupovi podataka za testiranje dijele se na lakše i teže. Za svaku instancu problema poznato je optimalno rješenje. Rezultati pokazuju znatno bolje performanse za hibridizirani algoritam u odnosu na običan.

Sažetak (engleski)

Bin packing problem is an optimization problem which belongs to the grouping problems. Those are the problems where the goal is to group the elements of a set. In this paper we will use the grouping genetic algorithm. Grouping genetic algorithm is a variant of genetic algorithms whose operators and encoding are designed specifically for grouping problems. We will also show the hybrid approach which uses various heuristics and local search algorithms. Finally, we will run tests for both approaches. Test sets are divided into easier and harder sets. For every test instance optimal solution is known. The results show much better performance for the hybrid approach.

• Ključne riječi: problem pakiranja spremnika; grupirajući genetski algoritam; hibridizirani grupirajući genetski algoritam; lokalna pretraga; heuristike
• Ključne riječi (engleski): bin packing problem; grouping genetic algorithm; hybrid grouping genetic algorithm; local search; heuristics
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:637495
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 09:34:37