Class Tree  

Description 
A number of cars are to be produced; they are not identical, because different options are available as variants on the basic model. The assembly line has different stations which install the various options (airconditioning, sunroof, etc.). These stations have been designed to handle at most a certain percentage of the cars passing along the assembly line. Furthermore, the cars requiring a certain option must not be bunched together, otherwise the station will not be able to cope. Consequently, the cars must be arranged in a sequence so that the capacity of each station is never exceeded. For instance, if a particular station can only cope with at most half of the cars passing along the line, the sequence must be built so that at most 1 car in any 2 requires that option. The problem has been shown to be %NPcomplete (Gent 1999).  We model station capacities by using the database predicates blockSize(I,S) maxCarsInBlock(I,M), such that C=M\S represents % Ith station capacity;  database predicate carPerClass(CARS,CLASS) represents how many cars (CARS) must be produced for each class (CLASS).  We use auxiliary predicate optInCar(I,O), it is defined by the guessed predicate sequencing(I,C). Constraints: c1  The given number of cars for each class must be produced (a class is a subset of options). c2  The cars must be arranged in a sequence so that the capacity of each station is never exceeded. author: Micaletto Davide revised by: Marco Cadoli, Toni Mancini, Fabio Patrizi. 
Encodings 1  3 of 3 
