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 (air-conditioning, sun-roof, 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 %NP-complete (Gent 1999).

- We model station capacities by using the database predicates blockSize(I,S) maxCarsInBlock(I,M), such that C=M\S represents % I-th 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