Heuristic algorithms and scatter search for the cardinality constrained P//Cmax problem

Dell’Amico, Mauro ; Iori, Manuel ; Martello, Silvano (2004) Heuristic algorithms and scatter search for the cardinality constrained P//Cmax problem. Journal of Heuristics, 10 (2). pp. 169-204. ISSN 1381-1231
Full text disponibile come:
[thumbnail of Heuristic.pdf]
Anteprima
Documento PDF
Licenza: Creative Commons Attribution Non-commercial 3.0 (CC BY-NC 3.0)

Download (259kB) | Anteprima

Abstract

We consider the generalization of the classical P//Cmax problem (assign n jobs to m identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2. We briefly survey lower and upper bounds from the literature. We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria

Abstract
Tipologia del documento
Articolo
Autori
AutoreAffiliazioneORCID
Dell’Amico, Mauro
Iori, Manuel
Martello, Silvano
Parole chiave
scheduling, parallel processors, cardinality constraint, scatter search, computational complexity, constraint handling, heuristic programming, minimisation, parallel processing, processor scheduling, tree searching
Settori scientifico-disciplinari
ISSN
1381-1231
DOI
Data di deposito
07 Apr 2006
Ultima modifica
31 Ott 2012 11:50
URI

Altri metadati

Statistica sui download

Statistica sui download

Gestione del documento: Visualizza il documento

^