ARTICLE IN PRESS

Computers & Operations Research 37 (2010) 1488–1499

Contents lists available at ScienceDirect

Computers & Operations Research

0305-05

doi:10.1

� Corr

E-m

journal homepage: www.elsevier.com/locate/caor

Construction of component tapes for radial placement machines

Csaba Raduly-Baka a, Timo Knuutila b,�, Mika Johnsson c, Olli S. Nevalainen b

a Elcoteq Design Center Oy, Joensuunkatu 13, FIN-24100 Salo, Finlandb Department of Information Technology and TUCS, University of Turku, FIN-20014 Turku, Finlandc Valor Computerized Systems (Finland) Oy, Ruukinkatu 2, 20450 Turku, Finland

a r t i c l e i n f o

Available online 13 November 2009

Keywords:

Printed circuit boards

Optimization

Flexible manufacturing

Heuristics

Combinatorial optimization

48/$ - see front matter & 2009 Elsevier Ltd. A

016/j.cor.2009.11.005

esponding author.

ail address: knuutila@it.utu.fi (T. Knuutila).

a b s t r a c t

With a great variation of products, PCB assembling machines must be reconfigured often, but at the

same time the efficiency of the assembly process should be kept high. In this paper we consider PCB

assembly machines of the radial type, which are used for manufacturing robust electronics devices. In

this machine type the components are brought to the assembly point by the means of a single

component tape, and a robotic arm places them onto a bare PCB one at a time. The component tape is

constructed on-line by a separate feeder unit (sequencer) composed of a set of slots storing component

reels of various types. While the insertion of components to the tape does not normally delay their

placements on the PCB, certain (broad) components delay the processing due to the operation principle

of the sequencer, thus increasing the manufacturing time. We study the problem of assigning

components to the sequencer in such a way that tape construction delay is minimized, give an integer

programming formulation of the problem, and present an optimization algorithm to reduce the

component insertion time caused by slow components. The results of this optimization algorithm show

considerable improvement against a simple feeder assignment, in case of tape instances containing

repeating sequences of components.

& 2009 Elsevier Ltd. All rights reserved.

1. Introduction

In electronics manufacturing, flexibility has become a keyattribute of the production process. Manufacturing efficientlyspecific products with specific machines has been researchedextensively in literature. Along with efficiency, more attention hasbeen paid to the flexibility of production in a situation, where thetype of products changes frequently and a time consumingmachine setup is required when changing the product batch[1–3,5,6]. The flexibility and efficiency of the machine configura-tion has a notable impact on the joint manufacturing costs of theproducts [7–9,32].

In this paper we study the control of a specific electronicsmanufacturing machine used in PCB assembly. In so-called radial

machines, a single input tape is used to bring the electroniccomponents from a component feeder to the assembly point,where a robotic head places them on the PCB. This is a traditionalmachine type which originates from the era of through-holefixation technique from 1980s. It is, however, still actual (RAD5and RAD8 of Universal Instruments, for example) in cases where

ll rights reserved.

the product should be more robust and the power consumption isrelatively high, like in amplifiers, TV-sets or control units.

1.1. Radial placement machines

In this machine model the topology of the PCB and otherrestrictions specific to the PCB type and the robotic placement

head determine the order in which components (i.e. varioustypes) are arranged on the component input tape (called simply thetape) of the placement machine and the components arrive in thesame order to the assembly point. The components are placedonto the tape by a sequencer (called also feeder unit), whichcomprises a linear array of feeder slots. The different componentsare stored in component (tape) reels, which are assigned stationaryto the slots of the sequencer. Each individual reel contains asupply of identical components. Duplicate component reels of agiven component type may be installed to the sequencer forefficiency reasons.

The tape (used by the placement head) moves (in steps ofconstant length and time) under the sequencer, and when propertape locations are aligned with feeder slots containing therequired component types, the feeder places those componentsonto the tape. Due to the physical dimensions of the componentreels, the space between two adjacent feeder slots is twice the

ARTICLE IN PRESS

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–1499 1489

space between two adjacent tape locations (see Fig. 1). Because ofthis, only every second tape location can be inserted withcomponents at a given moment. These placement operationsfrom the sequencer to the tape should respect the final ordering ofperforming the actual component placements to PCB. As compo-nents are placed into the tape, some component types (so-calledbroad components, or double pitch components) cause the tapemovement to be delayed by a specific amount of time.

The design of the actual placement machine is rather simple.There is a stationary pick-up and place head, which takes acomponent from the input tape and places it to the PCB. The PCBholding table is movable in the ðx; yÞ- plane and it can be rotatedin steps of p=2 to get the proper final orientation for the insertedcomponent (which is in itself always introduced in the same fixeddirection). The operations of the placement machine and thesequencer are synchronized so that one has to wait for the sloweroperation to be completed.

The machine operates in cycles where each cycle consists of apick-up and placement operation. Here, the placement head picksup an element from the component tape and simultaneously thePCB holding table is moved so that the proper insertion point ofthe new component is beneath the placement head and the PCBtable is eventually rotated if the component orientation demandsit. After this the component will be placed on the PCB.

There are numerous aspects where this kind of manufacturingsetup can be optimized. The order of the components on the tapemust be determined for each PCB type properly. The capabilitiesof the placement head should be taken into account: certaincomponent orders are not allowed due to the dimensions of thehead. Then, assuming a given component order, another aspect foroptimization is the content of the sequencer, namely how toassign components into the slots of the sequencer, in order toallow the placement of multiple broad components to the tape inthe same time. A third aspect of optimization is the actual feeder-to-tape placement process. In this step, multiple feeder slots maybe assigned to the same component type, and one should decideat which point to insert these components from the sequencer tothe tape of the robotic head.

In these types of machines the components are inserted on thetape either without extra delay or with a fixed delay of the tapemovement, depending on the type (width) of the component. Onecan generalize this problem into an n-pitch problem by definingan arbitrary number of delay times. Such a problem would, ofcourse, be at least as complex as the practical (2-pitch) feederassignment problem (see Section 4). In the present paper we focuson the 2-pitch case, which is present in the control of radialmachine sequencers. We will also show that the heuristicalgorithm introduced by this paper can be easily adapted to then-pitch case.

1.2. Previous research

There are slightly differing classifications of componentplacement machines, see for example Moyer and Gupta [20],Tirpak et al. [21], or Ayob and Kendall [19].

In their recent survey Ayob and Kendall [19] (see also [22])classified the surface mount device (SMD) placement machines tofive categories. These include dual-delivery, multi-station, turret-type, multi-head and pick-and-place machines. Research on thecontrol of these machine types has been very active during thelast 20 years. While the operation principles of different machinetypes differ at critical points, techniques used for optimizing thecontrol of placement machines are similar in most cases. Wetherefore briefly characterize the different machine types and

mention few references (older and recent ones) for research onthem.

Dual-delivery machines have a head and a feeder unit on bothsides of the machine, see Ahmadi et al. [24], Wilhelm et al. [37]and Choudhury [25] for control optimization of this machine type.

Multi-station placement machines contain several identicalmachine modules connected to each other with a conveyor. Themodules work in parallel and each of them perform a subtask forthe PCB, see Grunow et al. [27] and Csaszar et al. [26].Reconfigurable versions of this machine type have recently gainedtheir popularity.

Rotary turrent machines have a revolver head with multiplenozzles. The head is at a fixed position and the PCB holding boardand the linearly organized feeder unit are moveable, see e.g.Crama et al. [28] and Ho et al. [29]. While the machine type isextremely fast (called also ‘‘chip shooter’’), the large mass forcescause mechanical stress and the physical dimensions of themachines tend to be rather large.

Multi-head placement machines differ from the rotary turretmachines in the sense that their placement head is movable intwo or one dimension. In a common design of the machine typePCB and feeders are stationary and head moves along two gantries(so-called gantry machines), the head may be of revolver type or alinear array of spindles, see Van Laarhoven and Zijm [30], Du andLu [31], Sun and Lee [33], and Park and Kim [34]. The machine isnowadays popular due to its flexibility and accuracy.

Sequential pick-and-place machines have only one nozzle intheir placement head, and the PCB table and feeder unit are eitherstationary or movable, see e.g. Ball and Magazine [38], Leipala andNevalainen [17,18], Fu and Su [35] and Ayob and Kendall [36] forliterature.

Radial placement machines belong to the class of sequentialpick-and-place machines.

Ball and Magazine [38] model the placement sequencingproblem of pick-and-place machines as a directed postmanproblem, whereas Leipala and Nevalainen [17] treat it as a TSP-problem and quadratic assignment problem. Kumar and Li [39]used linear programming for feeder assignment and placementsequencing. They improve the initial machine control heuristi-cally using a number of efficient heuristics (local search with 2-and 3-changes).

Recently, modern metaheuristics, among others evolutionaryalgorithms, tabu search, simulated annealing, swarm optimiza-tion have been successfully used to solve several differentmachine control problems. An advantage of these methods istheir ability to consider the feeder setup and placement sequen-cing problems jointly. Then, the objective function, which is mostcommonly the total manufacturing time per PCB, is expressed as afunction depending on feeder assignment and placement se-quence. The value of the objective is then calculated by a functionwhich abstracts the operation of the machine. The level of theabstraction strongly influences the quality of the solution and alsothe need for computing time.

As an example of this kind of approach, Fu and Su [35] applieda genetic algorithm, simulated annealing and tabu search to solvethe joint control problem of a pick-and-place machine. Thecurrent trend with PCB component placement problems, and withhard combinatorial problems in general, is the hybridization of ametaheuristics with problem specific local search. As an othertrend, there is the increase of the number of research articlesusing exact solution methods. While the theoretical computa-tional complexity puts limits to our ability to find exact solutionsto large problem instances, there are instances of realistic size,which have been solved optimally by recent efficient problemsolvers; c.f. for example traveling salesman problems for jobgrouping problems [23].

ARTICLE IN PRESS

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–14991490

1.3. Feeder construction

In this research we focus on the assignment of component reels

into the feeder slots and the feeder-to-tape placement process of thecomponents performed by the sequencer.1

While we concentrate on the sequencer optimization, we notethat problems occurring in this task are closely related tooptimization of nozzle change operations and component pickupoperations of multi-head machines.

In the machine type studied here, the component placementtime is determined by the width of the component, also called thecomponent pitch. Components of a narrow pitch are inserted intothe tape as an interaction of two-step process:

1.

pro

bot

the

mo

advance component tape and unwind component feeder reelin parallel;

2.

place component to tape and pick-up component to placementhead in parallel.

Thus narrow components are inserted at the same speed as thetape moves (in optimal case). It is also possible to place multiplenarrow pitch components simultaneously, but that will not haveany positive effect on the tape movement delay, because allcomponents have to pass the placement head.

Double pitch components also occupy one feeder slot each, buttheir placement demands an extra processing step from thesequencer. During this step the component tape is stopped andthe placement head cannot thus pick up a new component.2 Theextra time of the double pitch components does not, however,depend on how many such components are brought from thesequencer to the tape in parallel. Placing one double pitchcomponent causes the same amount of delay as a simultaneousplacement of, say, three double pitch components. If multiplefeeder slots align with correct tape locations at the same time (ofthe tape stop position), so that the slots contain the componentswhich need to be placed just into these tape locations, placementsto these locations can be done at the same time. We can thusdecrease the potential delay caused by the sequencer by creatinga feeder slot assignment where such alignment scenarios arefrequent. It is therefore natural to take as the optimizationobjective the minimization of the number of the extra tapestoppings.

In this research it is assumed that the component ordering on

the tape has been already established by some other decision process.The assumption is, at least partly, motivated by the precedenceconstraints of the placements originating from physical dimen-sions of the components and the placement head. Because of theirdimensions and location, certain component orders cannot bemanaged by the machine, since the placement head mayaccidentally touch and damage already placed components.

We introduce an algorithm to address the feeder assignmentproblem of assigning double pitch component types to the feederslots. The algorithm selects frequently occurring patterns ofcomponent types on the component input tape and tries toreproduce these patterns in the sequencer. The algorithm takesinto account the fact that the feeder slot size is such that at agiven moment only every second tape location is aligned with afeeder slot. A natural assumption is that the size of the sequencer(the total number of feeder slots) is much smaller than the length

1 The problem was originally proposed by a developer of PCB control

grams (Valor Finland), who has noted that sequencer operations form a

tleneck in the operation of RAD5-machines.2 The reason for extra stop is that double pitch components are oriented on

component feeder tapes the long side aligned with the tape direction and the

vements of the sequencer are synchronized in steps of ‘‘one pitch movements’’.

of the tape to be constructed. An other motivation for fixedcomponent ordering is a hierarchical view of the machine control;for each particular component placement ordering we have tooptimize the sequencer operations.

Having the feeder slots assigned with the necessary compo-nent types, the sequencer inserts the necessary components ontothe tape as the tape is moved stopwise under the feeder. Becausemultiple slots may contain the same component type, it must bedetermined at which feeder-to-tape alignment these multiplyoccurring components are inserted. We show that this problem isbasically the minimum set cover problem [14], and a well knownapproximation algorithm used for the minimum set cover problemcan be used in tape construction also.

We test the feeder assignment algorithm on practical dataincluding single pitch and double pitch components. The resultsare compared to those of a brute force algorithm and a simpler(naive) heuristics. In addition to the above practical contributionswe give an integer formulation to the feeder assignment problemand discuss its relation to the turnpike problem [10]. We showthat the later problem is reducible (in P-time) to the feederassignment problem.

2. The feeder assignment and component tape constructionproblem

In this section we formulate the feeder assignment and

component tape construction (FACTC) problem. The followingassumptions are made:

1.

The order of the components on the tape of the placementmachine is fixed.

2.

A sequencer (feeder unit) is used to insert the componentsonto the tape, in the specified order.

3.

One feeder slot of the sequencer can contain components of asingle type, only. Some of the slots may be unused.

4.

Component types can be of single or double pitch. 5. The insertion of a double pitch component onto the tape blocks

the tape movement and causes a delay of a constant time ðcÞ inthe operation of the component assembly robot.

6.

The startup and shutdown times of the component assemblyand tape construction process are considered fixed.

7.

The distance between two neighboring feeder slots is twice thedistance between two neighboring tape locations, so at anygiven moment, the sequencer can insert a component ontoevery second tape location only.

Fig. 1 illustrates how the tape moves under the sequencer, andhow the feeder slots are aligned with tape locations at a givenmoment. The tape moves stepwise leftwards, and at each step thesequencer can insert into the tape locations that are under eachslot. Since there is only one component type in a slot, only thoseslots can make an insertion, which contain the component typemarked for the tape location aligned with the slot.

The feeder assignment has an effect on the delay of the tapemovement caused by the insertions of the double pitch compo-nents. Fig. 2 illustrates a feeder configuration with three differentdouble pitch components. In this example, the tape movement isdelayed by 3c, since each component is inserted separately. Thisdelay can be reduced by inserting several double pitchcomponents in parallel. This can be done by placing the doublepitch components in such feeder slots, that they alignsimultaneously to their intended tape positions, see Fig. 3. Inthis case the three components are inserted in one step, and thedelay caused by these insertions is reduced from 3c to c.

ARTICLE IN PRESS

Sequencer

Feeder Slot 1

Component reels

Component input tape

Fig. 1. Component input tape moving leftwards under the sequencer. Every second input tape location is under a feeder slot. Component reels are connected to the

feeder slots.

1

1 2 3

2 3

Fig. 2. When feeder slots of double pitch components are not properly aligned, each component insertion causes a separate delay. (The numbers on the tape and the

sequencer indicate the component types.)

1

1 2 3

2 3

Fig. 3. If feeder slots and tape positions are properly aligned, three double pitch components can be inserted together causing a single delay.

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–1499 1491

The feeder assignment may be disadvantageous for a giventape configuration, since there may be a weak match between thepatterns of double pitch components of the tape and sequencer.For example, the sequencer may contain an allocation whichallows parallel placement of certain components, but does notcontain the possibility of performing another more frequentparallel placement which appears periodically in the tape.

3 Some frequently used components may be fed by two reels for practical

reason.

2.1. Notation

In the feeder assignment problem we use the followingnotations:

l the total number of components to be inserted in thetape;

n the number of different component types;N¼ f1; . . . ;ng the set of component types;t ¼ ft1; t2; . . . ; tlg the components on the tape from left to right,

where tiAN is some component type;w ¼ fw1;w2; . . . ;wng the pitches of the component types, where

wi is either 0 indicating a narrow component or 1indicating a double pitch component;

s the number of slots in the feeder;f ¼ ff1; f2; . . . ; fsg a feeder assignment, where fiAN [ 0 specifies

the component type in slot i. If fi ¼ 0, no component typeis assigned to that slot;

p the number of double pitch component types, prn. Thevalue of p can be calculated by summing up values of 1in w;

m the number of slots in the feeder used for double pitchcomponents, prmr ðs-nþpÞ. The value of m is an inputparameter to our problem;

L¼ fi1; i2; . . . ; ihg where ijA1; . . . ; l give the locations of the doublepitch components on the tape (i.e. for iA1; . . . ; l: iAL ifand only if wti

¼ 1), and h is the number of double pitchcomponents to be placed into the tape.

The feeder must accommodate at least one instance of eachcomponent type (as a minimum requirement). It is typical thatthe size of the feeder is larger than the number of componenttypes and it is possible to assign multiple slots with the samecomponent type. Denote by f an assignment giving the minimaldelay in tape construction. As mentioned before, it is supposedthat the position of single pitch components in the feeder does notcause any tape construction delay. Nevertheless, we may stillwant to allow more feeder slots for single pitch components thanthe minimum necessary n-p slots.3 The input parameter m

specifies the number of slots used for wide components.

2.2. Integer programming formulation

We next present an integer programming formulation for theunified problem of feeder assignment and tape construction(FACTC). In this formulation one can (as observed in the beginningof Section 2) omit the further consideration of the n-p single pitchcomponents and only look for the double pitch components.Single pitch components are supposed to occupy (in some order)

ARTICLE IN PRESS

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–14991492

the feeder slots remaining free after allocating the double pitchcomponents.

We must account for the practical aspect of the feeder, whereat any given moment; the sequencer can insert a component ontoevery second tape location only. This can be modeled by using alarger feeder of size s0 ¼ 2 � s-1 and forbidding component assign-ment to every second feeder slot.

We may assume, without the loss of generality, that types1; . . . ; p are the 2-pitch components.

Let

gij ¼1 if i is odd and feeder slot icontains 2� pitch component type j

0 otherwise

�

where we limit the use of feeder slots to slots of odd locations, sothat proper spacing is maintained.

A legal feeder assignment is defined by the followingconstraints.

For each double pitch component type, there must be at leastone slot assigned with that component type:

ðiÞ for all jA1; . . . ;p;Xs0

i ¼ 1

gijZ1

The number of slots used for double pitch components is m:

ðiiÞXs0

i ¼ 1

Xp

j ¼ 1

gij ¼m

A slot can contain at most one double pitch component:

ðiiiÞXp

j ¼ 1

gijr1 for all iA1; . . . ; s0

2.2.1. The tape construction step

Constants (i)–(iii) define a legal feeder assignment for thedouble pitch components. In order to determine an optimal feeder

assignment, we must also consider the tape construction stepsused to insert the components from the feeder into the movingtape. Insertion of a component from feeder to tape can occurwhen a feeder location with an assigned component type isaligned with a tape location assigned for the same componenttype. There are at most lþs0 feeder-to-tape alignments, that is,there are lþs0 steps from the initial to the final position of the tape(see Fig. 4). Observe, that at the initial and final positions, aninsertion to the tape does not occur, and insertion of a doublepitch component is feasible only at a subset of these positions.

At each feeder-to-tape alignment, a given tape location may ormay not be inserted with a component, depending on whether thealigned slot contains a proper component type, and whether insertionat that alignment leads to an optimal solution (i.e. minimal delay).

Let tA ½k; . . . ; s0 þk-1� denote a feeder-to-tape alignment. Theso-called feeder-to-tape alignment event line visualizes the orien-tation of the sequencer in relation to the tape (see Fig. 4). Theevent line includes 2lþs0 feeder-to-tape alignment positionswhich are indexed from left to right as 1;2; . . . ;2lþs0. Let skt

0

denote the position of the k th tape element on the event line atmoment t. Then we have skt

0 ¼ lþs0 þk-t.Let ak denote the component type at location k on the tape. For

alignment t, the insertion of a component to location k of the tape

Event line (2l+s)

(l)

(s)

Feeder (s)

Tape at final position (l)

Fig. 4. The tape moves under the feeder from an initial to a fi

from feeder slot i (numbered from left to right as 1;2; . . . ; s0) ispossible if:

(a)

nal p

the feeder slot i contains the required component type:

ðivÞ giak¼ 1

and

(b) the tape location k is aligned with the feeder slot i:

ðvÞ Skt ¼ lþ i

Formula (v) gives us lþs0 þk-t¼ lþ i from which it followsi¼ s0 þk-t (when t¼ 1, the first tape location ðk¼ 1Þ is alignedwith the last feeder slot ði¼ s0Þ and the tape moves leftwards (seeFig. 4), for t¼ s0, the first tape location ðk¼ 1Þ is aligned with thefirst feeder slot i¼ 1). Of course k could be out of boundsðkA1; . . . ; lÞ meaning that there is no tape under feeder slot i.

Let qkt denote the decision variable whether the component attape location k is inserted at alignment t:

qkt ¼1 a 2� pitch component is inserted to tape location k at alignment t

0 otherwise

�

Then for all kA1; . . . ; l:

ðviÞXlþ s0

t ¼ 1

qkt ¼ 1

meaning that a tape location is inserted with a component exactlyat one alignment. Since the insertion can occur only if both (iv)and (v) hold at moment t, we have

ðviiÞ qkt rgiakwhere i¼ s0 þk-t

Thus, the values of qkt give both the feeder assignment and thecomponent tape construction sequence.

2.2.2. Objective function

We want to minimize the number of extra stops (delays) of thetape caused by insertions of the double pitch components. For anygiven tape alignment t, ð1-qktÞ is 0 if a double pitch component isinserted to the k th location of the tape, and 1 if insertion of thedouble pitch component does not occur. For an alignment t theproduct

ðviiiÞYkA L

ð1-qktÞ

is 1 only when no insertion of a double pitch component occurredat that alignment. At any given alignment t, the tape either moveson or stops so that component insertion can occur. Thereforeminimizing the number of stops means maximizing the numberof alignments where no double pitch components are inserted.The total number of alignments with no double pitch insertions isthe sum of the above product:

ðixÞXlþ s0

t ¼ 1

YkAL

ð1-qktÞ

Tape at initial position (l)

osition, defining a feeder/tape alignment event line.

ARTICLE IN PRESS

4 We define the decision version of FACTC to decide whether there is a solution

of the FACTC optimization problem such that the number of double pitch

placement stops is at most a given constant R.

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–1499 1493

The objective function to minimize in the combined problemof feeder assignment and tape construction is then

ðxÞ lþs0-Xlþ s0

t ¼ 1

YkAL

ð1-qktÞ

that is, because there are a fixed ðlþs0Þ alignments wherecomponent insertions can occur, so maximizing (ix) is equivalentto minimizing (x). (Note that one could easily modify the aboveformulation to minimize the total number of times componentsare moved from feeder slots to the tape (i.e. maximization ofparallelism). Then, qkt- settings should be solved for all k-indexesby extending the product in ðxÞ for indexes kA ½1; l�.)

By introducing a new variable zt , the above objective functionof the FACTC problem can be linearized to the form

ðxiÞXlþ s0

t ¼ 1

zt

with the following constraint on zt:

ðxiiÞ zt rð1-qktÞ for all kAL; tA ½1::lþs0�

3. Brute force search

The feeder assignment and component tape constructionproblem can be solved by the means of a brute force searchalgorithm as follows.

3.1. Brute force search for feeder assignments

The brute force algorithm for the feeder assignment problem

(called brute force for feeder assignment or BFFA) builds all possiblefeeder configurations, evaluates the tape construction delay foreach of them, and selects the one resulting in the smallest numberof tape movement delays. The complexity of the brute forceapproach depends on the feeder size s and the number ofcomponent types n. As mentioned, the positions of the singlepitch component types are those remaining free after assigningthe double pitch components.

The BFFA algorithm enumerates all possible ways to store the p

double pitch components in m slots. There are ð smÞ possible slot

subsets of size m in the feeder, and each of them can be populatedin pm different ways with p double pitch component types. Someof these ways will be unfeasible, since a valid feeder assignmentmust contain components of all types. In order to reduce thenumber of such assignments, we separate the m slots into twogroups, one having p slots and containing one double pitchcomponent of each type, and the other having m-p slots contain-ing any combination of double pitch components. The first groupgenerates p! possible configurations and the second group pm-p

possible configurations. Each configuration of these two groups isthen combined into m slots. Because there are ðmp Þ possible ways tocombine these two groups, the number of slot assignments of thebrute force algorithm is

p! � pm-p �m

p

!�

s

m

� �

At each step, the brute force algorithm calls to the componenttape construction algorithm to evaluate the feeder configuration,and stores the best feeder configuration found.

In a typical PCB, the number of different component types canbe large (for example n¼ 60 as a small case), and more than halfon these can be of double pitch type (i.e. p¼ 30). The size of thesequencer is also large enough to accommodate multiple copies ofcomponents (i.e. s¼ 120). In order to run the brute force

algorithm with m¼ 60 (maximally two double pitch componentsof each type), the number of possibilities to be checked becomestoo large for practical computation (approximately 10128). Thismotivates the search of a heuristic, which may not provide theoptimal result but runs in practical time.

3.2. Brute force search for tape construction

The component tape construction should be done in optimalway for each feeder assignment. This problem can also beaddressed with a brute force algorithm (lets call it brute force

for tape construction or BFTC). The tape moves leftwards under thefeeder (see Fig. 5), and at a specific alignment the feeder inserts aset of (one or more) double pitch components onto the tape. Theposition where the insertion is performed may influence theforthcoming choices and the total number of double pitchinsertion operations (see Fig. 6 where it is beneficial topostpone the insertion of the leftmost component of type ‘‘1’’, tothe alignment shown).

As mentioned above, the brute force algorithm tries out everypossible feeder-to-tape alignment and for every alignment all thepossible subsequent alignments. This leads often to mr differentpossibilities, where

r¼Xl

i ¼ 1

wti

is the number of double pitch component types inserted into thetape (wti

is the pitch of a component at the tape location i, asdefined earlier), which are difficult to evaluate exhaustively inpractice. The algorithm could be improved by keeping track of theoptimal choices made for every position on the tape.

4. Time complexity

In the following, we relate the decision version of FACTC

problem to the well known turnpike decision problem (TP).Although, the turnpike problem is not similar to our FACTC

problem, we will show later that for any turnpike instance it ispossible to construct a FACTC problem instance, which if solvedoptimally, will give a turnpike solution.

In the turnpike problem [10–12] a multiset D of ðn2Þ pointdistances is given, and the goal is to reconstruct the actuallocations of n points on a line so that the distances between allpairs of the points match exactly the values in the multiset. Theturnpike problem does not label the distances with pairs of points,so we do not know which distance resulted from which pair ofpoints.

The turnpike problem has been extensively studied byliterature mainly because of its use in DNA sequencing, where itis also known as the partial digest problem. In DNA sequencing, alarge amount of short sequences must be assembled into thecomplete DNA sequence. The complexity of the turnpike problemis currently not known, although there are instances where thenumber of solutions is exponential [13].

However, we can characterize the TP and FACTC decisionproblems by proofing the following lemma.4

Lemma 1. The turnpike problem is reducible in polynomial to the

combined feeder assignment and component tape construction

problem: TPrFACTC.

ARTICLE IN PRESS

1

1 2 1 2 3

2 2 1 3 32

2 3

Fig. 5. Parallel insertion of seven double pitch components.

1

1 1

2

2 2

3

3 3

Fig. 6. An optimal scenario of component insertions for double pitch components. The tape contains the same repeating pattern of components in the sequencer.

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–14991494

Proof. Consider an arbitrary TP instance T, where q¼ ðn2Þ andD¼ fdijiA1::qg is a multiset of distances of n points. Forconvenience, it is assumed that all point distances are integervalues, which does not reduce the complexity of TP (see [10,11]).A multiset D of integer numbers is a valid point distance set, ifthere is a set of points on a line whose inter-point distances matchexactly the multiset. On the other hand, multiset D can bedegenerate, meaning that it is not possible to construct a set ofpoints on a line which result in D distances. Such a case is, forexample, where all values in D are equal.

We want to construct a FACTC decision problem F, which has a

‘‘YES’’ instance if and only if T is a ‘‘YES’’ instance of TP problem.

Therefore, let M¼maxiA ½1::q�di be the largest distance in D and let

S¼Mþ2 denote the number of feeder slots required by two

components at distance M. We construct a FACTC problem

instance using a single double pitch component of type c, and a

feeder with size S. Let the input tape consist of q pairs of double

pitch components spaced at distances given by di, i¼ 1; . . . ; q, and

the space between these pairs is S, so the input tape will be

t ¼ cd1cScd2cScd3cS . . . cdqc

We then define FACTC instance F with component tape t , feeder

size S¼Mþ2, and constant R¼ q. Then, double pitch components

that are at distance S (or larger) cannot be inserted in parallel

because the feeder size is S. For that reason, the feeder can insert

at most 2 double pitch components at distance di where diAD

(like cdic) in parallel. This means that the component tape

construction with the optimal feeder assignment requires at least

q steps, since there are q sub-sequences cdic in t .

The resulting optimal feeder assignment can be considered as a

line segment, and the slots assigned with double-pitch compo-

nent c are points on this line segment.

1.

Suppose that D is a degenerate multiset of distances. Then thepoints on the line segment corresponding to the feederassignment will not define the distances in D, which can beverified in polynomial time.

2.

On the other hand if D was a valid point distance set, thereexists a point set which reconstructs D, which means thatthere is a feeder assignment, equivalent to that point set,which can insert in parallel 2 double pitch components at di

distance for any i. This means that this hypothetical feederassignment constructs t in q steps, which is the minimumamount of steps to construct t .

Lets assume that there is an algorithm called OFACTC, which

solves the FACTC decision problem. This means that all sequences

cdic are inserted in parallel (but spacing between c’s prohibits

placement of more c-components). Therefore, this feeder assign-

ment will also be a valid point set on a segment obeying

di- distances.

The above means that using a hypothetical optimal feeder

assignment algorithm, it is possible to determine in polynomial

time for an arbitrary multiset D whether it is a valid point set

distance or not, and if it is, it is possible (in polynomial time) to

reconstruct the point set. &

It is not known whether the turnpike problem is NP-completeor not. The exact complexity class of FACTC remains therefore stillopen. All the current solutions for the general case of the turnpikeproblem are pseudo-polynomial algorithms. In case of the feederassignment problem it is still possible that a pseudo-polynomialalgorithm exists but for practical needs, the above lemmamotivates the search for a heuristic algorithm.

4.1. Component tape construction

As described earlier, having a feeder assigned with componenttypes, the second part of the process is to determine the stepswhere to stop the tape to allow the insertion of one or (preferably)multiple double-pitch components. The number of such stopsshould be minimized.

Earlier we denoted with L the set of h tape locations wheredouble-pitch components are to be placed. Let Pt denote the set oftape locations which can be placed at alignment t wheretA1; . . . ; lþs as denoted earlier. There will be a number oft-indices for which Pt ¼{, and those can be ignored. Our goalin the component tape construction is to find a minimum numberof sets Pt such that their union is L. This basically is the minimum

set cover problem, which is known to be NP-hard [15].Actually, our problem is a sub-problem of the minimum set

cover problem, where the elements of set L are on a line, and thesize of subsets Pt is limited by the feeder size. A formal proof ofwhether the component tape construction is as hard as the (beinga sub-problem of) minimum set cover problem is not in the scopeof this paper. This relationship motivates the use of a greedyheuristic for component tape construction, which is commonlyused for the minimum set cover problem [14].

5. A simple method for feeder assignment

A simple method for constructing a feeder assignment is toassign m double pitch components to random feeder slotlocations. The final feeder must contain all component typespresent in the tape (in order to be able to print the tape). For each

ARTICLE IN PRESS

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–1499 1495

double-pitch component type, the number of components in thefeeder of that type should be proportional of the number ofcomponents of that type in the tape. Let bi denote the number ofdouble-pitch components of type i in the tape. The maximumnumber of components of type i in the feeder is thenai ¼ dm � bi=he, where h is the total number of double-pitchcomponents in the tape, as defined in the notation. The simpleas-

sign algorithm is described by the following steps:

1.

Count the number of components to be placed into the finaltape for each double-pitch component type.

2.

Proportionally to the above counts, an ai number is assigned toeach double-pitch component type so that the sum of thesenumbers does not exceed m (limit of double-pitch componenttypes in the feeder).

3.

For each double-pitch component type, ai components areassigned to random slot locations in the feeder.

4.

The remaining feeder slots (m is always less than the actualfeeder size) can be used for narrow component types.

6. An improved heuristics for feeder assignment

In this section we describe a heuristic algorithm for the feederassignment problem, that improves on the algorithm of Section 5by considering short, frequently occurring sequences of doublepitch components from the tape. The design of this heuristics ismotivated by the relationship of FACTC to the TP problem shownearlier. In some turnpike algorithms, the distances of set D areplaced on an open line as line segments, trying out variouspossibilities using backtracking from the longest distance of D.Our approach is similar in that we want to reserve feeder slots todouble pitch components, so that the distances between theseslots in the feeder reproduce as many similar distances on thetape as possible.

Having a feeder with m double pitch component types and p

double pitch components on the tape, we observe that in an idealscenario, if we could insert with all m slots at the same time ontothe tape, the number of insertion steps would be dp=me. Thiswould be possible only if the tape would contain the samerepeating pattern of double pitch components, as the pattern of m

double pitch components in the sequencer. For example in theparticular scenario of Fig. 6, the feeder is able to insert threedouble pitch components at once and then let the tape move andalign again for three parallel insertions. This would be an optimalfeeder allocation and placement tactics.

In practice the input is not as systematic, and may not allowsuch a perfect feeder assignment. On the other hand practicalscenarios may still exhibit some pattern repetitions. These occurinside a placement task of a single PCB and also because the sametape pattern is used to assemble multiple PCBs of the same type. Auseful method must therefore be able to handle non-systematictape content and at the same time recognize and exploit repeatingpatterns if they occur.

The length of the sequencer (number of slots) s limits themaximum length of the pattern which could be relevant forrecognition and (if possible) can be inserted at once. Our heuristicalgorithm looks for patterns up to maximum length s in the tapeand creates a slot assignment in the feeder in order to reproducethe most often occurring patterns.

6.1. Constructing the pattern set

In order simplify the representation for the algorithm, wetransform the initial tape representation into an alternative form.

This form is a series if double pitch components and spacesbetween them:

u ¼ ðe0; c1; e1; c2; e2; . . . ; cd; edÞ

where ciA ½1;n� is a double pitch component type. The integervalue eiZ0 specifies the number of intervening tape locationsreserved for single pitch components.

The length of this array is 2 � dþ1. We can ignore in thisnotation the initial space e0 occurring before the first doublepitch component, and the last space ðedÞ. Let uði; jÞ denote asubsequence of u between indices io j so thatuði; jÞ ¼ ðci; ei; ciþ1; eiþ1; . . . ; cjÞ. Such patterns, inserted in one step,can speed up the tape construction process. Determining thenumber of occurrences of a pattern in a sequence (or string) hasbeen extensively discussed in [4], as the exact matching problem.We skip the details of these algorithms, most of the exactmatching algorithms from [4] can be used here.

If the sequencer contains the component pattern uði; jÞ, it is notnecessary, that all these components are inserted at once. Thetape may contain matching subsequences of uði; jÞ at variouslocations, and the sequencer will be able to match those also, ifuði; jÞ is part of the sequencer contents. For the current approach,we do not consider more complicated super-patterns (i.e. patternswith holes like fci; ei; ciþ3; eiþ3; . . .g), since that would make thenumber of such patterns exponentially large. It is left for furtherstudy, what the effect of considering those super-patterns wouldbe on the final tape delay. The number of such super-patterns inthe tape of length l can be as much as 2mþ1

� l, where m themaximum length of such pattern. When considering onlycontinuous patterns, their number is not larger than m � l.Nevertheless, parts of uði; jÞ are considered separately by thepattern enumeration process, and placed in the feeder at suchdistances which minimize the final delay. (If we would considerinstead super-patterns of uði; jÞ, we would fix these distances intolocally suitable values, i.e. suitable for these super-pattern only.)

One of the initial conditions for the feeder assignment is thatthe sequencer inserts components simultaneously into eithereven or odd tape positions. This also means that in a particularuði; jÞ- pattern there is an odd number of tape locations betweenany two tape locations where parallel insertion can occur (valuesof e are odd).

If pattern uði; jÞ contains even e-values, it is separated into twopatterns, one where the double pitch components on the tape areat odd locations and the other where they are in even locations.Let us denote them with u1ði; jÞ and u2ði; jÞ. Both of these patternswill contain spaces of odd e-values.

Another limitation is given by the feeder size. We denote thesize of the space occupied by a pattern in the feeder by Sðuxði; jÞÞ

where x stands for 1 or 2:

Sðuxði; jÞÞ ¼ j-iþ1þXj-1

k ¼ i

ek

2

� �ð1Þ

where ðj-iþ1Þ gives the number of double pitch componentsaligned with their feeder slots, and the sum gives the spaces in theslots in-between. We limit our set of patterns by the condition

Sðuxði; jÞÞrs ð2Þ

A simple analysis shows that the worst case time performanceof the pattern set construction step is Oðl2m3Þ (assuming a naivealgorithm). There are at most l �m patterns to consider, and ittakes at most l �m2 steps to check for each pattern whether it isalready in the pattern set. The pattern construction step can beimproved by using suffix trees (see [4]).

ARTICLE IN PRESS

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–14991496

6.2. Building a feeder assignment from the pattern set

Let C¼ fc1;c2; . . . ;crg denote a set of r patterns, where eachck satisfies condition (2). For each pattern ckAC we denote withvk the number of occurrences of ck in u.

The patterns in C are sorted in decreasing order by vk. Thismay result in short but frequently occurring patterns precedinglonger/less frequent patterns. If the number of occurrences of twopatterns are the same, the longer pattern (Eq. (1)) precedes theshorter one.5

The elements of C are then considered in the sorted order forplacing into the feeder. If a pattern is successfully inserted intothe feeder (there is room for it and improves the final tape delay),it is removed from C and all remaining patterns which now canbe found in the new feeder setup are also removed from C.

Placing a pattern into the feeder means finding a slot positionto which the first double pitch component of the pattern can beassigned and the remaining elements of the pattern can beassigned to slots at distances given in the pattern. In this step, adouble pitch component can be assigned to a slot if it is either freeor it already contains the same type of double pitch component.

In order to a pattern to be insertable into the feeder at a givenposition, the resulting feeder must satisfy two conditions: thenumber of double pitch components must not be greater than m,and the number of components of each double-pitch componenttype must not be greater than ai. The value of ai is calculated in asimilar way for each component type i as in the simpleassign

algorithm described earlier.If, by placing the pattern, the feeder would contain more than

m double pitch components, or more than ai components of type i,the pattern is ignored and removed from C and the algorithmproceeds with the next pattern in C. When there is no more spaceto place new patterns into the feeder, the algorithm stops andreturns the resulting feeder.

The detailed implementation of the feeder assignment andtape construction heuristics would be several pages long. There-fore, the ideas are outlined by the following pseudo-routines:

5 W

produ

repres

in the

length

//

assigns a sequence of double pitch components to

//

the sequencer at a random location.

01

procedure addfeeder:

02

input f, r, B,

03

// B - array of remaining patterns

04

// f - feeder to be constructed

05

// r - pattern to be added

06

X[s] = an array where X[i] is 1 if slot i is empty

and

07

has not yet been tried out this algorith,

08

i = a random slot so that X[i] = 1

09

// cf is a copy of the feeder, which is locally

modified.

10

cf = f;

11

add r to cf at position i;

12

X[i] = 0;

13

if cf is a valid feeder

14

f = cf

15

remove r from B

16

else

17

repeat from line 08

18

end

e also evaluated the scenario where the sorting is done based on the

ct of pattern occurrences and pattern length, which more accurately

ents the actual component count associated with a pattern. No differences

results between the two models (occurrence only or occurrence times

) were observed.

19

end addfeeder.

20

//

builds a feeder assignment from a component tape

input

21

procedure assignfeeder:

22

input values l, n, t, w, s, p, m

23

// t - component tape

24

// l - tape length

25

// w - gives the component pitches for each

component type

26

// s - number of slots in the feeder

27

// p - number of double pitch component types

28

// m - maximum number of double pitch components

in the feeder

29

// n - number of different component types

(length of w)

30

// u - compact representation of the tape.

31

let u = compact(t, w, l);

32

/B, v S = unique patterns of u

33

// patterns according to conditions

described earlier in text

34

// each pattern in B has an associated count of

occurrences in v

35

sort B by v;

36

for all p in B

37

addfeeder(f, p, t);

38

if f has m double pitch components

39

stop

40

output f

41

end assignfeeder.

Routine compact transforms the initial tape input t into asequence u of double pitch components with spaces. Adding apattern reference ck to the feeder means positioning the doublepitch components from the pattern into the feeder at thedistances specified by the ei- counts of the pattern. The contentof the feeder is valid if the number of double-pitch components init is not more than m, and if it does not contain more than ai

components of type i.The output of assignfeeder is the assignment of double pitch

component types to sequencer slots. Observe that the algorithmmight not assign all double pitch components to slots, becausesome double pitch components do not participate in frequentlyoccurring patterns. These unassigned components (including alsothe single pitch components) can be placed into remaining emptyslots of the feeder at arbitrary locations. This can be done byreserving sufficient empty feeder slots to accommodate theseremaining components, and limiting the number of slots whichcan be filled to m when adding frequently occurring patterns tothe feeder. (In the pseudocode outline given above we omittedthis rather straightforward step.)

As mentioned before, there are at most l �m patterns toconsider. The number of patterns can still be limited by limitingthe minimum and maximum length of component sequencesconsidered when enumerating the patterns. In our experimentswe considered component sequences of lengths between 2 and10. This reduces the number of patterns to OðlÞ. Since the patternenumeration step looks up each pattern in the pattern set, theactual pattern set construction includes in the worst case Oðl2Þ

steps. For each pattern there are at most s feeder slot locationswhere the pattern can be inserted into the feeder. At each locationit takes s steps to verify that the feeder is a valid assignment. Thisresults in a Oðl2s2Þ time complexity of the feeder assignmentalgorithm. Since the feeder size is usually fixed in a specificmanufacturing setup, the value of s can be considered constant.

ARTICLE IN PRESS

0

50

100

150

200

250

300

Del

ay

1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 58 61 64 67 70 73 76 79

Fig. 7. Test case 1 (repetition of a random pattern) using the feeder assignment

heuristics. The delay of the sequencer operations is shown as a function of the size

of extra slots ðmÞ for duplicating the double pitch components. Delays are

expressed as the number of extra operation cycles of the sequencer. The feeder

size is s¼ 120. Upper curve: results of simpleassign. Lower curve: results of

assignfeeder. Results are averages of 100 test cases (for each m-value).

050

100150200250300350400450500

Del

ay

1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 58 61 64 67 70 73 76 79

Fig. 8. Test case 2. Delay of the sequencer as a function of m for a set of semi-

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–1499 1497

6.3. Extension to the n-pitch case

The above heuristics can be easily modified to support then-pitch generalization of the feeder assignment problem. In then-pitch generalization each component type can have a differentdelay time. In this case the narrow-pitch components aredesignated to be those with 0 delay time.

The feeder assignment heuristics works in a similar way forthe n-pitch case as for the 2-pitch case, except that in the n-pitchcase the patterns contain component types with non-zero delaytime. Since the delay times of components are not considered inthe assignfeeder algorithm that remains unmodified in the case ofn-pitch components. The actual delay times are considered only inthe tape construction step (of Section 6).

Further details of the n-pitch problem, and designing a betterheuristic algorithm for this extension are not considered here.

6.4. Special cases

In general, the feeder assignment problem is at least as hard tosolve optimally as it is to find a solution for the turnpike problem.It is thus obvious that the assignfeeder does not provide an optimalsolution for all problem instances. If there are repetitive patternsin the tape, the feeder assignment heuristics will recognize andexploit them. Whether this leads to an optimal solution dependson how regular these patterns are.

One can look for regularities in the tape to determine if anoptimal solution can be found in polynomial time. For example, ifat any given moment, only 1 component fits under the feeder,then it is trivial to insert optimally. But if there are at least 2(2-pitch) components under the feeder at arbitrary distance, thenwe have already reached the turnpike complexity. Furthermore, ifthere is a sufficiently small set of different distances between2-pitch component pairs on the tape, one can make an exhaustivesearch to build an optimal solution.

random tapes with feeder size 120. Upper curve: results of simpleassign. Lower

curve: results of assignfeeder. The results are averages for 100 repetitions with

semi-random component tapes.

7. Heuristics for component tape construction

Having the feeder slots assigned with various componenttypes, the sequencer starts to insert the components from thefeeder onto the tape. As discussed earlier, the objective is tominimize the number of double pitch placement occasions. Thisstep can be achieved by the use of a greedy heuristics for theminimum set cover problem. The algorithm consists of two steps.First a matrix reduction algorithm [14] is applied to extract anumber of subsets which are part of an optimal solution. Then, inthe second step (if the set L is not covered by the subsetsextracted in the first step), the subsets are considered indecreasing order of their size, until the L is covered. More detailson this algorithm can be found in [14–16].

8. Experiments

We summarize the results of the experiments with the feederassignment and tape construction algorithms in this section. Thealgorithms were tested with three different types of input tapes.The tape size was fixed to 1000 locations in these tests6 and thefeeder size was set to 120. We also studied the effect of thenumber of slots for double pitch components ðmÞ on the totaldelay.

6 This is a relatively large number, but it helps to observe differences between

algorithms and to see whether the running times become unpractically large.

8.1. Delays

Case 1: The tape content was generated by repeating a singlepattern of component types (various different patterns of lengthbetween 30 and 60 were used). The resulting costs (delay of tapeconstruction) were averaged over all tapes (using different tapeinstances for each m-value). The size of the extra feeder space forthe double pitch components was varied between 0 and 80. Thenumber of component types in this test was n¼ 30 of whichp¼ 18 were double pitch, see Fig. 7 for a summary of results.

It is observed that, as the value of m increases, the tape delayrapidly decreases to a low stationary level. The algorithmeffectively recognizes the repeating patterns in the tapes and isable to create a feeder assignment which utilizes these patterns.For the naive algorithm the increase in the number of extraavailable slots also produced similar improvement on the delay,but the overall quality of the result is worse than for assignfeeder.

Case 2: Several random patterns were randomly repeated togenerate tape contents. This results in semi-random tapes wherethe random patterns are mixed in the tape. Similar attributeswere used as in the first test (feeder size 120, mA ½0;80�, 18double pitch components).

Fig. 8 shows a similar reduction in delay as in case 1, exceptthat it is less accentuated due to the increased randomness ofthe tape.

ARTICLE IN PRESS

050

100150200250300350400450500

Del

ay

1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 58 61 64 67 70 73 76 79

Fig. 9. Test case 3. Delay of the sequencer as a function of m for a set of random

tapes with feeder size 120. Upper curve: results of simpleassign. Lower curve:

results of assignfeeder. The results are averages for 100 repetitions with semi-

random component tapes.

0

50

100

150

200

250

300

350

400

1Tests

Steps

assign feederbrute force

2 3 4 5 6

Fig. 10. Results of feeder assignment heuristics assignfeeder compared to the

results of brute force method (BFFA with BFTC) for similar test cases as previously

discussed, but shorter tape lengths (100 components) and feeder unit (10 slots).

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–14991498

Case 3: The tapes were generated as pseudo-random se-quences of component types. No pattern repetition was includedin these tapes. Other data in the generation of test cases were thesame as for case 1.

Fig. 9 reveals that, in this case, increasing the value of m doesnot provide such a good decrease in the tape construction delay.This can be attributed to the fact that the random content of thetapes does not support the existence of any repeating patterns. Itis also observed that when increasing the feeder size, due to therandomness of the tape, any arbitrary random solution(apportioned according to component counts) is as good ascounting patterns, since in this case most pattern counts areonly 1.

8.2. Comparison with brute force methods

It is evident that there are cases where our heuristics will notproduce optimal results. We therefore implemented brute forcealgorithms (BFFA with BFTC) for the joint problem of feederassignment and tape construction, and compared the results ofthe heuristics to the brute force solutions. Due to the very hightime complexity of the brute force methods, the practical probleminstances presented in Section 7.1 were too large to execute, andwe had to content ourselves to small problem instances. Theseproblems are similar to the ones described earlier, except that thetape lengths were set to 100 and the feeder size to 10. Theproblem instances were generated in a similar way as the onesdescribed earlier (cases 1–3).

Fig. 10 shows that while the feeder assignment heuristicsassignfeeder does not always provide the optimal solution, itsresults were close to optimal and the algorithm runs in a practicaltime. For the instances tested here, the running time of ourheuristic algorithm was less than a second for all data instances,while the brute force algorithm took about 30 min to execute forthe same (small) instances. The feeder assignments produced bythe heuristics caused on average 15% more delay than thoseproduced by the brute force method.

We also developed an ILOG model based on the integerformulation presented in Section 2, and tested the model usingversion 10.0.0 of CPLEX. In our evaluation of the model usingCPLEX, we were able to get results in useful time for trivialproblems with the following properties:

There are less than or equal to m 2-pitch components in thetape.The distance between the 1st and last 2-pitch components isless than or equal to the size of the feeder.

These are problem instances where all the 2-pitch componentscan be inserted in one step, as they are clustered at a short (feedersize length) region of the tape. In these simple cases both ouralgorithm and CPLEX finds the optimal solution.

Another simple case, where the optimal solution is known, is atape with l¼ 21 components ½12345678910123456789101� and afeeder with s¼ 40 slots, where m¼ 20 are used for 2-pitchcomponents. All components in the tape are 2-pitch. In this casethe optimal solution is a feeder containing ½1357913579246810246810�, which inserts components in three stepsoptimally. For this type of problem instance, our heuristics didfound a similar feeder configuration ð½1;3;5;7;9;1;3;5;7;9;0;0;0;0;0;0;0;2;4;6;8;10;2;4;6;8;10�Þ, where the two significantpatterns are randomly positioned in the feeder, and the resultingnumber of steps was also 3.

However, in practical instances the 2-pitch components arespread out on the tape at arbitrary locations, and the length of thetape is several times the feeder size. When we used CPLEX to solveour test instances presented earlier (with tape length 1000), wedid not get any answer after a 30 min run. We also tried withsmaller problem instances with CPLEX, by using the first 100locations of the tapes, without success.

9. Conclusions

This study considered the FACTC problem of assigning electro-nic components to feeder slots and constructing the input tape ofa radial placement machine. The task of the sequencer of theplacement machine is to construct the input tape for the actualoperation of component placements. In this machine, both theassignments of components to feeder slots and the way of pickingup components from the feeder slots determine the efficiency ofthe feeder operations. We introduced a sub-optimal but fastalgorithm assignfeeder to solve the feeder assignment problemand compared it against (optimal) brute force componentassignment algorithm on small problem instances. On largeproblem instances the brute force algorithm was all too slow tobe practical.

We showed that the component-to-feeder assignment has astrong relationship with the turnpike problem, which has beenextensively researched before and so far its complexity is not

ARTICLE IN PRESS

C. Raduly-Baka et al. / Computers & Operations Research 37 (2010) 1488–1499 1499

clarified. While our heuristics provided good practical results, forcomplex problem instances the results were sub-optimal.

In this paper it was assumed that the order of componentplacements is given as an input, and the goal is to optimize thefeeder content and tape construction procedure. Another problemto be solved with these machines is the ordering of componentson the tape. These two problems can be seen as sub-problems ofthe component tape ordering problem which should considerdetails like the precedence constraints of component placementsdetermined by PCB topology, orientation of the components onthe board and the machine speed factors.

It turned out that the order of tape reels in sequencer has asignificant effect on the processing time of the machine. Theutilization of group picks is here a decisive factor. A similarproblem, i.e. maximization of the number of group picks, occursalso in the control of multi-head placement machines. These onecan take advantage of the possibility of picking up severalcomponents at the same head-to-feeder location. An other similarsituation occurs when changing nozzles between head and nozzlemagazine. The considerations of the present paper might be of usewhen solving these hard problems.

References

[1] Crama Y, van den Klundert J. The approximability of tool managementproblems. Technical Report, Maastricht Economic Research School onTechnology and Organizations; 1996.

[2] Crama Y, van de Klundert J. The worst-case performance of approximationalgorithms for tool management problems. Naval Research Logistics1999;46:445–62.

[3] Crama Y, van de Klundert J, Spieksma FCR. Production planning problems inprinted circuit board assembly. Discrete Applied Mathematics2002;123:339–61.

[4] Gusfield D. Algorithms on strings, trees, and sequences. Cambridge UniversityPress; 1997. ISBN 0521585198.

[5] Ayob M, Kendall G. Real-time scheduling for multi head placement machine.In: 5th IEEE international symposium on assembly and task planning(ISATP’03), Besancom, France, July 2003. p. 18–133.

[6] Burke EK, Cowling PI, Keuthen R. The printed circuit board assembly problem:heuristic approaches for multi-head placement machinery. In: Proceedings ofthe conference on artificial intelligence (IC-AI2000), vol. III. Las Vegas, NV:CSREA Press; June 2001. p. 1456–62.

[7] Johnsson M. Operational and tactical level optimization in printed circuitboard assembly. TUCS Dissertations No. 16, Turku Centre for ComputerScience; 1999.

[8] Knuutila T, Pyottiala S, Nevalainen OS. Minimizing the number of pickups ona multi-head placement machine. TUCS Technical Report 649, Turku Centrefor Computer Science; 2004. Journal of the Operational Research Society2007;58:115–21.

[9] Knuutila T, Pyottiala S, Nevalainen OS. Improving the pickups of componentson a gantry-type placement machine. TUCS Technical Report 692, TurkuCentre for Computer Science; 2005. In: 5th international conference ontechnology and automation, ITCA, 2005. p. 227–31.

[10] Redstone J, Ruzzo WL. Algorithms for a simple point placement problem.Algorithms and complexity. In: 4th Italian conference, CIAC 2000, Rome, Italy,March 2000. p. 32–43.

[11] Newell WR, Mott R, Beck S, Lehrach H. Construction of genetic maps usingdistance geometry. Genomics 1995;30:59–70.

[12] Lemke P, Skiena SS, Smith WD. Reconstructing sets from interpoint distances.Technical Report, DIMACS-2002-37; 2002.

[13] Zhang Z. An exponential example for partial digest mapping algorithm.Journal of Computational Biology 1994;1(3):235–9.

[14] Chvatal V. A greedy heuristic for the set-covering problem. Mathematics ofOR 1979;4(3):233–5.

[15] Feige U. A threshold of ln n for approximating set cover. In: Proceedings ofthe 28th annual symposium on theory of computing, 1996. p. 314–8.

[16] Johnson DS. Approximation algorithms for combinatorial problems. Journalof Computer and System Sciences 1974;9:256–78.

[17] Leipala T, et al. Job grouping in surface mounted component printing.Robotics and Computer-Integrated Manufacturing 1999;15:39–49.

[18] Leipala T, et al. Optimization of the movements of a component installationautomaton. European Journal of Operational Research 1989;38:167–77.

[19] Ayob M, Kendall G. A survey of surface mount device placement machineoptimisation: machine classification. European Journal of OperationalResearch 2005;164:609–26.

[20] Moyer LK, Gupta SM. Development of the surface mount assembly processthrough an angular board orientation. International Journal of ProductionResearch 1998;36(7):1857–81.

[21] Tirpak TM, et al. A generic classification and object-oriented simulationtoolkit for SMT assembly equipment. IEEE Transactions on Systems,Manufacturing and Cybernetics, Part A 2002;32(1).

[22] Ayob M, et al. Optimisation of surface mount placement machines. In:Proceedings of the IEEE ICIT’02 Bangkok, 11–14 December 2002. p. 498–503.

[23] Knuutila T, et al. Three perspectives of solving the job grouping problem.International Journal of Production Research 2001;39(18):4261–80.

[24] Ahmadi J, Ahmadi R. Component fixture positioning/sequencing for printedcircuit board assembly width concurrent operations. Operations Research1995;43(3).

[25] Choudhury ND, et al. Process planning for circuit card assembly on a series ofdual head placement machines. European Journal of Operational Research2007;192:626–39.

[26] Csaszar P, et al. Optimization of a high-speed placement machine using tabusearch algorithms. Annals of Operations Research 2000;96:125–47.

[27] Grunow M, et al. Component allocation for printed circuit board assemblyusing modular placement machines. International Journal of ProductionResearch 2003;41(6):1311–31.

[28] Crama Y, et al. The component retrieval problem in printed circuit boardassembly. The International Journal of Flexible Manufacturing Systems1996;8:287–312.

[29] Ho W, Ji P. Component scheduling for chip shooter machines: a hybridgenetic algorithm approach. Computers and Operations Research2003;30(14):2175–89.

[30] van Laarhoven PJM, Zijm WHM. Production preparation and numericalcontrol in PCB assembly. The International Journal of Flexible ManufacturingSystems 1993;5:187–207.

[31] Du X, Li Z. New model and hybrid genetic algorithm for componentplacement of multihead gantry mount machine. In: International conferenceon industrial engineering and engineering management, 2008. p. 790–4.

[32] Raduly-Baka C, Knuutila T, Johnsson M, Nevalainen OS. Selecting the nozzleassortment for a Gantry-type placement machine. OR Spectrum2008;30:493–513.

[33] Sun D-S, Lee T-E. A branch-and-price algorithm for placement routing for amulti-head beam-type component placement tool. OR Spectrum2008;30:515–34.

[34] Park T-H, Kim N. A dynamic programming approach to PCB assemblyoptimization for surface mounters. International Journal of Control, Auto-mation and Systems 2007; 5(2):192–9.

[35] Fu H-P, Su C-T. A comparison of search techniques for minimizing assemblytime in printed wiring assembly. International Journal of ProductionEconomics 2000;63:83–90.

[36] Ayob M, Kendall G. A triple objective function with a Chebychev dynamicpick-and-place point specification approach to optimise the surface mountplacement machine. European Journal of Operational Research2005;164(3):609–26.

[37] Wilhelm WE, et al. A model to optimize placement operations on dual-headplacement machines. Discrete Optimization 2007;4(2):232–56.

[38] Ball MO, Magazine MJ. Sequencing of insertions in printed circuit boardassembly. Operations Research 1998;36(2).

[39] Kumar R, Li H. Integer programming approach to printed circuit boardassembly time optimization. IEEE Transactions on Components, Packaging,and Manufacturing Technology, Part B 1995; 18(4):720–7.