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.

Bounds for the Cardinality Constrained P||Cmax Problem / Dell'Amico, Mauro; S., Martello. - In: JOURNAL OF SCHEDULING. - ISSN 1094-6136. - STAMPA. - 4:3(2001), pp. 123-138. [10.1002/jos.68]

Bounds for the Cardinality Constrained P||Cmax Problem

DELL'AMICO, Mauro;
2001

Abstract

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.
2001
4
3
123
138
Bounds for the Cardinality Constrained P||Cmax Problem / Dell'Amico, Mauro; S., Martello. - In: JOURNAL OF SCHEDULING. - ISSN 1094-6136. - STAMPA. - 4:3(2001), pp. 123-138. [10.1002/jos.68]
Dell'Amico, Mauro; S., Martello
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/15976
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 28
  • ???jsp.display-item.citation.isi??? 23
social impact