Optimization of the feeder assignment for PCB assembly machines

Sammanfattning: This report is part of a master thesis done at Chalmers University of Technology in Göteborgand in cooperation with Valor Computerized Systems. The purpose with the report was tocompare different algorithms performance in solving a subproblem in PCB assembly. PCBassembly is about to balance the PCB production between different production lines in afactory. For each line one need to balance electrical parts’ assembly between the machines inthe production line. Finally a minimized sequence of the assembly of components isconstructed. The subproblem for this thesis has been the feeder assignment problem, wherethe problem is come up with setup for how and in which feeder slots the components for theproduction should be placed, for minimizing the production time. The subproblem has beenshowed to be NP-hard been proven that the Traveling Salesman problem can be transformedto the subproblem.We have chosen to compare two versions of Local Search algorithms and two versions ofgenetic algorithms and a simple heuristic algorithm. To obtain a reliable comparison, thesolutions are imported into Valor’s software to solve and model a complete assemblymachine. Valor’s software has enabled us to obtain the simulated production times. To be ableto 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’scurrent software. To draw a concussion of which algorithm to use is not possible. All fivealgorithms have given around one percent improvements. One explanation for that is that thesimplified cost function has simplified the problem to much so that it is not possible toseparate 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 isamarbete med Valor Computerized Systems. Syftet med rapporten var att jämföra olikaalgoritmers förmåga att lösa ett utav delproblemen inom kretskortstillverkning.Kretskortstillverkning handlar om att fördela kretskorts tillverkning mellan olikaproduktionslinjer i en fabrik. För varje linje handlar det om att fördela komponenternasmontering mellan maskinerna i en produktionslinje. Slutgiltigt så ska en minimerad sekvensav montering av komponenter konstrueras. Rapporterns delproblem, matarfördelningsproblemet, har varit att lösa hur och i vilka matare som komponenter ska placerasi, så att produktionstiden är minimerad. Delproblemet är bevisat att vara NP-svårt genom attbevisa att Handelsresandeproblemet kan transformeras till delproblemet.Vi har valt att jämföra två versioner Local Search algoritmer och två versioner av generiskaalgoritmer och en enkel heuristik algoritm. För att få en trovärdig jämförelse har lösningarnaimporteras till Valor’s programvara för att lösa och modellera upp en fullständigmonteringsmaskin. Genom Valor’s programvara har vi kunnat erhålla simuleradeproduktionstider. För att kunna använda valda algoritmer har också en egen förenkladkostfunktion utvecklats.Vår tillgångavägsätt sätt har visat på att det går att sänka produktionstiden jämföra medValors nuvarande programvara. Vilken algoritm som ska användas går inte att dra slutsatserifrån då de alla fem ligger på runt en procents förbättring. En förklaring till detta har varit denförenklade kostfunktionen vilket trors ha förenklat problemet för mycket och gjort att bralösningar inte kan skiljas från mindre bra lösningar.