- October 10th, 2003
- October 12th, 2003
- November 26th, 2003
- November 27th, 2003
- February 17th, 2004
- February 18th, 2004
- July 15th, 2004

changes and not the number of violations of paint color batches

limitations.

(2) In the Car Sequencing Problems from RENAULT, the number of paint

color changes is in the hundreds.

(3) If a solution A has one more violation on high priority ratio

constraints than solution B, solution A must achieve 100 paint color

changes less than solution B, so as to be better ranked than solution
B.

Such a case is highly unlikely.

(4) The maximum number on the cars with the same color is STRICT.

If the maximum number (length) is 10, a sequence of 30 cars of the
same color is NOT allowed,

even if you consider the penalty of two paint color changes.

(5) Should we take into account the number of color changes of production

day D-1 in the computation of the number of color changes of a solution
?

If yes, I think it means that we just have to add a same constant K
to the number of color changes

of each solution that we examine.

ANSWER: No you don't have to take into account number of color changes
of

production day D-1. You have only to take into account the color of
the

last ordered vehicle of day D-1 so as to know if there is a color change

with the first ordered car of day D.

(6) What happens if N > number of cars in the window W concerned with
the

ratio constraint ? More generally, could the number of violations of
a ratio

constraint on a specified window W of size P be negative ?

If yes, I think it means that we compute such violations on EVERY rolling
sequence.

ANSWER: No the number of violations of a ratio constraint on a specified
window

W of size P cannot be negative. If N > number of cars in the window
W ,

then the number of violations is zero in the window W.

If the maximum number of cars with the same color is N, then we could never find

a sequence of P cars with the same color (P>N). If this sequence of P cars is in

a solution, we consider the solution is invalid.

(7) The maximum number of cars produced per day is 2000 and the maximum
number of

colors considered is 50.

(8) Assuming that we have at the end of day D-1, a yellow car followed
by a red car, then at the

beginning of day D, we have a blue car followed by a green car, we
count two color changes on day D

(one after the red car of day D-1, one after the blue car of day D).
We count three color changes

if the car after the green one has another color than green.

(9) A color change is taken into account after the car in position N
only if there is a car in position N+1

AND the car in position N+1 has a different color than the car in position
N.

If the car in position N is the last car produced of the day D, we
do not count any color change for it.

Then on day D+1, we could possibly count one color change after the
car in position N, if the car in

postition N+1 has a different color.

(10) We forgot to mention in the subject (October 10th, 2003) the following
case

which is in the data set A:

1;high_priority_level_and_difficult_to_satisfy_ratio_constraints;

2;low_priority_level_ratio_constraints;

3;paint_color_batches;

(11) The following cases are useless and they are not in the data set
A.

It is an error in the subject which is now corrected in the new online
documents.

1;paint_color_batches;

2;high_priority_level_and_difficult_to_satisfy_ratio_constraints;

3;low_priority_level_ratio_constraints;

1;paint_color_batches;

2;high_priority_level_and_difficult_to_satisfy_ratio_constraints;

"ratio" N/P=1/5 would be the following:

I suppose that day D+1 is the day to be scheduled and that there is
no

vehicle associated with the ratio constraint HPRC1 in the first 4

positions of day D+1. The impact of day D on day D+1 is 3 further violations,

computed in the following rolling sequences :

`.....x _ _ _ x x _ _ _ _...........................
: 1 violation`
` D
D+1`

`.....x _ _ _ x x _ _ _ _...........................
: 1 violation`
` D
D+1`

`.....x _ _ _ x x _ _ _ _...........................
: 1 violation`
` D
D+1`

(13) Assuming the rule 4/10, a violation is counted in the following case:

`xxxxx_ _ _ _ _`

x: cars of the same characteristic sequenced in day D-1

-: cars in day D.

However, no vilation will be counted in the following cases, because

there are less than 4 cars with the same charactistic in the sliding

windows of size 10:

` xxxx_ _ _ _ _ _`
` xxx_ _ _ _ _ _ _`
` xx_ _ _ _ _ _ _ _`
` x_ _ _ _ _ _ _ _ _`

A "easy_to_satisfy" constraint could be impossible to satisfy

completely since we have no control over the day D-1.

Related to this problem, in the data instance 022_3_4_EP_RAF_ENP, the

last two cars in day D-1 and the first 5 cars in day D with the

characteristic taken into account in the contraine HPRC1 which is of

the form 5/6. The present scheduling does not satisfy this constraint.

This is a little bit "bizarre" since this constraint should be easy.

This is absolutely right. For this data instance and for the

contraints HPRC1, there are 2 violations at the beginning of the day
D

because of the cars sequenced on the day D-1. We apologize for the

definition on the "easy_to_satisfy" constraints which is not precise

enough. We should add in the definition of these constraints that day

D-1 is not taken into account. BUT, day D-1 is still taken into

account for the "normal" ratio constraints.

(14) On the paint color batches of day D, we take into account only
the

last car of day D-1. This is to count one spary gun whas as soon as

the first car of day D has a different color of the last car of day

D-1.

On the longuest paint color batches constraint (upper batch size limit),

we take into account only the cars in day D. This constraint is not
considered

from day D-1 to day D.

a) In test-set A there is no instance of the type

1;high_priority_level_and_easy_to_satisfy_ratio_constraints;

2;paint_color_batches;

You are right : we do not propose all possible combinations of

objectives in the instances of the test-set A. In fact, we extract
the

instances from 6 of our car factories.

b) Which solution is used to generate the file

"reporting_reference_solution.txt". I assume, that it is the solution

corresponding to the file "vehicles.txt"(but without the cars of day

D-1).

Yes, the file "reporting_reference_solution.txt" is based on the

solution from the file "vehicles.txt". The report does not show vehicles

from day D-1. However, the report statistics do take into account the

cars from day D-1 to compute the number of ratio constraints violations

and paint color changes.

c) This solution(question 2) is it generated by

renault or is it more or less random?

The solution is generated by a RENAULT application which is operational

in all our factories since 1993.

- Each team must submit one archive file (candidate-NN.tar.gz or candidate-NN.zip)
containing the directory

Candidate-NN/ and all the subdirectories
mentionned in the subject document.

Please to **replace NN with the family name of
the team leader.**

What to put in these subdirectories:

Candidate-NN/Synthesis/ % an array
containing a synthesis of your results, format .ps or .pdf is appreciated.

Candidate-NN/Instances/ % Test
Set A data instance files we provided,

not very important if this subdirectory is empty since we have the data
files.

Candidate-NN/Solutions/ % The
files containing the structures of the solutions (schedulings indeed).

In any case, you **must respect the format of the solution checker**.

Candidate-NN/Results/
% The files containing the values of the solutions, not very important

if the values are already in the solution files.

Candidate-NN/Team-description/
% a summary on the affiliation of each member of the team and their status
(Prof., Dr., PhD., Ms, etc.)

Candidate-NN/Method-description/ % a detail
description of your method, result analysis, and references. Format
.ps or .pdf is appreciated.

Candidate-NN/Program/
% Only a binary is required, source code is required if we have runtime
problems.

In any case, **all these informations will stay
confidential until the end of this challenge to anybody**
** except to the members of the jury for evaluation
purpose.**

(17) More details on the evaluation procedure.

- Due to an exceptionnal number of participants, it is impossible for
us to have ten runs

for each non-deterministic programs, the number
of runs to compute the average results will

be halved, i.e. **five runs will be done instead
of ten for this qualification stage**.

For the final stage, with less participants, ten
runs will be computed.

- Now, be aware that the jury gives favor to **robust** programs.

- On the **computing time of 600 seconds**, we remind that your programs
should provide

a time limit option (-t) on the command line, e.g.
`binary
data-instance -t 600`

We will also limit the runtime to 600 seconds with
shell scripts to avoid cheatings.

So please to **save in your programs the last best
solutions found before reaching the time limit**.

- For the jury, the qualification stage consists in eliminating candidates
with results "under the average".

This means that this will depend on the number of
candidates who really send a program, the quality

of the global results and also the results of RENAULT
(the ones they have with their own program,

and the ones they will get with your programs).

Though we have announced a maximum of ten candidates
will be selected for the final stage,

the jury could select more if the results are very
closed and exceptionnal. Then the selected candidates

will be judged on the unkonwn Test Set X at the
final stage.

However, only a maximum of ten candidates (included
the winners) will be selected for a presentation

at the ROADEF'2005 conference. The ideal case would
be five teams in each category.

Besides, the jury according to the final results
could invite other teams for a presentation

at the ROADEF'2005 conference in an invited session
if there are original and interesting contributions.

To have an idea, one can have a look on the previous
ROADEF challenges (in
particular 2003)

WEB pages. In any case, **the jury is free to take
the ultimate decision**.

Please to feel free to contact Van-Dat CUNG if it is not clear or if you have any doubt.

- There is **an error of translation in the english version of
the subject (page 16/16)**.

**One should read** "For each class of scenarios,
an ** average** of the marks ..."

"For each class of scenarios, a

(18) On various questions.

- The **paint batch limit** is still the most confusing (see answer
(14) above) and one could find that the

solution checker does not detect some violations
on this point.

Indeed, the paint batch limit is considered only
from the first car of the day D. The last car of the day D-1

is taken into account only to know whether one spray
gun wash should be done (and so counted) before

the first car of day D. In practice, the paint batch
limit could be changed everyday, this is why we do not look

at day D-1 for this limit.

Hope it is clearer this time, if you find it is still
not clear, please to contact Van-Dat
CUNG,

we will find a way to explain it differently.

- On the sentence saying that **there must not be any compensation
between the objectives**.

It means that we want to compare the candidates'
solutions first on

objective O, then on objective O+1 (if the solutions
are equal on

objective O), then objective O+2 etc. We have tried
to ensure that with

the weighted sum of the objectives.

- We could consider that there are a **maximum of fifteen (15) high
priority level and difficult to satisfy ratio constraints**

and of **thirty (30) low priority level ratio constraints**.

- The 600 seconds is the wall clock time. But since we have completely
dedicated machines to test the programs,

there is almost no difference between wall clock
time and CPU time.

instances was that on instance 048_ch2_RAF_EP_ENP_S22_J3 the

optimization objectives state that there are difficult to satisfy high priority level ratio

constraints while the highest priority is on paint color batches. In the

challenge subject this case is not mentioned (in 2.1.2.2) and according to the

faq (answer 11) this case would be useless.

- You are right. There is no difference between the 2 following cases
:

case 1

1;paint_color_batches;

2;high_priority_level_and_difficult_to_satisfy_ratio_constraints;

3;low_priority_level_ratio_constraints;

case 2

1;paint_color_batches;

2;high_priority_level_and_easy_to_satisfy_ratio_constraints;

3;low_priority_level_ratio_constraints;

(21) Another question arising when looking at the instances: What will
be

the maximum ratio constraint denominator (and therefore the number
of

vehicles from the previous production day) ?

- 500 can be considered as the maximum ratio constraint denominator.