Please to note that some answers have been translated, so if you have any doubt, please to send an email for confirmation toVan-Dat CUNG.

October 10th, 2003

(1) The evaluation method takes into account the number of paint color
changes and not the number of violations of paint color batches

(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.

October 12th, 2003

(4 bis) Always on the answer (4) , a simple rule is :
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:


(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.



November 26th, 2003

(12)  If car sequence at D day containing , for exampple, HPRC1(x) with a
"ratio" N/P=1/5 would be the following:
.....x _ _ _ x x     _ _ _ _...........................
           D                          D+1

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

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.

November 27th, 2003

(15) Complementary information on the solution checkers and the data set A

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

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

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.

February 17th, 2004

(16) More details on the results submission procedure.

- Each team must submit one archive file (candidate-NN.tar.gz or 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 ..." instead of
    "For each class of scenarios, a median of the marks ...".

(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.

February 18th, 2004

(19) Back on the computing time.

- 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.

July 15th, 2004

(20) One minor thing i noticed when having a first look at the new
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 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
case 2

(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.