Article ID: | iaor20135338 |
Volume: | 64 |
Issue: | 10 |
Start Page Number: | 1503 |
End Page Number: | 1504 |
Publication Date: | Oct 2013 |
Journal: | Journal of the Operational Research Society |
Authors: | Estellon B, Gardi F |
Keywords: | NP-hard, sequencing |
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.