For an evolutionary algorithm to work properly, it needs to have a notion of the quality of a solution. As such, evolutionary algorithms are not suited to pure decision problems unless the ``distance'' from a proposed solution to a real solution can be measured and used as a cost. That is, the decision problem needs to be transformed into an optimization problem before being solved via evolutionary algorithms. For the car sequencing problem, there are two fundamental ways of doing this: authorize an overuse of resources or an overuse of time. In the former, the capacity constraints on options are softened, allowing them to be violated. Any such violation can be given a cost. The sum of all such violation costs can then be used as a measure of distance from a solution to the original problem. If an assignment with this cost at zero is found, a solution to the car sequencing problem has been found. This example explores the other alternative for transformation into an optimization problem: allow more than n slots to build n cars. The number of additional slots used is used as a measure of the cost: again, if it is reduced to zero, a solution to the original car sequencing problem has been found.

In order to allow the number of slots to be increased, a certain number of ``empty'' configurations are added to the problem. These configurations require no options and so may be used in the schedule to buffer, or create free space, between real configurations. As you shall see in the description of the decoder, empty configurations are never inserted by choice--they are only inserted when no real configuration can be placed that would respect the capacity constraints on all options. One might view these configurations as a stall of the production pipeline. The number of empty configurations appearing before the last car is built can then be used as a cost. If this cost is reduced to zero, the schedule cannot be further compressed and a solution to the original problem has been found. As a convention, configurations are numbered from 1, the empty configuration having index 0.