# Encoding CarSequencing.dlv

Name CarSequencing.dlv [Root]    Unclassified (114) Martin Gebser CSPLib 001: Car Sequencing Problem - DLV 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 - DLV 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. #maxint = 1000000. sequencing(I,C) v fail(I,C) :- classes(C), cars(I). :- cars(I), not #count{ C : sequencing(I,C) }=1. % c1 :- not #count{I : sequencing(I,C)}=N, classes(C), carPerClass(C,N). % c2 :- #count{S: sequencing(S,C), optInClass(C,O,1), +(I,SIZE,W), S>=I, SMAX, options(O), maxCarsInBlock(O,MAX), blockSize(O,SIZE), cars(I).