Car sequencing is NP-hard: a short proof

Article OPEN
ESTELLON , BERTRAND; Gardi , Frédéric;
  • Publisher: Palgrave Macmillan
  • Journal: Journal of the Operational Research Society,volume 64,issue 10 October,pages1,503-1,504
  • Related identifiers: doi: 10.1057/jors.2011.165
  • Subject: [ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO] | [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]

In this note, a new proof is given that the car sequencing (CS) problem is NP-hard. Established from the Hamiltonian Path problem, the reduction is direct while closing some gaps remaining in the previous NP-hardness results. Since CS is studied in many operational rese... View more
Share - Bookmark