Problem polnjenja košev v povezavi z omejitvijo kardinalnosti

Abstract

Keywords

Data

Language:	Slovenian
Year of publishing:	2011
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[M. Remic]
UDC:	004(043.2)
COBISS:	8451156
Views:	45
Downloads:	3
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Cardinality constrained bin packing
Secondary abstract:	Bin packing is an optimizational NP-hard problem of packing items of given sizes into minimum number of capacity-limited bins. Besides the basic problem, numerous other variants of bin packing exist. The cardinality constrained bin packing adds an additional constraint that the number of items in a bin must not exceed a given limit Nmax. Some well-known algorithms for solving the general bin packing problem are described, along with three specific algorithms for solving the cardinality constrained bin packing problem. The FFD, RFF and Zhang's algorithms are compared to the three specific algorithms on random lists of items with 0%, 10%, 30% and 50% of large items. The behaviour of all algorithms when Nmax increases is also studied. Results show that all three specific algorithms outperform the general algorithms on lists with low percentage of large items. One of the specific algorithms performs better or equally even on lists with high percentage of large items and is therefore of significant interest. The behaviour when Nmax increases shows that all three specific algorithms can be used for solving the general bin packing problem as well.
Secondary keywords:	approximation algorithms;comparison;FFD;RFF;Zhang's algorithm;computer science;diploma;
File type:	application/pdf
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	43 str.
ID:	23984544