Bounds for the cardinality constrained P∥Cmax problem

✍ Scribed by Mauro Dell'Amico; Silvano Martello

• Publisher: Springer US
• Year: 2001
• Tongue: English
• Weight: 150 KB
• Volume: 4
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/jos.68

✦ Synopsis

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 ÿxed k = 2; while it remains strongly NP-hard for any ÿxed 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 speciÿcally tailored lower bounds are introduced, and their average tightness is evaluated through extensive computational experiments on randomly generated test instances.