Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem

We consider the classical P||Cmax problem (assign n jobs tom 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 boundsfrom 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.