Definition and Evaluation of the difficulty of the Car Sequencing Problem

The Car Sequencing Problem is a relevant topic both in the literature and in practice. Typically, the objective is to propose exact or heuristic procedures that calculate, in a reduced computational time, a solution that minimizes the number of violated sequencing rules. However, reaching a solution that does not violate any sequencing rule is not always possible because although sequencing rules should be defined to smooth the workload, the evolution of the production mix or some other characteristics can influence the quality of the solutions. In this paper, a first definition of a sequencing rule difficulty is proposed and a statistical study is performed, which allow us to determine the impact of the number of rules, as well as to evaluate how difficult an instance is.