Academic journal article Journal of Management Information and Decision Sciences

An Experimental Design Comparison of Four Heuristic Approaches for Batching Jobs in Printed Circuit Board Assembly

Academic journal article Journal of Management Information and Decision Sciences

An Experimental Design Comparison of Four Heuristic Approaches for Batching Jobs in Printed Circuit Board Assembly

Article excerpt

ABSTRACT

The goal of the printed circuit board (PCB) job-batching problem is to minimize the total manufacturing time required to process a set of printed circuit board jobs on a pick-and-place machine. Specifically, to determine which jobs should be processed with the same setup so that the total number of setups is reduced without increasing the required processing time such that the reduction in setup time is offset. Since PCB manufacturers assemble thousands to millions of boards each year, even modest time savings per job are useful.

In this paper, we reports the results of an experiment designed to compare four heuristic approaches to solve the PCB job-batching problem: cluster analysis, a bin-packing approach, a sequencing genetic algorithm, and a grouping genetic algorithm. We developed these heuristic approaches in previous work. However, based on that work, there was not overall best heuristic. These results show that the cluster analysis and bin-packing approaches have fast execution time but do not find optimal solutions while the two genetic algorithms are slower but often find optimal solutions. Results describe the problem characteristics for which each heuristic performs best. Based on the results described here, a user can decide which heuristic is most appropriate based on PCB job characteristics and execution time requirements.

(Heuristic algorithms for combinatorial optimization; PCB assembly)

INTRODUCTION

We performed an experiment to compare the performance of four heuristic approaches to solve the printed circuit board (PCB) job-batching problem. This problem attempts to minimize the manufacturing time (both setup and processing time) for a set of PCB jobs on a pick-and-place machine. Magazine et al. (2002) have shown that this problem is NP-hard so heuristics must be used for difficult problems. In previous work (Williams and Magazine, forthcoming.), we developed heuristic families to solve the PCB-JB problem. None of the heuristics performed best on all problems. In this paper, we describe an experiment and results to determine the problem characteristics for which a heuristic performs better than the other heuristics. Results were analyzed to determine the significant factors affecting solution quality and execution time.

The four heuristics that were compared are: 1) the clustering heuristic is based on a set of techniques adapted to our problem from the cluster analysis literature 2) the bin-packing heuristic is analogous to the best-fit-decreasing bin-packing algorithm 3) the GASPP (Genetic Algorithm Shortest Path Problem) heuristic is a sequencing genetic algorithm that uses a shortest-path algorithm for fitness evaluation. This heuristic searches the space of all job sequences 4) the GGA (Grouping Genetic Algorithm) heuristic searches the space of all partitions of a set of jobs.

The printed circuit board is a subassembly in most electronic products. In 1998, 72.5% of all PCBs produced were utilized by 3 major industries: computers, telecommunications, and consumer electronics. PCB production increased by 5% in 1998 to become a $35 billion industry (Nakahara 1999) and by the year 2000 was a $42.1 billion industry (Nakahara 2001).

In the printed circuit board manufacturing process, the assembly stage can be a system bottleneck (Ahmadi and Kouvelis 1999). During assembly, components such as resistors, capacitors, and integrated chips are placed onto the PCB. PCB assembly has evolved from a labor-intensive process to a highly automated process in which a pick-and-place machine inserts most of these components. According to Mody et al. (1992) a typical shop has 25-30 machines exceeding $1.5 million dollars in value. At Hewlett-Packard (HP), the capital investment of a single assembly line can exceed $2 million dollars (Jain et al. 1996).

The high capital investment combined with the competition among PCB manufacturers creates an environment requiring production efficiency (Mody et al. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.