Solving the Car-Sequencing Problem as a Non-binary CSP

The car-sequencing problem arises from the manufacture of cars on an assembly line. A number of cars are to be made on a production line; they are not identical because different options are available as variants on the basic model. The different stations which install the various options have been designed to handle at most a certain percentage of the cars passing along the assembly line. Consequently, the cars must be arranged in a sequence so that these capacities are not exceeded. In this paper, the formulation of the car-sequencing problem is presented as a non-binary constraint satisfaction problem (CSP) with constraints of fixed arity 5. A search algorithm based on non-binary forward checking (nFC) is used to solve the problem. For the car-sequencing problem the variables should be assigned consecutively. The choice of value ordering heuristics having a dramatic effect on solution time for this problem, different value ordering heuristics were implemented. Since any possible solution is a permutation of a fixed set of values, a succeed-first strategy for value ordering only postpones the assignment of the difficult classes and a value ordering based on fail-first could be a better choice. These methods are compared on the instances reported in the CSPLib. The results obtained showed the superiority of a strategy of fail-first type against to a succeed-first strategy. In particular, the

MaxUtil

and

MaxPQ

heuristics allowed a better exploration of the space of solutions and solved all the instances of problems with 200 variables. It should be underlined the fact that these problems were solved in little time (6 seconds on average) and the longest time is 13 seconds for the instance 90_09, whereas for ILOG Solver the least powerful time exceeds 1 minute. This result can be justified by our encoding. Indeed, we encoded the maximum of constraints (the capacity of each option, the request for each class) inside an explicit 5-ary constraint with very high tightness (close to 0.95).

MaxUtil

remains the best heuristic because it is surprisingly backtrack-free. Within the future work, the filtering method will be improved. A hybridization between the optimization methods is another way of interesting research. The use of parallelism also seems an interesting direction for solving this type of problem.