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

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

0.00 Avg rating0 Votes
Article ID: iaor20043605
Country: Netherlands
Volume: 10
Issue: 2
Start Page Number: 169
End Page Number: 204
Publication Date: Mar 2004
Journal: Journal of Heuristics
Authors: , ,
Keywords: heuristics
Abstract:

We consider the generalization of the classical P/Cmax problem (assign to 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.

Reviews

Required fields are marked *. Your email address will not be published.