Poopćeni problem dodjeljivanja

master's thesis

• Author: Porin Ćustić
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Committee member: Mladen Jurak (član povjerenstva)
• Committee member: Pavle Goldstein (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-07-18, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Zamislite da ste lopov koji se nalazi u sefu nekog poznatog muzeja. Namjera vam je ukrasti što vrjednije predmete, ali dolazite do problema - na raspolaganju imate malu naprtnjaču. Želite odabrati predmete koji će stati u naprtnjaču, a da im ukupna vrijednost bude što veća. Možete zamisliti i jedan legalan scenarij: imate \(n\) poslova i isto toliko radnika. Svakom radniku trebate platiti da odradi po jedan posao, a svaki od njih ima drugačiju cijenu za pojedini posao. Naravno, cilj vam je dodijeliti poslove tako da vam trošak bude što manji. Poopćeni problem dodjeljivanja je generalizacija ova dva problema. On pretpostavlja da imate \(n\) predmeta i \(m\) naprtnjača, te da vrijednost i težina svakog predmeta ovisi i o naprtnjači u koju ćete ga staviti. Cilj vam je rasporediti sve predmete po naprtnjačama na takav način da ukupna vrijednost bude što veća, a da se ne prekorači kapacitet ni jedne naprtnjače. Ovaj diplomski rad se bavi upravo tim trima problemima. Svaki problem ćemo opisati, analizirati i navesti neke algoritme za njihovo rješavanje. Opisat ćemo i način na koji su problem naprtnjače i linearni problem dodjeljivanja povezani sa poopćenim problemom dodjeljivanja. Na kraju rada ćemo reći nešto više i o implementaciji algoritama za rješavanje ovih problema te navesti neke eksperimentalne rezultate.

Abstract (english)

Imagine yourself in an action movie scene: you are a thief inside a museum vault. You are there to steal as much valuable items as you can, but there is a problem - you only have a small knapsack. You want to choose items that will fit into your knapsack, but will also have the highest possible value. You can imagine another situation: you have \(n\) number of jobs that need to be done by \(n\) workers. For every job, every worker has a price which you need to pay in order for him to get that job done. You need to assign one job to every worker with the objective of minimizing the total cost. Generalized Assignment Problem is a generalization of these two problems. You are given \(n\) number of items and \(m\) number of knapsacks, with the value and size of each item depending on the knapsack you will put it in. Your goal is to maximize the total value by placing each item in one of the knapsacks, making sure none of the knapsacks is overfilled. This master thesis deals with exactly these problems. We will describe and analyze all three problems and give a few algorithms that solve them. We will also describe the connection between Linear Assignment Problem, Knapsack Problem and Generalized Assignment Problem. At the end we will present implementation of some algorithms that are discussed throughout the thesis.

• Keywords: poopćeni problem dodjeljivanja; problem naprtnjače; linearni problem dodjeljivanja
• Keywords (english): Generalized Assignment Problem; Linear Assignment Problem; Knapsack Problem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:814674
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-03-27 10:52:35