Printed circuit boards are manufactured in automated assembly lines, where high-speed placement machines put components on the boards. These machines are frequently bottlenecks in the production. This is true especially in high-mix low-volume environments, where time consuming setup operations of the machines have to be done repeatedly. Therefore, one can improve productivity with a proper setup strategy. The most popular strategies are the so-called group setup strategy and minimum setup strategy. In this paper, we consider the machine setup problem as a combination of a job grouping problem and a minimum setup problem. We formulate this joint problem as an Integer Programming model, where the objective is to minimize the weighted sum of the number of setup occasions and the total number of component feeder changes. We also present and evaluate hybrid algorithms based on both grouping and minimum setup heuristics. The best results are achieved by a method which uses both these strategies simultaneously.
Today's electronic industry uses highly automated systems to manufacture its products. The central part of an electronic product, printed circuit board (PCB) with its electronic components, is manufactured in automated assembly lines. A line can assemble components on multiple types of PCBs and it has one or several high-speed machines to perform the actual placement of operations. Problems incurring in PCB assembly are largely specific to the particular production environment. Here, one should consider whether the factory has one or many assembly lines and whether the production program contains a few or numerous different products. According to these properties the problems in PCB assembly can be divided into four major classes, which in turn include several different subproblems [1], [2], [3]. One PCB type and one machine (1-1) class concentrates on single machine optimization problems (e.g., feeder arrangement and placement sequencing). Multiple PCB types and one machine (M-1) class comprises setup strategies for a single machine. One PCB type and multiple machines (1-M) class includes line balancing and component allocation to multiple machine problems. Multiple PCB types and multiple machines (M-M) class concentrates on scheduling problems in general. These problem types have been studied intensively during the last 15 years from practical and theoretical point of view. The field is interesting for (at least) two reasons. First, the competitiveness of individual companies in the field depends on the cost efficiency of the production. One important aspect is the throughput of individual assembly lines which should be maximized to keep the machine and personal costs low. Second, the problems are quite challenging due to their inherent difficulty and the fact that they offer the possibility of using several different approaches for formulation and solution. For a detailed discussion of subproblems in PCB assembly, see the extensive survey by Crama et al. [4].
In this paper, we examine the single machine setup problem (M-1) in a high-mix low-volume environment. We assume that the total number of different component types exceeds limited component feeder capacity, and feeder setup operations are needed often during a shift. Small PCB manufacturers tend to have only few assembly lines and a large variety of PCBs to produce, which causes problems. More pressure is added to setup operations, if prototypes are assembled in the same line. To improve the productivity, an efficient use of the bottleneck machines is one of the key aspects in production control.
Leon and Peters [5] classify the different setup management strategies into four main categories: unique setup, group setup, minimum setup and partial setup strategies. We consider in this work group setup and minimum setup strategies, which seem to be the most popular strategies in high-mix low-volume production environments in the single machine case.
Group setup strategy forms job groups of similar PCBs so that component setups are incurred only between groups. Hence, any board type in the group can be produced without changing the component setup, which is only required when switching from one group to another. A natural objective is to minimize the number of groups. One should note that a group setup implies the same feeder setting for all PCB types in the group. Of course it reduces the possibility of generating efficient control programs for individual PCB types. Therefore, the method is more useful in low-volume production than for the mass production. Numerous researches have studied the group setup strategy: Hashiba and Chang [6] suggest grouping PCBs as the first step in their three-stage procedure of reducing setup times and present heuristics for the grouping problem. Maimon and Shtub [7] present a mixed-integer programming formulation and a heuristic method for grouping a set of PCBs to minimize the total setup time. Shtub and Maimon [8] consider the PCB grouping problem as an extension of set-covering problem. Daskin et al. [9] present a mathematical formulation for the PCB-grouping problem, show that the problem is NP-complete, and give a branch-and-bound based heuristic algorithm for solving it. Bhaskar and Narendran [10] apply graph theory for solving the grouping problem. Crama et al. [4] analyze the approximation of the job grouping and minimum setup strategies. Smed et al. [11] introduce and compare several heuristics algorithms based on greedy, clustering, and repair-based local search methods, and Knuutila et al. [12] compare the results of efficient heuristics to optimal solutions found by 0/1-programming and by constraint logic programming.
It is worth noting here that the PCB grouping changes essentially if there are a fixed number of simultaneously operating machines instead of a single machine. Then the objective is to distribute the work to the different machines so that the maximally loaded machine has smallest possible load, see Crama et al. [4], for a model of this problem.
Minimum setup strategy attempts to sequence the boards and determine component-feeder assignments to minimize the total component changeover time. Barnea and Sipper [13] translate the mathematical model of the tool switching problem of Tang and Denardo [14] to the PCB environment and present a heuristic for minimizing setups. Jain et al. [15] develop a mathematical model and a four-stage method for sequencing jobs on a PCB assembly line, where a rolling horizon of production is taken into account. Günther et al. [16] present and compared three heuristics for solving a minimum setup problem on a typical surface mount technology production line. Dillon et al. [17] present four variants of a greedy heuristic that aims at maximizing iterative the component commonality whenever the PCB type changes. Narendran and Rajkumar [18], [19] also apply the minimum setup strategy in their heuristics to minimize the total setup time on a PCB assembly environment. Hertz et al. [20] present and compare several algorithms based on efficient traveling salesman problem (TSP) heuristics and new distance definitions for minimizing the number of tool switches in a flexible machine.
In this work our interest focuses on group setup and minimum setup strategies. According to our experience a single component feeder of a placement machine can be changed typically in 1–5 min but it may take, for instance, 15–25 min to prepare the machine for the component setup operations, because the starting of one or several component changes requires extra manual work by the personnel. Therefore, we have to consider two different setups: a component setup comprises the required operations to replace one component feeder with another, and a setup occasion takes place every time when the line is interrupted for one or more feeder changes. The cost function of the setup operations for a set of PCB assembly jobs on a single machine is a weighted sum of these two operations C(y,z)=Ry+Sz,where R and S are constant weights (i.e., time factors) for the number of setup occasions (y) and for the number of component changes (z).
We have examined earlier the ability of several efficient grouping and minimum setup algorithms to minimize formula (1) [21]. We observe that if R/S is at least 5, grouping algorithms give better results; otherwise minimum setup algorithms are more preferable. The reason for this is clear: by setting R (S) to zero we have the common job grouping problem (the minimum setup problem). It is more interesting to consider the situation where both of these weights are positive (i.e., R>0,S>0), and our main goal here is to find a method suited for this practical case. The algorithms given in this paper are based on a hybrid method presented by Smed et al. [21]. In the original method, after grouping the PCBs each group is considered as a super-PCB. They are then used as an input for a minimum setup algorithm, which arranges the super-PCBs in such a way that the feeder changes between the super-PCBs are minimized.
The rest of the paper is organized as follows: In Section 2 we formulate the hybridization of the job grouping and minimum setup problems as an Integer Programming (IP) model. In Section 3 we describe two heuristic algorithms to the problem and present their experimental results in Section 4. The paper is closed with concluding remarks in Section 5.
Check access to the full text by signing in through your organization.
In this section, we formulate the hybrid machine setup problem, called here the job grouping with minimal feeder setup (JGMFS) problem, as an IP model. We follow Tang and Denardo's [14] mathematical model (translated into PCB environment by Barnea and Sipper [13]), where the objective is to minimize the number of tool switches (component feeder changes). In addition, our formulation takes into account the number of setup occasions (groups) by adding a new decision variable (y n) to the model. If
Since the optimal solution of our IP formulation for JGMFS is hard to find in problems of realistic size, we need to develop efficient heuristics. First, we shortly present algorithms that we have been used to the JGMFS problem previously [21]. Then, we describe our new hybrid algorithms.
In this section, we present a summary of our computational results with the hybrid algorithms (GMSA1, GMSA2, GMSA3) on three different datasets. The number of different PCBs in the dataset 1, 2, 3 are 20, 30, 40, respectively. To get a better understanding of the operation of the methods we have repeated the experiment for each dataset 100 times using each time different PCB sets. The PCBs were drawn randomly from an production program of a high-mix low-volume production plant. Each PCB type
We formulated a combined job grouping problem and minimum feeder setup problem in PCB assembly for a single machine case. The objective was to reduce the weighted sum of the number of setup occasions and the number of component feeder changes. This hybridization model simulates the real-world production planning situation where both of these factors should be considered. We presented two new hybrid algorithms (GMSA2, GMSA3) based on efficient grouping and minimum setup heuristics. Our practical
2021, Computers and Operations Research
Bard (1988) developed a nonlinear integer program and solved it using a dual-based relaxation heuristic to produce good solutions in a small CPU time. Salonen et al. (2006b) considered both job-grouping and tool-switch objectives but also reported heuristic results for the classical SSP. Burger et al. (2015) developed job-grouping heuristics for the color print scheduling problem, which is an application of the SSP.
Copyright © 2005 Elsevier Ltd. All rights reserved.
