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 ill 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.

Lower bounds and heuristic algorithms for the $k_i$-partitioning problem / Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 171:(2006), pp. 725-742. [10.1016/j.ejor.2004.09.002]

Lower bounds and heuristic algorithms for the $k_i$-partitioning problem

DELL'AMICO, Mauro;IORI, MANUEL;
2006

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 ill 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.
171
725
742
Lower bounds and heuristic algorithms for the $k_i$-partitioning problem / Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 171:(2006), pp. 725-742. [10.1016/j.ejor.2004.09.002]
Dell'Amico, Mauro; Iori, Manuel; S., Martello; M., Monaci
File in questo prodotto:
File Dimensione Formato  
DIMM_Ki_Partitioning_EJOR.pdf

accesso aperto

Tipologia: Pre-print dell'autore (bozza pre referaggio)
Dimensione 226.29 kB
Formato Adobe PDF
226.29 kB Adobe PDF Visualizza/Apri
1-s2.0-S0377221704005818-main.pdf

non disponibili

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 502.45 kB
Formato Adobe PDF
502.45 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/310057
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact