Bounds for the Cardinality Constrained P||Cmax Problem

We consider the generalization of the classical P||Cmax problem arising when a given limit k is imposed on the number of jobs that can be assigned to any machine. This generalization has practicalinterest in the optimization of assembly lines for printed circuit boards (PCB). The problem is strongly NP-hard for general k, it is solvable in O(n log n) time for fixed k=2, while it remains strongly NP-hard for any fixed k >= 3. We consider immediate adaptations of simple upper and lower bounds for P||Cmax, and analyze their worst-case behavior. We show that the cardinality constraint does not strengthen the LP relaxation of the problem, and that the worst-case performance of the bounds for P||Cmax generally worsen when they are adapted to the new problem.New specifically tailored lower bounds are introduced, andtheir average tightness is evaluated through extensive computational experiments on randomly generated test instances.