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 available as:
[img]
Preview
PDF
License: Creative Commons Attribution Non-commercial

Download (259kB) | Preview

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
Document type
Article
Creators
CreatorsAffiliationORCID
Dell’Amico, Mauro
Iori, Manuel
Martello, Silvano
Keywords
scheduling, parallel processors, cardinality constraint, scatter search, computational complexity, constraint handling, heuristic programming, minimisation, parallel processing, processor scheduling, tree searching
Subjects
ISSN
1381-1231
DOI
Deposit date
07 Apr 2006
Last modified
31 Oct 2012 11:50
URI

Other metadata

Downloads

Downloads

Staff only: View the document

^