Heuristic approaches to batching jobs in printed circuit board assembly.

摘要

The goal of the printed circuit board job-batching (PCB-JB) problem is to minimize the total manufacturing time (setup time and processing time) required to process a set of printed circuit board jobs on an insertion machine. PCBs are processed on a single-head, concurrent, pick-and-place machine that places components onto a board. The PCB-JB problem is a combinatorial optimization problem that is NP-hard thereby, in general, restricting optimal solution techniques to small instances.; We have developed four heuristic approaches to solve the PCB-JB problem: a cluster analysis approach (clustering), a best-fit-decreasing bin-packing approach (BFDJB), a sequencing genetic algorithm approach (GASPP), and a grouping genetic algorithm approach (GGA). We randomly generated 80 problems and performed an experimental design to characterize the performance of these heuristics. Results show that there is not a best heuristic for all circumstances. Clustering obtains the best average solution quality and fastest execution time. For a small number of jobs in the set to be partitioned, the grouping genetic algorithm finds the best solutions often finding the optimal solution. For problems with a large number of jobs, clustering is preferred for problems with a small job size variance and the BFDJB heuristic is preferred for problems with a large job size variance. The execution time for the BFDJB heuristic is close to the clustering algorithm. The two genetic algorithms are slower. GGA requires over 30 hours for a problem that takes less than 18 seconds for the clustering heuristic.