# Encoding CarSequencing.sm

Name CarSequencing.sm [Root]    Unclassified (114) Martin Gebser CSPLib 001: Car Sequencing Problem - Smodels spec - author: Micaletto Davide revised by: Marco Cadoli, Toni Mancini, Fabio Patrizi. 2009-03-30 13:03 2008-11-29 00:10 No % CSPLib 001: Car Sequencing Problem - Smodels spec - % author: Micaletto Davide % revised by: Marco Cadoli, Toni Mancini, Fabio Patrizi. % % 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. #hide. #show sequencing(I,C). % main predicate - the production sequence 1 { sequencing(I,C): classes(C) } 1 :- cars(I). % c1 N{ sequencing(I,C): cars(I)}N :- classes(C), carPerClass(C,N) . % c2 % each block can contain at most maxCarsInBlock for each option :- MAX+1{sequencing(S,C): optInClass(C,O,1): cars(S): ge(S,I): le(S,I+SIZE-1)}, options(O), cars(I), maxCarsInBlock(O,MAX), blockSize(O,SIZE).