Car sequencing is NP-hard: a short proof

Abstract

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 research courses, this result and its proof are particularly interesting for teaching purposes.

Keywords:

• car sequencing
• computational complexity
• NP-hardness proof

Acknowledgements

The authors express their gratitude to the anonymous referees for their reviewing, which has resulted in an improved paper.