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 practical interest 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 analyse their worst-case behaviour. 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, and their average tightness is evaluated through extensive computational experiments on randomly generated test instances.
