No Subject

["Bodsch, Norbert" <Norbert.Bodsch@volkswagen.de>]

Hi all,

I'm new in this list, so I would enjoy if anyone could give me some hints
how to tackle the  problem as stated in what follows. To say it beforehand:
I'm searching for a suitable representation for a kind of "Mixed-model
assembly line sequencing problem".

The painted carbodies of  the model "Bus" in the Volkswagen plant in
Hannover are stored in a large buffer, called "Steuerhaus", before they are
launched onto the assembly lines.

The goal is to find a sequence such that certain constraints (You might know
the "Car Sequencing Problem") are fulfilled and certain optimality criteria
are maximized/minimized, the main of which is to achieve a smooth load at
the single stations at the assembly lines.

As the "Bus" ist available as a utility vehicle and as a passenger car with
many different options, the product variety is so high, that each car can be
regarded as unique. And the work contents are so different for the different
models, that a sequence that is "good" for one station possibly is "bad" for
another. 

So, pure car sequencing alone doesn't fit to my problem. Nor does another
approach to generate a "smooth" sequence, "Level Scheduling".

Initially, I tried to solve the problem with Genetic Algorithms alone: An
individual in my population is a single sequence which I can measure by the
optimality criterium. (There has been done some work before at Volkswagen,
but on a simplified problem.)

But it's difficult to regard other facts that can't be neglected:

1. Assembly line structure (read this in a fixed font like Courier):
                                    7
                                o-------o 
       1                  5         8
    o-----o   3     4 o-------o o-------o
o-S-o  2  o-------o---o   6   o-o   9
    o-----o           o-------o o-------o
                                    10
                                o-------o

So the lines 1 and 2 are parallel, as well as 5 and 6 as well as 7 to 10. S
ist the "Steuerhaus".

> 2. The problem is constrained: Not every model is allowed to go over every
> line. There are distance constraints (which You probably know from the
> "car sequencing problem"). Some of them are soft, others hard. Many
> different constraints of this kind exist, and there are also other kinds
> of constraints. So actually it's a Constraint Satisfaction Problem.
> 
So my problem is to handle the CSP together with a GA. The main problem is
that the Genetic operators return infeasible offsprings. As I know, there
are tree different ways to tackle this:
a) Strong Penalties 
b) Repair Function
c) Sophisticated GA problem representation and Genetic operators that
produce feasible offsprings.

3. Another problem is, that the problem's a dynamic one: Only those cars
that are actually stored in the "Steuerhaus" are available for beeing
sequenced at that time, and as there are continously appearing new cars from
the paintshop, You have to react or resequence. And this reactivity must be
"fast".

Dear reader, if You have arrived at this line, You're possibly interested in
similar questions. So it would be nice to give me Your comment and hints.

Regards
Norbert Bodsch (Ph.D. student)

Norbert Bodsch
Volkswagen AG
K-DOE-3  IS Entwicklungssteuerung und Fertigungsplanung
Fabrikplanung und -simulation
Brieffach 1832
38436 Wolfsburg
Tel. (0 53 61) 9-2 95 03
Fax (0 53 61) 9-2 48 89
norbert.bodsch@volkswagen.de