Car sequencing
The car sequencing problem (CSeq) illustrates interesting features of CP including wide parameter settings, redundant, surrogate and global constraints
addition, and specialized data structures de nition. This is a constraint satisfaction problem that amounts to find an assignment of cars to the slots of a
car-production company, which satisfies capacity constraints.
As a model-oracle of this problem is given here (Mx(k)). Starting from this model, we built an optimized model by introducing several refinements (Px(k)). When building our improved
model of car sequencing, we recorded four faulty constraint models that are used
for experiments. Here again, the idea was to keep models that represent realis-
tic faults instead of a posteriori injected faults.
Tab.1 gives the results of CPTEST on two instances of the problem: an
assembly line of 10 cars, 6 class and 5 options (instance1) ; an assembly line with 55 cars,
7 class and 5 options (instance2). Using conf_one, CPTEST reports non-conformities for the
three first CPUT in less than 1sec for both instances. CPUT4 has no solution as
the fault introduced on the pack constraint prunes dramatically the search space.
This case is interesting as detecting this fault is really uneasy. With the conf_all
relation, the results are balanced as three instances were not detected as non-
conformant within the allocated time slot. For example, in CPUT2, the capacity
constraint of the first option is violated (1 out of 2). This fault results from a
bad formulation but it is quickly detected with confone. When confall is selected,
more constraints have to be negated and then our algorithm has to backtrack a
lot, which explains the failure. The non-conformity reached in this case satisfies
the model-oracle and violates CPUT2, so it represents a correct assembly line
that CPUT2 excludes from its solutions. Therefore, we can conclude that CPUT2
adds and removes solutions which make it difficult to detect as non-conform.
| conf_one | conf_all | |||
|---|---|---|---|---|
| 10 slots | 55 slots | 10 slots | 55 slots | |
non-conf CPUT1 T(s) |
4 5 3 6 4 6 5 1 3 2 |
p1 |
4 5 4 6 3 6 5 1 3 2 |
--- |
0.30s |
1.23s |
2.49s |
timeout |
|
| non-conf CPUT2 T(s) | 4 6 3 1 5 2 3 5 4 6 |
p2 |
5 4 3 5 4 6 2 6 3 1 |
--- |
0.85s |
1.65s |
1.20s |
timeout |
|
| non-conf CPUT3 T(s) | 5 2 3 6 1 4 3 6 4 5 |
p3 |
5 4 3 5 4 6 2 6 3 1 |
--- |
0.24s |
0.70s |
90.73s |
timeout |
|
| non-conf CPUT4 T(s) | conf |
conf |
1 3 6 2 6 4 5 3 4 5 |
p4 |
0.96s |
1.06s |
1.26s |
100.22s |
|
non-conf__ P T(s) |
conf |
--- |
6 4 5 3 4 5 2 6 3 1 |
--- |
3.01s |
timeout |
0.17s |
timeout |
|
p1 = 6 5 6 4 5 2 4 4 4 3 5 6 7 6 3 3 3 5 6 4 5 5 2 2 7 3 4 2 5 5 5 4 1 3 4 1 6 4 3 1 5 3 3 6 1 6 7 7 7 2 6 3 1 6 4 _______________________________________________________________________________________ |
||||
tab3. Fault detection and localization of car sequencing problem.
| TEST | LOCALIZATION | ||||
|---|---|---|---|---|---|
| G.rulers | #_constr. | fault_injected | non.conf._detected | fault localization | time |
| CPUT1 | 2 | p1_ct2 | [4 5 3 6 4 6 5 1 3 2] | (rev(P1), (m_ct2)) | 0.46s |
| CPUT2 | 3 | p2_ct3 | [4 6 3 1 5 2 3 5 4 6] | (rev(P2), (m_ct2)) | 0.23s |
| CPUT3 | 3 | p3_ct2 | [5 2 3 6 1 4 3 6 4 5] | (rev(P3), (m_ct2)) | 0.67s |
| CPUT4 | 4 | p4_ct5 | sol(CPUT4)=emptyset | (rev(p4_ct2),emptyset) | 0.87s |
| CPUT5 | 6 | p5_ct1 |
sol(CPUT5)=emptyset | (rev(p5_ct1),emptyset) | 1.29s |
| CPUT6 | 6 | p6_ct6 | sol(CPUT6)=emptyset | (rev(p6_ct6), emptyset) | 1.34s |
| CPUT7 | 6 | p7_ct5 | sol(CPUT7)=emptyset | (rev(p7_ct5,p7_ct6),emptyset) | 1.28s |
Correction:
- Mutant1 ==> (Emptyset, 32 EC)
- Mutant2==> (Emptyset, 32 EC)
- Mutant3==> (Emptyset, 31 EC)
- Mutant4==> (ct12, 37 EC)
- Mutant5==> (ct1, Emptyset)
- Mutant6==> (ct6, Emptyset)
- Mutant7==> (ct5, Emptyset)
- ----------==> (ct6, Emptyset)
All our experiments were performed on Intel Core2 Duo CPU 2.40Ghz machine with 2.00 GB of RAM.
