Lower bounds and heuristic algorithms for the ki-partitioning problem

Dell’Amico, Mauro ; Iori, Manuel ; Martello, Silvano ; Monaci, Michele (2006) Lower bounds and heuristic algorithms for the ki-partitioning problem. European Journal of Operational Research, 171 (3). pp. 725-742. ISSN 0377-2217
Full text available as:
[img]
Preview
PDF
License: Creative Commons Attribution Non-commercial

Download (231kB) | Preview

Abstract

We consider the problem of partitioning a set of positive integers values into a given number of subsets, each having an associated cardinality limit, so that the maximum sum of values in a subset is minimized, and the number of values in each subset does not exceed the corresponding limit. The problem is related to scheduling and bin packing problems. We give combinatorial lower bounds, reduction criteria, constructive heuristics, a scatter search approach, and a lower bound based on column generation. The outcome of extensive computational experiments is presented

Abstract
Document type
Article
Creators
CreatorsAffiliationORCID
Dell’Amico, Mauro
Iori, Manuel
Martello, Silvano
Monaci, Michele
Keywords
partitioning, cardinality constraints, scheduling, parallel machines, bin packing, scatter search, column generation
Subjects
ISSN
0377-2217
DOI
Deposit date
07 Apr 2006
Last modified
31 Oct 2012 11:51
URI

Other metadata

Downloads

Downloads

Staff only: View the document

^