Re: <no subject>

[James Ignizio <jpi6g@virginia.edu>]

Mr. Norbert:

We encountered what would seem to be a rather similar problem in the
petrochemical industry some years ago. It was solved, to the satisfaction of
the company, by:

1. First constructing an Expert System that replicated the existing
process/decision making for scheduling/sequencing/balancing, and then

2. Using permutation search to improve on the solution arrived at by the
Expert System. (I suppose that GAs could be used in place of the permutation
search method if one wanted.)

Since the procedure reduced (per the firm's calculations, not ours) costs at
a rate of 5 million dollars a year, they were quite happy with the $50,000
it cost them for the solution(s). So, while it isn't "mathematically
sophisticated," the approach might be of interest in your situation.

Jim Ignizio

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Professor James P. Ignizio
University of Virginia
ignizio@virginia.edu
JUST PUBLISHED! GONE AWRY: A virtual tour through High Tech Hell
http://www.geocities.com/goneawry25
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

----------
>From: "Bodsch, Norbert" <Norbert.Bodsch@volkswagen.de>
>To: Multiple recipients of list GASCHEDULING <gascheduling@sheffield.ac.uk>
>Date: Wed, Mar 22, 2000, 11:52 AM
>

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