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 disponibile come:
[thumbnail of DIMM_Ki_Partitioning_EJOR.pdf]
Anteprima
 Documento PDF
Licenza: Creative Commons Attribution Non-commercial 3.0 (CC BY-NC 3.0)
Download (231kB) | Anteprima

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
Tipologia del documento
Articolo
Autori
AutoreAffiliazioneORCID
Dell’Amico, Mauro
Iori, Manuel
Martello, Silvano
Monaci, Michele
Parole chiave
partitioning, cardinality constraints, scheduling, parallel machines, bin packing, scatter search, column generation
Settori scientifico-disciplinari
Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
ISSN
0377-2217
DOI
10.1016/j.ejor.2004.09.002
Data di deposito
07 Apr 2006
Ultima modifica
31 Ott 2012 11:51
URI
https://amsacta.unibo.it/id/eprint/2123

Altri metadati

Statistica sui download

Statistica sui download

Vedi altre statistiche

Gestione del documento: Visualizza il documento

© ALMA MATER STUDIORUM - Università d Bologna, 2007-2024.

^