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