Optimization of the feeder assignment for PCB assembly machines
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Publicerad
2010
Författare
Wiklund, Kristoffer
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
This report is part of a master thesis done at Chalmers University of Technology in Göteborg and in cooperation with Valor Computerized Systems. The purpose with the report was to compare different algorithms performance in solving a subproblem in PCB assembly. PCB assembly is about to balance the PCB production between different production lines in a factory. For each line one need to balance electrical parts’ assembly between the machines in the production line. Finally a minimized sequence of the assembly of components is constructed. The subproblem for this thesis has been the feeder assignment problem, where the problem is come up with setup for how and in which feeder slots the components for the production should be placed, for minimizing the production time. The subproblem has been showed to be NP-hard been proven that the Traveling Salesman problem can be transformed to the subproblem. We have chosen to compare two versions of Local Search algorithms and two versions of genetic algorithms and a simple heuristic algorithm. To obtain a reliable comparison, the solutions are imported into Valor’s software to solve and model a complete assembly machine. Valor’s software has enabled us to obtain the simulated production times. To be able to use the chosen algorithm a new and simplified cost function has been developed. Our approach has showed that is possible to lower the production time compared to Valor’s current software. To draw a concussion of which algorithm to use is not possible. All five algorithms have given around one percent improvements. One explanation for that is that the simplified cost function has simplified the problem to much so that it is not possible to separate a good feeder assignment hungry against a less good solution. Sammanfattning Denna rapport är en del av ett examensarbete utfört på Chalmers tekniska högskola i samarbete med Valor Computerized Systems. Syftet med rapporten var att jämföra olika algoritmers förmåga att lösa ett utav delproblemen inom kretskortstillverkning. Kretskortstillverkning handlar om att fördela kretskorts tillverkning mellan olika produktionslinjer i en fabrik. För varje linje handlar det om att fördela komponenternas montering mellan maskinerna i en produktionslinje. Slutgiltigt så ska en minimerad sekvens av montering av komponenter konstrueras. Rapporterns delproblem, matar fördelningsproblemet, har varit att lösa hur och i vilka matare som komponenter ska placeras i, så att produktionstiden är minimerad. Delproblemet är bevisat att vara NP-svårt genom att bevisa att Handelsresandeproblemet kan transformeras till delproblemet. Vi har valt att jämföra två versioner Local Search algoritmer och två versioner av generiska algoritmer och en enkel heuristik algoritm. För att få en trovärdig jämförelse har lösningarna importeras till Valor’s programvara för att lösa och modellera upp en fullständig monteringsmaskin. Genom Valor’s programvara har vi kunnat erhålla simulerade produktionstider. För att kunna använda valda algoritmer har också en egen förenklad kostfunktion utvecklats. Vår tillgångavägsätt sätt har visat på att det går att sänka produktionstiden jämföra med Valors nuvarande programvara. Vilken algoritm som ska användas går inte att dra slutsatser ifrån då de alla fem ligger på runt en procents förbättring. En förklaring till detta har varit den förenklade kostfunktionen vilket trors ha förenklat problemet för mycket och gjort att bra lösningar inte kan skiljas från mindre bra lösningar.
Beskrivning
Ämne/nyckelord
Datavetenskap (datalogi) , Computer Science