TY - THES A1 - Epping, Thomas T1 - Color sequencing N2 - In this dissertation, we present several solution approaches for the color change minimization problem that arises in the paint shop of an automobile plant. We give NP-completeness results for an abstract formulation of this problem and show that it is APX-hard, even in a restricted form. For this form, we establish a connection to binary matroids. When solving the color change minimization problem with the help of a line storage system, we present dynamic programs that use algorithms from computational biology, among others. Finally, we look into the color change minimization problem within the overall production process of an automobile plant. We describe an algorithm that sequences a daily production and that has been successfully developed with and implemented in the Ford Motor Company (Europe). N2 - Diese Arbeit stellt verschiedene Methoden zur Lösung des Problems der Farbwechselminimierung in der Lackierstraße einer Automobilfabrik vor. Für eine theoretische Formulierung des Problems geben wir NP-Vollständigkeitsresultate und zeigen, dass es selbst in eingeschränkter Form noch APX-schwer ist. Für diese zeigen wir eine Verbindung zu binären Matroiden auf. Bei der Farbwechselminimierung mit Hilfe eines Linienspeichers geben wir, unter anderem mit Methoden der Bioinformatik, dynamische Programme zur Lösung des Problems an. Schließlich betrachten wir die Farbwechselminimierung im Kontext des kompletten Produktionsprozesses einer Automobilfabrik. Wir beschreiben ein Verfahren zur Sequenzierung einer typischen Tagesproduktion, das in Kooperation mit der Ford-Werke AG erfolgreich umgesetzt wurde. KW - Karosserie KW - Spritzlackieren KW - Farbwechseltechnik KW - Prozessoptimierung KW - Reihenfolgeproblem KW - APX-Hardness KW - Binary methods KW - Dynamic programming KW - Flexible manufacturing systems KW - Projekt management and scheduling Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-000000572 ER -