Figure 1. Generic Placement Machine
Configuration V. Jorge Leon and Brett A. Peters
Department of Industrial Engineering
Texas A&M University
College Station, TX 77843-3131
This paper considers the operation of component placement equipment for the assembly of printed circuit boards (PCBs) in a medium volume, medium variety manufacturing environment. It focuses on the setup management and operational planning issues associated with productive use of these expensive resources. The concept of replanning is introduced to adapt to changes in the production environment by explicitly considering the initial state of the system. The partial setup strategy is suggested as a means of efficient adaptation and as a strategy that subsumes other setup strategies encountered in practice and the literature. These concepts are applied to the optimization of a single placement machine producing multiple products. The results of using partial setups are compared with other commonly used strategies. Experimental results suggest significant gains at the single machine level. Future research is being pursued to improve the solution procedures and extend these replanning concepts to the line level.
The electronics industry is a critical segment of the U.S. manufacturing sector facing challenging global competition. Operating effectively in this industry is becoming more difficult as product variety and options increase, product complexity increases, product life cycles shrink, and profit margins decrease. In addition, the capital equipment costs of electronics assembly facilities are extremely high. These factors necessitate high productivity levels for electronics assembly facilities.
This paper considers component placement equipment for the assembly of printed circuit boards (PCBs) in a medium volume, medium variety manufacturing environment. Component placement equipment is very expensive and is, therefore, often the bottleneck in PCB assembly operations. This paper focuses on the setup management and operational planning issues associated with productive use of these expensive resources. It introduces the concept of replanning to adapt to changes in the environment, explains and exploits a partial setup strategy as a means of efficient adaptation, and shows that this strategy subsumes other setup strategies encountered in practice and the literature. The paper then applies these concepts to the optimization of a single placement machine producing multiple products and compares the results with other commonly used strategies.
For medium volume, medium variety electronic assembly facilities, the concept of replanning is becoming increasingly important. It is necessary that the facilities be capable of quickly reacting to changing events (e.g., changes in product priorities, product design, component availability, or demand levels). The proper response to these changes requires considering the current state of the facility (i.e., the current configuration of each of the lines and machines, the current levels of work-in-process component inventories, the current staffing levels and assignments, etc.) and making the best decisions based on that state - hence the term replanning.
We have seen this situation at several electronic assembly companies and become aware that they do not have the proper tools to address the problem. Furthermore, with the rapid proliferation of electronic components in a variety of consumer products and the increasing customization of these products, it seems likely that an increasing number of companies will need general replanning models to cope with dynamic manufacturing environments.
This paper provides a foundation for system-level replanning by considering the replanning activities necessary at a single placement machine. The setup management and operational planning decisions are made based on the current state of the machine as well as on the latest production requirements on hand. Making proper decisions at the single machine level is critical for effective replanning of the entire facility.
The work in this paper is of interest for two reasons. First, it provides a general model that will adapt the most appropriate strategy for use in a changing environment. It also offers potential performance gains over other commonly used operational planning and setup management strategies. The general model can be used to justify the use of existing strategies, where appropriate. However, it can also identify areas of potential efficiency gain and dynamically recommend the appropriate alternative operational planning strategies. Second, and perhaps most important, this paper provides a foundation for studying the system-level replanning problem. The replanning concepts and strategies used at the machine level will provide the core elements for shop floor operating strategies for the production system. It is essential that a proper understanding of the issues involved with replanning and a set of fundamental strategies for replanning be developed before attacking this problem on a large scale.
The "generic" placement machine used in this paper has three basic components: a table that holds the PCB, a feeder carriage that holds the components, and a head that picks up components from the feeders and places them on the PCB. A machine configuration illustrating the relationship between these components is shown in Figure 1. Our generic machine is a sequential machine in which the head moves to the feeder carriage to pick up the component. After picking up the component, the head moves to the proper location on the PCB for this component. The component is then placed on the board and the head moves back to pick up the next component, until all of the components are placed and the head returns to its initial position. This sequence of events is called a machine cycle. The assignment of component types to slots in the feeder carriage is the component-feeder assignment. The sequence in which the components are placed on the PCB is the placement sequence. We will refer to a specific component-feeder assignment on a machine as the state of the machine.
Figure 2 shows the various time intervals of interest. The changeover time is the time required to remove the components from the feeders on the machine and place a new set of components in the feeders. The placement time is the time to place all components on all PCBs in a batch and is equal to the batch size multiplied by the individual board cycle time plus a material handling time for each board. The board cycle time is the time to place all components on a single PCB. The changeover time plus the placement time is the total product time. The sum of the total product times for all products produced in a period is the makespan.
Figure 1. Generic Placement Machine
Configuration
A board cycle assumes the placement head starts from a given position (i.e., home), moves between feeders and placement locations to mount the required components, and then moves back to the initial position. The placement distance can be easily computed given: (i) the machine and board geometry (i.e., x-y coordinates of feeders, placement locations, and home position), (ii) the component-feeder assignments, and (iii) the placement sequence. The data in (i) is given and the data in (ii) and (iii) must be decided in solving the problem.
Figure 2. Definition of Relevant Time
Intervals
In general, there are a number of different implementations of this generic placement machine depending on which machine components can move, how many heads there are, and whether or not the movement of machine components is sequential or concurrent. McGinnis et al. (1992) provide a classification of the different machine types and a discussion of their similarities and differences. Although these distinctions can be important, for our purposes in this paper, the simpler generic machine provides an appropriate initial model for the analysis of the fundamental concepts in the context of partial setup strategies and replanning.
There have been a number of papers in the literature that consider the optimization of a single placement machine. McGinnis et al. (1992) provide a good review of the recent work in electronic assembly optimization. Most of the "single machine" papers have used the unique setup strategy. (Drezner and Nof, 1984; Ball and Magazine, 1988; Crama et al., 1990; Gavish and Seidmann, 1987; Bard et al., 1989; Chan and Mercier, 1989; Grotzinger, 1988) That is, they have determined the assignment of components to feeder slots on the machine and the sequence of component placements on the printed circuit board to minimize the board cycle time for placing the components on the board given a particular machine type. This setup strategy assumes that during a changeover all the feeders are removed from the machine and replaced with feeders containing the component types in the appropriate feeder locations as specified by the component-feeder assignment.
Another commonly used strategy is the group setup strategy. (Ammons et al., 1991; Askin et al., 1994) With group setup, the component-feeder assignment for the machine is determined for a group or family of similar products. Any product in this group can be produced without having to changeover the machine. Changeover of the machine is only required when switching from one group to another group. Given the feeder assignment for the group, the best placement sequence for each individual product is determined by solving a traveling salesman problem (TSP).
There are also several possible variations of these strategies. A certain set of common components could always be left on the machine and other components added or removed as required for a particular product. Another alternative is to do some or all of the setup off-line. This alternative implies that there are two or more feeder carriages for the machine. While one is being used in production to assemble a PCB, the other is being setup for the next product (or group of products).
A third distinct strategy, the partial setup strategy, has not received much attention in the literature. This strategy is more general since it incorporates the previously mentioned strategies as special cases. This strategy explicitly considers the minimization of makespan. Partial setup strategies specify that only a subset of the feeders on a machine are changed when switching from one product to the next. The critical decisions with partial setups are the specification of the product sequence, the feeders to be changed, the component-feeder assignment, and the component-placement sequence; that is, the best setup strategy for the given conditions.
Lofgren and McGinnis (1986) consider using partial setups on a component sequencer machine. This machine does not require the consideration of assigning components to specific feeder slots. Sadiq et al. (1993) develop a rule-based approach for sequencing printed circuit boards on a single placement machine. A related concept has also been used outside of electronic assembly. Tang and Denardo (1988) present a procedure to minimize the number of tool changes in an NC machine. Askin and Standridge (1993) also provide an overview of partial changeovers for an NC machine. The partial setup strategy, and its application to printed circuit board assembly, is the focus of this paper and is further discussed in later sections.
Considerable insight into the state dependent nature of partial setups can be obtained by investigating a single product case. Product i is to be processed on the placement machine, which is currently in some state , where is a vector that defines the component-feeder assignment for the machine. In order to process product i, at least the required setup must be performed; that is, all of the components needed to produce product i that are not currently on the machine must be loaded onto the machine. However, it is possible that additional setup could be performed to reduce the placement time for product i. The objective, however, is to minimize the total product time (see Figure 2). There are a large number of possible setups that could be chosen, each leading to a different placement time. In fact, we could plot these points on a placement time versus changeover time graph like the one shown in Figure 3.
Figure 3.
Single Product Partial Setup Graph
Two lines are drawn at a 45 angle through points A and B, as shown in Figure 3. Any point on the solid line has the same total product time as point A. Similarly, any point on the dashed line has the same total product time as point B. For this particular example, we see that the dashed line is closer to the origin than the solid line, so any point on the dashed line is preferred to any point on the solid line. Therefore, point B would be preferred to point A, for this specific example. In other examples, this preference might be reversed. However, the partial setup strategy strives to find the point closest to the origin. Point C, in Figure 3, is dominated by both points A and B, since point C lies beyond both the solid and dashed lines. Point D represents an improved partial setup solution. It represents increased changeover beyond the minimum, but not to the extreme of unique setup, such that the total product time is reduced - that is, it lies inside of the dashed line in Figure 3.
Clearly, different system conditions (i.e., different batch sizes, feeder installation/removal times, etc.) will make either unique setup or minimum setup dominate the other. The objective of the partial setup strategy is to determine the point with the minimum total product time. If either point A or point B is the minimum point, then the partial setup strategy will choose to use the setup corresponding to that point. Hence, the partial setup strategy includes these other setup strategies as alternatives.
Conceptually, the search for improved solutions could include first investigating points A and B and choosing the one that dominates. If it is point A, then look for solutions with less changeover time, i.e., move toward the origin along the horizontal axis, that fall below the solid line in the figure. If it is point B that dominates, then look for solutions with more changeover time, i.e., move away from the origin along the horizontal axis, that fall below the dashed line.
The removal and replacement of feeders contributes to the changeover time of the machine. During this time the machine is idle and unproductive. Therefore, it makes sense to consider an objective that considers this time when planning the operation of the machine, namely, the minimization of the total product time. The total product time includes the changeover time to enable the machine to produce a product and the placement time required to assemble each PCB in the batch of that product.
With a unique setup strategy, the entire focus is on minimizing the board cycle time and, hence, the placement time. The changeover time is independent of the component-feeder assignment of the previous product, since every feeder is changed each time the machine is setup for a new product. With group setup, the main focus is on minimizing the changeover time. The changeover time is zero, or relatively small, for any products within a group. Once the components to be placed on the machine have been determined, the assignment of these components to feeders and the placement sequence for each individual product is determined to minimize the board cycle time (or placement time).
The partial setup strategy explicitly considers the tradeoff between changeover time and placement time. It uses the minimization of the total product time as the objective. Therefore, it can choose the unique setup if that is appropriate, e.g., if the batch size is very large. It can choose a minimum setup strategy, changing few, if any, feeders, if that is appropriate, e.g., very small batch sizes and short placement times. However, it is not locked into a particular strategy, but will adapt according to the circumstances. Because it considers the total product time, it is a more general model of the operational planning problem.
The partial setup strategy involves three major decisions: (1) determining the sequence in which to produce the products, (2) determining the component-feeder assignment to use for each product, and (3) determining the placement sequence to use for each product. The sequence of products is important because it determines what components will already be on the machine for each product. A complicating characteristic of this problem is that the changeover time for the next product depends not on its immediate predecessor, but all of the preceding products. This is partially due to the residual components that may be left on the machine after a product is produced even if those components are not needed on the next product. Therefore, the problem under consideration is more complicated than the sequence dependent setup problem. To clearly distinguish this case, we will refer to the current state of the machine. This state is the current assignment of components to feeders on the machine and depends on all of the preceding products and the component-feeder assignments used for those products. Therefore, this problem is not merely sequence dependent but state dependent.
This concept of state dependency is important in the context of replanning. When changes occur in the manufacturing system to warrant replanning, the best decisions depend on the current state of the system. In fact, all operational planning decisions are replanning decisions in that they must consider the initial state of the system. The system is always in some state, and there is a cost associated with changing that state. In the case of a single machine, the state can be easily represented as the current assignment of components to feeders. In a more complex system, the state may be more difficult to represent, but the basic idea is the same - replanning decisions must consider the current state of the system.
The state dependent changeover time for product i is defined as the time required to change the state of a machine (the component-feeder assignment) to enable it to process product i, given its current state. Note that this time depends on the current state of the machine as well as the desired state of the machine for processing product i. The state dependent placement time for product i is defined as the time required to process product i, given the state of the machine when product i is processed.
The problem of determining a good partial setup strategy can be represented by the following conceptual formulation:
Determine Product Sequence, Component-Feeder Assignments, and Placement Sequences
to
Minimize: Makespan
subject to: Component Placement Constraints
Component-Feeder Assignment Constraints
Product Sequencing Constraints
The objective is to minimize makespan for producing the set of products. The first set of constraints define the sequence of placements of the individual components on the printed circuit board. These constraints form an asymmetric traveling salesman problem (TSP). That is, given a component-feeder assignment for each product, minimizing the time required to place all the components on the PCB is equivalent to solving a TSP through each of the placement locations. The costs on each of the arcs is the time for the placement head to move from the previous placement location to the feeder containing the component needed for the next placement and then to the placement location on the PCB for this component. Clearly, these costs depend on the assignment of components to feeders; hence, the interdependence between these two sets of decisions.
The second set of constraints correspond to the component-feeder assignment constraints. The decision variables are the feeder slots that each component is assigned to. Each component needed for a product must be assigned to the machine, but only a single component type can reside in each feeder slot. The choice of component-feeder assignments depends on the previous state of the machine as this state will affect the changeover that is required. This assignment also impacts the placement sequence and resulting placement time for the product.
The final set of constraints are related to the sequencing of products on the machine. Each product must be produced and only one product can be produced at a time. The sequence of products determines the state of the machine for each subsequent product, which affects the component-feeder assignments and thus the component placement sequence.
The objectives of the experimental study are two-fold: (i) to demonstrate the adaptability of the partial setup strategy to varying demand and operating conditions; and (ii) to quantify the potential gains achievable with partial setups compared to other setup strategies. The following sections describe the solution procedures, test problem generation, and analysis of results.
In order to achieve the above objectives, we develop a simple heuristic solution procedure for partial setups and compare its performance with the unique, minimum, and group setup strategies. The solutions for unique and minimum setups are obtained as special cases of the partial setup problem. The group setup strategy requires the development of another heuristic. The procedures used for partial and group setup are important contributions of this paper. These two procedures are described in the following sections.
A simple heuristic for partial setup is induced by the conceptual formulation. The problem is decomposed into three interdependent subproblems; namely, component-feeder assignment, C(i), for each board i, placement sequence, P(i), for each board i, and product sequence, S, for all the boards. Let S(k) be the kth board in the sequence and n be the number of different boards. The determination of the parameters BITER and SITER is discussed later in the text. The procedure for the single-machine, partial-setup strategy (SPSS) is summarized in the following steps.
Procedure SPSS
End STEP 4
End STEP 2
End of STEP 1
End of Procedure SPSS
The determination of P(i) and C(i) in Steps 5 and 6 uses an iterative linear assignment problem (LAP)/TSP solution procedure that was inspired by the problem decomposition proposed in Drezner and Nof (1984). The main difference is that in the partial setup case the component-feeder assignment cost matrix explicitly considers the changeovers from the current machine state. Hence, when solving the assignment problem both the placement time and the changeover time are accounted for.
The assignment problem to find C(i) for each board is linear given the assumption of a single feeder slot for each component type. In our implementation, this LAP is solved using the shortest augmenting path algorithm by Jonker and Volgenant (1987). This efficient algorithm is O(F 3), where F is the number of slots on the feeder carriage.
The sequencing problems in Steps 5 and 8 can be solved as asymmetric traveling salesman problems. In Step 5, placement locations are represented as cities, the placement head is the salesperson, and the distance from one location to the next is the time required by the placement head to pick up components from the appropriate feeder slot and place them on the board. There are several optimal and heuristic procedures to solve the TSP (Laporte, 1992). In this implementation, we use the nearest-neighbor heuristic. While other TSP solution procedures may perform better, this improvement will benefit all of the solution strategies, and hence, we use the simple nearest-neighbor heuristic to determine the placement sequence. A tour is determined using each location as the starting city, and the shortest tour is selected. The procedure implemented runs in O(L3), where L is the number of placement locations on a board.
The sequence dependent changeover times, suv, in Step 7 can be determined in a straightforward manner once C(i) and P(i) are known. These are simply the time required to install and remove the feeders that are to be changed from one product to the next plus the placement time given the resulting component-feeder assignment.
In general, each iteration continues until the solution converges to a local optima, i.e., the same solution is obtained in successive iterations. In our tests, the procedures converge to local optima in less than three iterations in the vast majority of problems tested. In fact, the average number of iterations used in Steps 1 and 4 from all experimental runs is 2.297 and 1.197, respectively. Therefore, the stopping condition used in the experiments is a predetermined number of iterations, i.e., BITER = SITER = 3 iterations in Steps 1 and 4.
The proposed procedure can be used to generate both solutions using unique and minimum setup strategies. A solution equivalent to the unique setup strategy can be obtained using the proposed procedure by simply setting the changeover cost equal to zero. The procedure then attempts to minimize the board cycle time disregarding the time incurred in installing and removing feeders. The component-feeder assignment and placement sequence are found using the LAP/TSP heuristic. In Step 7, the arc costs will not be sequence dependent since the changeover time is zero, and therefore, any sequence can be used.
Similarly, a solution that minimizes feeder changeovers can be obtained using an appropriate large number as the changeover time. In this case, the procedure will only make the required component-feeder assignment changes and then attempt to minimize the placement time given this component-feeder assignment.
The group setup problem is solved by extending the LAP/TSP decomposition for the single board. The extension considers a "composite board" consisting of the superposition of all the boards in the same family - i.e., the x,y coordinates of all the placement locations for all the boards are superimposed and all required components are considered at one time (no repeated components are allowed). The TSP subproblem considers a series of tours, P(i), i = 1,…,n, one board type at a time, following an arbitrary sequence of boards and with all of the components on the feeder carriage. The cost of a solution is the time needed to install all required components in the feeder carriage plus the placement time associated with each board. The procedure iterates between the solution of these two subproblems until it converges to a local optimum or a predetermined number of iterations have been completed. This procedure appears to be similar to the one in Ammons et al. (1992) as described in McGinnis et al. (1992).
The procedure assumes that all boards will be produced in the same family or that families of boards have already been determined. Given the family, the procedure creates the "composite board," determines the component-feeder assignment for the family, and determines the component placement sequence for each board in the family.
If the composite board is denoted by H, the procedure for the single machine group setup strategy (SGSS) can be summarized as follows.
Procedure SGSS
End STEP 2
End of STEP 1
End of Procedure SGSS
The test problems are randomly generated to resemble industrial data obtained from two electronic assembly companies. This data provided the relative magnitudes and applicable ranges of the various parameters.
Given these basic dimensions, the x-y placement coordinates for each board were randomly sampled from uniform distributions as follows: x = 275 + UNIFORM(0, 150) and y = 120 + UNIFORM(0, 100). The feeder locations and home (0,0) position remained fixed for all experiments.
The 10 component types required per board were
selected from a total of 70 different component types. Problems
where multiple boards had a prespecified percent of common
components, %COMMON, were generated. Specifically,
consider the set C of components required for a given
board and C C the set of common components between
boards in the same random problem, where |C | = 
. The components in
set C were randomly sampled from a uniform distribution
UNIFORM(1, 70). The components in both C and C were
sampled anew, from UNIFORM(1,70), for each different board within
the same problem set. For each board, the components in C
were assigned to the first |C | placement locations and
the remaining 100-|C | locations were assigned a component
type randomly selected from C.
Figure 4. Machine/Board Configuration
Used In The Experiments
Nine experiments were conducted using three different problem sets. Each problem set consisted of 20 problem instances. Experiments 1-3 use single board problems generated considering an initial machine state. Experiments 4-6 use 5-board problems generated to have at least 50% common components. Finally, Experiments 7-9 use 5-board problems generated to have 100% common components.
For the single board problems, 50% of the feeder slots are empty in the initial machine state. Further, 50% of the component types initially on the feeder carriage are required by the board type under consideration. The initial component-feeder assignment is random (i.e., the component types needed for the board are not necessarily in the required feeder slot for the board to be produced). In the multiple board problems, the initial machine state is assumed to have all empty feeders.
The scenarios tested represent a wide variety of production settings. Runs were made for different levels of changeover time per feeder and different ratios of batch size to head velocity. It should be noted that these two parameters determine the relative weight of changeover time with respect to placement time; i.e., total product time = (changeover time per feeder)*(number of feeders installed or removed) + (batch size/head velocity) * (placement distance per board). The changeover time per feeder values used are 0, 30, 60, 90, 120, and 150 seconds to install or remove a feeder. Typical values in the companies we have observed range from 30 to 60 seconds. The batch size/head velocity ratios used are 1.667, 0.500, and 0.167, corresponding to approximately 20 hours, 6 hours, and 2 hours of placement time per batch, respectively.
All the experiments were conducted for all batch size/head velocity and changeover time per feeder combinations. The total number of SPSS runs is 4,320 (9 experiments, 20 problems, (6+2) levels of changeover time, and 3 levels of batch size/velocity ratio). The 2 additional levels for changeover time were at 1 and 10,000 for unique and minimum setup, respectively. Only 40 runs (2 sets of 20 multiple board problems) were required with SGSS since the solution of this procedure is independent of the changeover time and batch size/velocity ratio values used; i.e., given the component-feeder assignment and placement sequences we could compute the appropriate objective function for each different scenario.
The main characteristics of the nine experiments are summarized in Table 1. Note that the percentage of components in common for the single board experiments (i.e., 1, 2, and 3) is with respect to the initial machine state.Table 1. Main Parameters for the Experiments
| Experiment Number |
Number of Boards |
Batch Size / Velocity Ratio |
% Common Components |
| 1 | 1 | 1.667 | 50 |
| 2 | 1 | 0.500 | 50 |
| 3 | 1 | 0.167 | 50 |
| 4 | 5 | 1.667 | 50 |
| 5 | 5 | 0.500 | 50 |
| 6 | 5 | 0.167 | 50 |
| 7 | 5 | 1.667 | 100 |
| 8 | 5 | 0.500 | 100 |
| 9 | 5 | 0.167 | 100 |
The results for experiments 1-9 are summarized in Tables 2 and 3 and in Figures 5 to 13. The tables show the average makespan and corresponding standard error (in seconds) for various levels of the time required to install or remove a feeder. Each average is taken from running 20 different problems. Different curves in the figures correspond to the results obtained using partial, unique, minimum, and group setup strategies.Table 2. Summary of Experimental Results for Single Board Problems
Table 3. Summary of Experimental
Results for Multiple Board Problems
Figure 5. Results of Experiment 1
(# boards = 1; batch/vel. = 1.667; % common
= 50)
Figure 6. Results of Experiment 2
(# boards = 1; batch/vel. = 0.500; % common
= 50)
Figure 7. Results of Experiment 3
(# boards = 1; batch/vel. = 0.167; % common
= 50)
Figure 8. Results of Experiment 4
(# boards = 5; batch/vel. = 1.667; % common
= 50)
Figure 9. Results of Experiment 5
(# boards = 5; batch/vel. = 0.500; % common
= 50)
Figure 10. Results of Experiment 6
(# boards = 5; batch/vel. = 0.167; % common
= 50)
Figure 11. Results of Experiment 7
(# boards = 5; batch/vel. = 1.667; % common
= 100)
Figure 12. Results of Experiment 8
(# boards = 5; batch/vel. = 0.500; % common
= 100)
Figure 13. Results of Experiment 9
(# boards = 5; batch/vel. = 0.167; % common
= 100)
In all cases, the procedure using the partial setups either dominates or closely tracks other dominating setup strategies. This is an important contribution of this paper.
Consider for instance the plot for experiment 5 shown in Figure 9. It represents a scenario where the run times per batch of a given board type is 6 hours. The curve associated with unique setup crosses the curves associated with group and minimum setup. This plot clearly shows potential losses if a company uses a fixed setup strategy - either unique, group, or minimum. The losses can range from minutes to several hours in the problems tested. This plot also shows how a company using the partial setup strategy will "adapt" to changing conditions yielding improved efficiencies over the other setup strategies.
As expected, the unique setup strategy tends to perform better in environments where the placement time is more significant than the changeover time - i.e., large batch size/head velocity ratio and/or small feeder installation and removal times. This result is evident in the tables and figures where the performance of unique setup deteriorates as the batch size/head velocity ratio decreases. Furthermore, as changeover times become predominant, this strategy is dominated by the minimum setup strategy. The partial setup strategy is able to perform effectively under all scenarios by concentrating on the overall makespan instead of only on changeover time or only on placement time.
The group setup strategy dominates the minimum setup strategy because it attempts to minimize the placement time taking all the boards into consideration in addition to minimizing the number of feeder changes. The minimum setup strategy only considers the latter. As expected, this dominance attenuates as the relative weight of placement time is decreased. Interestingly, this strength of group setups is also a weakness when compared to partial setups since the strategy of "installing all the components at once" need not be the most appropriate one.
In this paper, we propose partial setups as a general setup management strategy for electronic component placement machines that includes other common setup strategies found in the literature and in practice as special cases. We suggest a simple heuristic procedure for finding partial setup solutions and compare its performance with other commonly used setup strategies.
The electronics industry is a major part of modern manufacturing. Efficient operation of printed circuit card assembly systems is vital for maintaining competitiveness in a global marketplace. The concept of a partial setup strategy represents a new method of operating PCB assembly systems that has the potential to greatly increase the system efficiency. In addition, this strategy is flexible, in that it adapts the setup management strategy to the production situation. As requirements change, the partial setup strategy adapts to these changes. Several companies have already recognized this mode of operation as having many potential benefits. However, they lacked the tools to compare its performance with other strategies or to determine the operational plans to follow using a partial setup strategy. The work in this paper is a step toward providing an increased understanding of partial setups and a set of tools for operating in this mode.
Furthermore, a partial setup strategy is needed for replanning purposes since it considers the impact of schedule changes given an initial system state. Encouraging experimental results suggest significant gains at the single machine level. Future work is currently being pursued on two fronts. One is to improve the solution procedures presented in this paper for finding partial setups. There is still considerable work in investigating more sophisticated procedures for solving the partial setup planning problem. Second is to extend the replanning concept from the single machine case to the line level case. Peters and Subramanian (1995) have done some preliminary work in this area. However, there are many complicating issues at the line level that need to be addressed and resolved. Moving the partial setup approach to replanning up to the line level may represent some of the largest potential gains for industry.
We thank Mr. Salvador Issa and Mr. David Shaddock at Rockwell International (El Paso, Texas) for their technical advice and support to this project. We also thank Westinghouse Corp. (College Station, Texas) for their long-term support and assistance in carrying out this research. We thank Professor Volgenant for providing the code to solve the LAP problem and Mr. Yi-Ping Chen for coding the group setup procedure. Finally, we thank the anonymous referees whose comments helped to improve this paper.
Ammons, J.C., L.F. McGinnis, and C.A. Tovey, 1991, "Process Planning for Surface Mount," Proceedings SMI '91, San Jose, CA, August.
Ammons, J.C., M. Carlyle, L. Cranmer, G.W. Depuy, K.P. Ellis, L.F. McGinnis, C.A. Tovey, and H. Xu, 1992, "Workstation Optimization in Printed Circuit Card Assembly," Working Paper 92-03-30, Manufacturing Research Center, Georgia Institute of Technology, Atlanta, GA 30332.
Askin, R.G., M. Dror, and A.J. Vakharia, 1994, "Printed Circuit Board Scheduling and Component Loading in a Multimachine, Openshop Manufacturing Cell," Naval Research Logistics, 41, 5, 587-608.
Askin, R.G. and C.R. Standridge, 1993, Modeling and Analysis of Manufacturing Systems, John Wiley & Sons, Inc., New York.
Ball, M.O. and M.J. Magazine, 1988, "Sequencing of Insertions in Printed Circuit Board Assemblies," Operations Research, 36, 192-201.
Bard, J.F., R.W. Clayton, and T.A. Feo, 1989, "Optimizing Machine Setup and Component Insertion in Printed Circuit Board Assembly," Working Paper, Operations Research Group, College of Engineering, University of Texas, June.
Chan, D. and D. Mercier, 1989, "IC Insertion: An Application of the Traveling Salesman Problem," International Journal of Production Research, 27, 10, 1837-1841.
Crama, Y., A.W.J. Kolen, A.G. Oerlemans, and F.C.R. Spieksma, 1990, "Throughput Rate Optimization in the Automated Assembly of Printed Circuit Boards," Annals of Operations Research, 26, 455-480.
Drezner Z. and S.Y. Nof, 1984, "On Optimizing Bin Picking and Insertion Plans for Assembly Robots," IIE Transactions, Vol. 16, No. 3, 262-270.
Gavish, B. and A. Seidman, 1987, "Printed Circuit Boards Assembly Automation - Formulations and Algorithms," Proceedings of IXth ICPR, Cincinnati, Ohio, August.
Grotzinger, S., 1988, "Positioning for a Dual Delivery Placement Machine," IBM Research Division, T.J. Watson Research Center, Yorktown Heights, New York.
Jonker R. and A. Volgenant, 1987, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing, 38, 325-340.
Laporte, G., 1992, "The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms," European Journal of Operational Research, 59, 231-247.
Lofgren, C.B. and L.F. McGinnis, 1986, "Dynamic Scheduling for Flexible Printed Circuit Card Assembly," Proceedings IEEE Systems, Man, and Cybernetics, Atlanta, GA.
McGinnis, L.F., J.C. Ammons, M. Carlyle, L. Cranmer, G.W. Depuy, K.P. Ellis, C.A. Tovey, and H. Xu, 1992, "Automated Process Planning for Printed Circuit Card Assembly," IIE Transactions, 24, 4, 18-30.
Peters, B.A. and G.S. Subramanian, 1995, "Analysis of Partial Setup Strategies for Solving the Operational Planning Problem in Parallel Machine Electronic Assembly Systems," International Journal of Production Research, to appear.
Sadiq, M., T.L. Landers, and G.D. Taylor, 1993, "A Heuristic Algorithm for Minimizing Total Production Time for a Sequence of Jobs on a Surface Mount Placement Machine," International Journal of Production Research, 31, 6, 1327-1341.
Tang, C.S. and E.V. Denardo, 1988, "Models Arising from a Flexible Manufacturing Machine, Part I: Minimization of the Number of Tool Switches," Operations Research, 36, 5, 767-777.