Car sequencing is NP‐hard: a short proof

Car sequencing is NP‐hard: a short proof

0.00 Avg rating0 Votes
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: ,
Keywords: NP-hard, sequencing
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.

Reviews

Required fields are marked *. Your email address will not be published.