FEEDER ALLOCATION POLICY FOR A TURRET HEAD PLACEMENT MACHINE USING DYNAMIC PROGRAMMING Except where reference is made to the work of others, the work described in this thesis is my own or was done in collaboration with my advisory committee. This thesis does not include proprietary or classified information. _________________________ Harish Krishna Ramaswamy Certificate of Approval: _____________________________ Dr. Jeffrey S. Smith Professor Industrial and Systems Engineering _____________________________ Dr. Jorge Valenzuela, Chair Associate Professor Industrial and Systems Engineering _____________________________ Dr. Emmett Lodree Assistant Professor Industrial and Systems Engineering ______________________________ Stephen L. McFarland Acting Dean Graduate School FEEDER ALLOCATION POLICY FOR A TURRET HEAD PLACEMENT MACHINE USING DYNAMIC PROGRAMMING Harish Krishna Ramaswamy A Thesis Submitted to the Graduate Faculty of Auburn University in Partial Fulfillment of the Requirements for the Degree of Master of Science Auburn, Alabama December 16, 2005 iii FEEDER ALLOCATION POLICY FOR A TURRET HEAD PLACEMENT MACHINE USING DYNAMIC PROGRAMMING Harish Krishna Ramaswamy Permission is granted to Auburn University to make copies of this thesis at its discretion, upon request of individuals or institutions and at their expense. The author reserves all publication rights. ______________________________ Signature of Author ______________________________ Date of Graduation iv VITA Harish Krishna Ramaswamy, son of Ramaswamy Krishna and Bhama Narayanaswamy, was born April 1981, in Chennai, Tamilnadu, India. He graduated from Spartan Matriculation Higher Secondary School in 1999. He attended Sri Venkateswara College of Engineering, University of Madras for four years and graduated with a Bachelor of Engineering degree in Mechanical Engineering in May 2003. He then entered the Graduate School at Auburn University, Department of Industrial and Systems Engineering, in August 2003. v THESIS ABSTRACT FEEDER ALLOCATION POLICY FOR A TURRET HEAD PLACEMENT MACHINE USING DYNAMIC PROGRAMMING Harish Krishna Ramaswamy Master of Science, December 16, 2005 (B.E, Madras University, 2003) 85 Typed Pages Directed by Dr. Jorge Valenzuela The first objective of this thesis is to determine a feeder carriage allocation policy for a turret head placement machine. The feeder allocation problem deals with determining which component types have to be allocated to the surplus slots of the feeder carriage of the placement machine, so as to minimize the number of replenishments. The feeder allocation problem has been formulated as a dynamic programming model which maximizes the number of boards that can be made by a single allocation of component reels to the feeder slots. It has also been shown that maximizing the number of boards that can be made by a single allocation of components, delays replenishment as much as possible, thereby decreasing the total number of replenishments required. vi As a second objective, a methodology of solving optimization problems with spreadsheets is proposed. This technique is called spreadsheet based optimization. The methodology is illustrated by considering the component allocation problem for a turret head placement machine. vii ACKNOWLEDGMENTS I would like to take this opportunity to thank one and all who have made this thesis possible. First and foremost I would like to express my sincere gratitude to Dr. Jorge Valenzuela. I am deeply indebted to him for all his stimulating suggestions, encouragement, and support rendered to me, during my academic program in Auburn. He has been a wealth of information and my inspiration. I wish to express my sincere appreciation to my committee members Dr. Jeffrey Smith and Dr. Emmett Lodree for their input and suggestions. I am most grateful to my parents, grandparents, sister and brother in law for their love and support they have given me throughout my life. I am also ever thankful to all my friends for supporting me and encouraging me. Special thanks are however due to Skylab Gupta for all his help and support. viii Style manual or journal used: European Journal of Operational Research Computer software used: Microsoft Word, Microsoft Excel, CPLEX 8 ix TABLE OF CONTENTS CHAPTER 1: INTRODUCTION??????????????????? 1 1.1 Surface Mount Technology??????????????????.. 1 1.2 Turret head placement machine????????????????... 2 1.3 Problem Overview?????????????????????... 4 CHAPTER 2: LITERATURE REVIEW??????????????......... 7 CHAPTER 3: PROBLEM FORMULATION ?????????????? 17 3.1 Assumptions??????????????????????......... 17 3.2 Notation?????????????????????????? 18 3.3 Model formulation?????????????????????... 18 3.4 Example?????????????????????????... 21 3.5 Alternative solution approaches????????????????... 26 3.5.1 IP formulation?????????????????????? 26 3.5.2 Sequential search approach????????????????? 26 CHAPTER 4: IMPLEMENTATION METHODOLOGY?????????.. 28 4.1 Need for spreadsheet based optimization???????????......... 28 4.2 Steps involved in spreadsheet based optimization?????????... 31 4.2.1 Identifying end user requirements/Defining the objectives????... 32 4.2.2 Designing the worksheets?????????????????.. 33 4.2.3 Building the model??????????????????......... 43 x 4.2.4 Integration???????????????????????.. 45 4.2.5 Testing????????????????????????? 48 CHAPTER 5: EXPERIMENTATION AND RESULTS????????......... 49 5.1 Small scale problems??????????????????.??.. 49 5.2 Medium scale problems???????????????????... 51 5.3 Large scale problems????????????????????... 54 5.4 Analysis of results?????????????????????? 57 5.4.1 Gain in production time????????????????......... 61 5.5 Solution times???????????????????????.. 62 CHAPTER 6: CONCLUSION AND FUTURE WORK??????????. 63 6.1 Conclusion????????????????????????... 63 6.2 Future work????????????????????????.. 65 BIBLIOGRAPHY????????????????????????? 66 APPENDIX A: VBA CODE FOR THE DP MODEL???????????. 69 APPENDIX B: VBA CODE FOR THE SEQUENTIAL SEARCH APPROACH. 71 xi LIST OF FIGURES Figure 1.1 Turret head placement machine??????????????... 3 Figure 3.1 DP representation??????????????????......... 21 Figure 3.2 Optimal solution????????????????????... 24 Figure 4.1 Spreadsheet based optimization 1?????????????? 29 Figure 4.2 Spreadsheet based optimization 2?????????????? 30 Figure 4.3 Non spreadsheet based optimization????????????? 30 Figure 4.4 Steps involved in spreadsheet based optimization???????... 31 Figure 4.5 Identifying end user requirements?????????????? 33 Figure 4.6 Example of an introductory sheet????????????........ 34 Figure 4.7 Example (1) of input sheet????????????????... 36 Figure 4.8 Example (2) of input sheet????????????????... 37 Figure 4.9 Example (1) of use of buttons???????????????.. 38 Figure 4.10 Example (2) of use of buttons???????????????.. 39 Figure 4.11 Example of results sheet?????????????????... 40 Figure 4.12 Example of calculation sheet???????????????? 41 Figure 4.13 Example (1) of resetting data???????????????... 42 Figure 4.14 Example (2) of resetting data???????????????... 43 Figure 4.15 Example (1) of messages?????????????????.. 46 xii Figure 4.16 Example (2) of messages?????????????????.. 47 Figure 5.1 Number of boards Vs Number of surplus slots????????? 60 Figure 5.2 Percentage reduction in replenishments Vs Number of boards........... 61 xiii LIST OF TABLES Table 3.1 Example???????????????????????? 22 Table 3.2 Stage t = 4?????????????????????......... 22 Table 3.3 Stage t = 3?????????????????????......... 22 Table 3.4 Stage t = 2?????????????????????......... 23 Table 3.5 Stage t = 1?????????????????????......... 23 Table 5.1 Number of components and surplus slots for small scale problem?.. 50 Table 5.2 Demand for components of each PCB type for small scale problems?????????????????????........... 50 Table 5.3 Reel sizes for components of each PCB type for small scale problems?????????????????????........... 50 Table 5.4 Solution for small scale problems?????????????? 51 Table 5.5 Component types allocated to the extra slots for small scale problems?????????????????????........... 51 Table 5.6 Number of components and surplus slots for medium scale problem?????????????????????............. 52 Table 5.7 Demand for components of each PCB type for medium problems?.. 52 Table 5.8 Reel sizes for components of each PCB type for medium scale problems ?????????????????????.......... 53 Table 5.9 Solution for medium scale problems???????????........ 54 xiv Table 5.10 Component types allocated to the extra slots for medium scale problems???????????????????????... 54 Table 5.11 Number of components and surplus slots for large scale problems?????????????????????........... 55 Table 5.12 Demand for components of each PCB type for large scale problems?????????????????????........... 55 Table 5.13 Reel sizes for components of each PCB type for large scale problems?????????????????????........... 56 Table 5.14 Solution for large scale problems????????????......... 57 Table 5.15 Component types allocated to the extra slots for large scale problems?????????????????????........... 57 Table 5.16 Batch size for medium scale problems??????????......... 58 Table 5.17 Number of replenishments for medium scale problems?????... 58 Table 5.18 Number of surplus slots Vs Number of boards???????........ 59 Table 5.19 Relative gain in production time??????????????.. 62 1 CHAPTER 1 INTRODUCTION In the recent past the electronics manufacturing industry has seen remarkable innovations. This can be attributed to the highly demanding and competitive market of the electronics industry. The use of Printed Circuit boards (PCB?s) in various applications has increased drastically. For example PCB?s are extensively used in computers, mobile phones, cars, and robots. In the last year alone PCB production rate has increased by around 30% leading to annual production amount of more than 35 billion dollars [21, 19]. Hence in order to survive in this highly competitive environment, companies must be able to produce products faster, cheaper, and of better quality. Companies using through hole technology (THT) to manufacture PCB?s found it difficult to keep up with the ever increasing demand. The advent of surface mount technology has greatly helped companies to manufacture products with complicated designs with high speed and quality. 1.1 Surface Mount Technology Previously PCB?s were manufactured by through hole technology (THT). In THT, components are mounted on the PCB?s by inserting the leads of the components into the 2 holes made on the PCB board and then soldering the leads on the bottom of the board. In SMT the components to be mounted on the PCB are placed directly on one side or both sides of the bare substrate by soldering. Thus in the SMT the solder paste serves a dual purpose of holding the components on the board and providing electrical connectivity. The advantages of SMT over THT are obvious; holes need not have to drilled, smaller components can be placed easily, higher board density, and components can be placed on either side of the board. All these lead to a better quality and reduced costs. The basic SMT manufacturing line consists of three steps [22]. In the first step the solder paste is screen printed on the bare substrate and inspection is carried out to check for defects. In the second step, the components to be mounted are placed on the board such that the leads of the components rest on the solder pads. In the third step, by means of the solder reflow process, electrical and mechanical contact of the leads with the board is established. The components on the PCB board are usually placed by means of highly automated placement machines. 1.2 Turret head placement machine The processes involved in SMT are highly automated. The placement of components on the board is usually done by placement machines. Basically there are two types of placement machines [18]; pick and place (PAP) machine and the turret head placement machine also known as the chip shooter machine. Each of these machines has its own characteristics. In the PAP machine, multiple stationary feeders are used to store the components. A moving placement head is used to pick up the components from the feeder slots one at a time and place it on the board which is also stationary. PAP machines operate at a lower speed than chip shooter machines, but have better accuracy and are usually used to place large components. This thesis is based on the turret head placement machine. The turret head placement machine it characterized by its high placement speed; it can place between 40,000 and 53,000 components per hour [14]. A turret head placement machine is shown in Figure 1.1. Figure 1.1: Turret head placement machine A turret head placement machine consists of a rotating turret, a moving feeder carriage and movable X-Y table on which the PCB is placed. A reel of each component type is placed in each slot of the feeder carriage. Sometimes two or more slots may be required to hold the reels of a component. The rotating turret usually has around 10 to 12 heads [18] and picks up components from the feeder carriage on one side while simultaneously placing the components on the PCB. The assembly heads each have several nozzles of different sizes. The moving X-Y table facilitates the positioning of the 3 4 PCB. Turret head placement machines are usually used to place small components on the board. 1.3 Problem Overview In the assembly of PCB?s, the placement operations are usually the bottlenecks and are also the most time consuming task. Any reduction in the placement time would greatly reduce the cycle time and therefore improve productivity. There are three sub problems involved in the optimization of placement problems [5]. The first problem deals with determination of the component placement sequence. The second problem involves assigning component types to the feeder slots, and the third problem deals with the sequence in which each components are to be retrieved. This research deals with the second sub problem. In the turret head placement machine when any of the component reels in the feeder slots are exhausted, the machine stops and the exhausted reels have to be replenished manually by the operator. Replenishing the reels is time consuming and depends highly on the skill level and the availability of the operator. The time taken to replenish a reel depends upon two factors; time required by the feeder carriage to move back and forth from the setup position to the reload position and the time taken by the operator to load a new reel. In a high density and high volume production environment this results in an increased number of replenishments. This in turn forces the machine to stop often resulting in loss of valuable production time. Though in some cases the loss in production time due to feeder replenishment can be small when compared to the assembly time, the need for an available operator to replenish the reel may further increase the machine idle time. 5 Moreover, the feeder tray in the turret head type is constantly moving horizontally for component positioning and hence rules out the use of spliceable feeders and other mechanisms designed to keep the machine operating even while the reels are replenished. Usually the number of different component types to be assigned to the feeder slots is less than the number of available slots; that is surplus or extra slots are available. The first objective of this research is to maximize the number of boards that can be made by a single allocation of components to the feeder slots and therefore reduce the idle time due to feeder replenishment. This in turn requires determining which component types are to be allocated to the surplus slots. This is called the feeder allocation problem. In this research a dynamic programming (DP) model is proposed to solve the model. Most research conducted in this area has involved building optimization models which are usually linear programs or integer programs. These models require optimization software like Cplex, Lingo or Lindo. The biggest shortcoming of this approach is that these software products are expensive. Another disadvantage of this approach is that the managers or operators in the industry might find it difficult to operate the software and interpret the results. Therefore, the second objective of this research is to present a methodology to build user interfaces to solve such optimization problems using spreadsheets. This technique is called spreadsheet based optimization or spreadsheet modeling [2]. This is demonstrated by using the DP model. This manuscript is organized as follows. In chapter 2, research in the area of placement machines is discussed in detail. Chapter 3 describes the problem considered for this master?s thesis along with assumptions made and develops the DP formulation. In order to illustrate the working of the model an example is also presented. Chapter 4 deals 6 with the methodology or the steps involved in constructing a spreadsheet based interface for implementing the model. In chapter 5 the experimental results are given and discussed. Chapter 6 gives the conclusion and directions for future work. 7 CHAPTER 2 LITERATURE REVIEW This chapter presents a literature review on problems in the optimization of placement machines. Among all the steps involved in the SMT process, the placement machine is generally the bottleneck in the assembly line. Hence, any reduction in the placement times will result in considerable increase in productivity and therefore profit. According to Grunow et al [16] there are a number of reasons why placement machines do not reach their nominal placement rates. Some of these factors are the sequence of placement operations, the feeder slot assignment, the rotational speed of the turret, the varying width of the feeders, and the component retrieval. The authors also discuss the importance of sequencing of the placement operations. In a turret head placement machine the sequence and the setup are the main factors that determine the magazine movement. One way of reducing the feeder carriage movement is by multiple allocations of components to the feeder slots. In this paper, the authors have also presented a simulation based system that incorporates various types of assembly machines. According to the authors, this simulation system serves dual purposes; it can be used as a tactical production planning aid and also can be used for the kinematic analysis of the processes of the PCB assembly lines. 8 In the area of placement machines, several approaches have been discussed in order to improve the placement time through optimally sequencing the component placement and by proper component allocation. In [11] Ellis et al have proposed a solution approach to determine the optimal placement sequence of components and feeder arrangement on the chip shooter machine. The authors? state that the solution approach developed can be integrated into a process planning system to reduce assembly time and improve productivity. The solution approach proposed minimizes the placement time of a turret head placement machine. The solution approach involves constructing an initial solution based on some characteristics and set of rules of the placement machine and then using a two-opt improvement algorithm to improve the initial solution. In order to evaluate the proposed solution approach, the authors have developed an estimator function for the placement time of the turret head placement machine. This estimator function has been developed using the operational characteristics of the turret head placement machine, such as the PCB table speed, turret head speed, concurrent mechanisms, and the feeder carriage speed. This solution approach resulted in placement times that are lower than those obtained from commercial software. Kimberly et al [12] have focused on obtaining the placement time required to populate a PCB using a particular model of the chip shooter machine, namely the Fuji CP4-3. In order to do this, the authors have developed a conceptual model of the placement time estimator function for a turret head placement machine. The placement time estimator function takes into account the operational characteristics of the chip shooter machine like the PCB table speed, concurrent mechanisms, the turret head speed 9 and the feeder carriage speed. The estimator function also takes into account the characteristics of the components to be mounted. By means of experiments, the machine parameters that are relevant to the estimator function have also been determined. Experimental results indicate that there is no statistical difference between the estimated and the actual placement times. Gronalt et al [15] have proposed a heuristic solution to efficiently switch components in a multiple machine and multiple board environments. The authors have decomposed the component switching problem into component set up and component assignment problems. The proposed method uses a recursive heuristic ? mixed-integer linear optimization model. The heuristic consists of two stages. The first stage of the recursive heuristic is used to determine the component set up for a sequence of board types to be assembled on a single placement machine. This has been achieved by using a modification of the ?keep component needed soonest? policy. In the second stage reels of the component types are assigned to the feeder slots of the carriage. Both the stages are solved iteratively, and the solutions to the set up problem provide the basis for solving the assignment problem. In [9] Depuy et al have developed a component allocation methodology which, for one component, allocates multiple feeder slots among multiple placement machines. The objective of their research was to minimize the work load and therefore reduce the cycle time for a printed circuit board assembly system. In order to do this, the problem has been formulated as a mixed 0-1 integer programming model that takes into account a number of operational characteristics. By this approach the authors have shown that the cycle time can be greatly improved by assigning components among multiple machines. 10 Crama et al [6] have focused on minimizing the make span of a PCB assembly process. The authors deal with the component retrieval problem which arises when component reels are assigned to multiple feeder slots. The component retrieval problem deals with determining the feeder slot from which components have to be retrieved for each related component placement on the board. The component retrieval problem has been formulated as a longest path problem in PERT/CPM network; that is the component retrieval problem was been formulated as a shortest path problem with side constraints. The authors have proved that this problem can be solved in polynomial time. They have also proved that a straight forward dynamic programming approach to solve the component retrieval problem with not necessarily yield an optimal solution. Therefore the authors have proposed a two phase dynamic programming approach which can be solved in polynomial time. Crama et al [7] have focused on the planning problem of assembling different types of boards using a single line of placement machines. Three planning problems have been considered in this paper; a) finding a feeder rack assignment for each machine b) component placement sequence for each board type and each machine c) the component retrieval sequence for each machine board pair. A solution approach based on the hierarchical decomposition of the planning problem has been proposed. A heuristic has been used to solve the feeder rack assignment problem and the other sub problems have been solved using constructive heuristics and local search methods. In order to compute the feeder rack assignment without computing the placement sequence and the component retrieval plan, an estimate of the make span for each board and each machine for given feeder rack arrangement has been computed. Later these estimates have been 11 used as an indicator of the quality of the feeder rack assignment. The authors have also proved that, it is possible to obtain a feeder carriage assignment and a component placement sequence such that the subsequent components can be retrieved from consecutive feeder slots. Bard et al [5] have focused on three issues a) component placement sequence b) assigning component reels to the feeder slots and c) the sequence in which components must be retrieved in case a particular component type is assigned to more that one feeder slot. All of these problems have been formulated as non linear integer programs. The authors have developed a series of algorithms to solve each of the above problems iteratively using a two step approach. The component placement sequence has been obtained using a weighted nearest neighbor traveling salesman problem heuristic. The feeder slot assignment and the component retrieval problem have been formulated as a quadratic integer program. The authors state the quadratic integer program is difficult to solve and hence have decomposed the quadratic IP into two sub problems by using Lagrangian relaxation techniques. The results of the two sub problems are then combined to obtain good solutions. Finally the current feeder carriage assignments are used to update the component placement sequence. The other advantage of the multiple allocations of components to feeder slots is that it helps to balance the assembly line. In [3] Ammons et al have considered a component allocation problem in which there are more than one placement machines. These machines may or may not be identical. The objective of their research is to balance the assembly line. The line balancing problem has been formulated as a large scale integer programming model which takes into account multiple and non identical 12 machines. The model has been solved using two methods. The first method uses a heuristic based on list processing in order to solve a simplified version of the component/line balancing problem. The second method involves using a LP based branch and bound mathematical software called MINTO to solve the whole problem. In related research Depuy et al [10] have considered the component allocation problem for coupled automatic placement machines. Their objective is to determine which machines place which component types and therefore reduce/balance the printed circuit board assembly line. In order to do this a large scale 0-1 mixed integer program has been presented. To solve the large scale integer programming model, the authors have proposed two methods. The first method deals with model simplification and data aggregation in order to reduce the size of the problem. In the second method, an integer programming heuristic has been developed by modifying a LP based branch and bound mathematical programming software. Grunow et al [17] discuss the problem of assembly line balancing in modular placement machines in order to obtain the desired output rate. This paper focuses on three issues; a) determination of the number of feeders for each component type to be used b) assignment of component reels to modules and c) assignment of placement operations to modules. The third problem is referred to as the workload balancing problem. In order to solve these problems the authors have proposed an integer program and two heuristic solution procedures. In both the heuristics the first stage is used to generate a feasible solution satisfying the constraint of limited component magazine capacity at each module of the placement machine. The second stage deals with balancing the workload of each module in order to minimize the cycle time. In order to balance the work load the authors 13 have presented two alternatives. The first alternative uses priority rules in order to remove the bottlenecks in the workload. This is achieved by reassigning some of the assembly operations to other modules of the machine. The second alternative determines the optimal solution by solving an IP. Zijm and Harten [23] discuss the design of a process planning system of a printed circuit assembly line, which is hierarchically structured. The authors have considered an assembly line that has a pipette head as a placement machine. The objective of the authors is to balance the workload at different machines and thereby minimize cycle time. This is achieved by determining the number of reels of each component type to be used. The authors have also shown that the process planning problem can be decomposed into a series of hierarchically coupled sub problems and each of these problems are of combinatorial structure. Models and solution techniques for solving the sub problems are also discussed. Neammanee and Randhawa [20] have focused on the problem of assigning boards to production lines with the objective of minimizing the assembly time. The authors state that the board assignment and component allocation have to be performed concurrently as the set up times are sequence dependent. In order to solve this problem an integrated methodology having seven phases has been proposed. The seven phases are a) Grouping the printed circuit boards. b) Family decomposition. c) Sequencing of sub families. d) Keep tool needed soonest (KTNS) procedure. e) Determination of component set up. 14 f) Component allocation. g) Board assignment. The effect of two parameters, capacity of the feeders and threshold value (indicates the effectiveness of joining a component type to a component group), on the proposed solution procedure has also been studied. The outcome of the study indicates that the capacity of the feeders influences the total workload imbalance but does not have any effect on the total assembly time. The threshold value was found to have a significant effect on the total make span. The interactions of the threshold value, variations in requirements of PCB?s and component usage, also have a significant effect on the global make span. Moreover the authors have also shown that their proposed methodology can solve large scale problems quickly and efficiently. Francis and Horak [13] have proposed an integer program and a bisection algorithm for determining number of reels of each component type to be used. This model aims to maximize the number of boards that can be assembled before the first reel runs out. Ahmadhi et al [1] have considered a pick and place machine with two feeder carriers for the delivery of components to the placement head. The issues that arise in the optimization of pick and place machines with dual carriers are a) the number of reels of each component type to be allocated b) the assignment of each reel to the carrier c) the alternating pick and place sequence between each carrier and the PCB d) the position of each reel on the assigned carrier. In this paper the authors have focused on two issues; component allocation and partitioning. In component allocation, the objective is to determine the number of reels of each component type to be used. In order to do this the 15 authors have developed an integer program model that maximizes the number of boards that can be made by a single allocation of components to the carriers, without any replenishment. Once the number of reels of each component type to be used is determined, the objective of the partitioning problem is to determine on which two feeder carriers each component reel has to be assigned. The author states that the partitioning problem is very important as it greatly affects the throughput time. The partitioning problem has been formulated as an integer program that uses the output of the component allocation problem to minimize the dead time. Dead time is the down time incurred due to operation imbalance, excess rotation of each head and nozzle changes. Moreover for each problem three different scenarios have been considered which vary depending on the fixtures used for the delivery of components and the pick sequence. Ho and Ji [18] have focused on two placement problems of a turret head placement machine; a) arrangement of component types to the slots in the feeder carriage b) sequence of the pick and place operations. The authors have proposed a hybrid genetic algorithm to determine the optimal placement sequence and the feeder arrangement simultaneously. The hybrid genetic algorithm uses different search heuristics such as, the nearest neighbor heuristic, the 2 opt heuristic and a new heuristic called iterated swap procedure. In the algorithm, the chromosome is represented by means of a two link structure; the first link represents the component placement sequence and the second link denotes the feeder arrangement. The initial population for the first link is generated by means of the nearest neighbor heuristic and randomly for the second link. Then an iterative swap procedure is applied to the first link and a 2 opt heuristic is applied to the second heuristic. This is then followed by selection, modified crossover and heuristic 16 mutation operations. The authors have also shown that the proposed hybrid genetic algorithm gives better results than a simple genetic algorithm. In [21] Ramasamy et al have developed a feeder carriage replenishment policy for a turret head placement machine. The objective of the authors is to reduce the idle time of the turret head placement machine due to frequent replenishments by using multiple allocations of components to the feeder carriage slots and effectively synchronizing the feeder exhausts. A mixed 0-1 integer program has been presented to do the same. The proposed model differs from other models in the sense, if a particular component is assigned to more than one slot, than the demand for that component type is split among all the slots. That is an additional problem of determining how many components of each component type has to be picked from each slot arises. Since the model is based on the fragile synchronization of the feeder exhaust any variation in reel sizes can disrupt the synchronization therefore increasing the number of replenishments. In order to counter the variation in reel sizes due to supplier allowances, a policy called the Fixed Replenishment (FR) policy has been proposed. 17 CHAPTER 3 PROBLEM FORMULATION As described in chapter 1, each time the feeder slots of the turret head placement machine runs out of components, the machine stops and waits to be replenished. The downtime incurred due to frequent replenishments can be considerably high. This chapter deals with the first objective described in chapter 1; maximize the number of boards that can be made by a single allocation of components to the feeder slots and therefore reduce the idle time due to feeder replenishment. This in turn requires determining which component types are to be allocated to the surplus slots. In this chapter a dynamic programming (DP) model is presented along with the assumptions and notations. The model is also illustrated with a small example. 3.1 Assumptions Some of the assumptions that have been made while formulating the DP model are 1. Each component type reel can be accommodated in a single slot; that is the width of the reels are lesser than the width of the feeder slots 2. All the surplus slots have to be used 3. The reel sizes and demand are already known; they are deterministic 18 4. There are no variations in reel sizes 5. Each slot has one mandatory reel Notice that assumption 2 is made to reduce the number of computations since it is always better to use all the surplus slots. 3.2 Notations T Number of different component types = Number of stages t Index for the component types ; t = 1 to T S Total number of surplus slots r t Reel size of component type t d t Demand of component type t in each board X t Number of surplus slots available to assign to component type t, t+1, t+2, ?T; X t = 0 to S Y t Number of extra reels of component type t to assign to the surplus slots; decision variable R t (Y t ) Number of boards that can be made using Y t reels of component type t; Y t = 0 to X t F t (X t ) Maximum number of boards that can be made stages t through T given that current state is X t 3.3 Model formulation Dynamic programming (DP) is a method of decomposing problems that are hard to solve, into smaller problems that can be solved easily. In order for a problem to be formulated as a DP, it has to be a Markovian process, that is, the future must depend only on the present. In order to formulate a problem as a DP, the stages of the system have to be identified. In our problem, the different component types, t = 1 to T is considered to be the different stages of the system. By this manner the sequential property is induced into the system. Next, the state of the system has to be defined in such a way that it completely describes the system. In our problem, the decision to be made is determining which components to assign to the surplus slots. The state of the system at each stage is defined as the number of surplus slots at that stage. The decision to be made in each stage t when the system is in the state X t , is how many reels, Y t , of the component type t have to be assigned to the surplus slots. Once a decision (Y t ) is made, a return R t (Y t ) is generated. The return is the number of boards that can be made by using Y t +1 reels of component type t. Based on the decision made, the system is transformed into a new state at the next stage. Because of the way the problem is set up, it can be clearly noted that the problem is Markovian. The objective is to maximize the total return (number of boards) over all the stages. Hence the problem can be stated as )]} t Y t (X 1t F), t (Y t {Min[R t X t Y 0 Max) t (X t F ? + ?? = Tt ?? (1) and SX t ,1... 0= )()( TTTT XRXF = (2) SX T 0,1...= Where t d 1) t (Y t r ) t (Y t R +? = t X t Y T t 0,1... 1,2.. =? =? (3) 19 20 The above formulation represents a backward recursive dynamic programming approach. Equation (1) determines the maximum number of boards that can be made over all the stages. Equation (2) determines the return for the stage t = T. We have Y t = X t because of the assumption that all surplus slots available will have to be used. Equation (3) determines the number of boards that can be made using Y t +1 reels of component type t. The number of boards that can me made can be determined by multiplying the reel size of a component and the number of reels used and then dividing this amount by the demand for that component type. In equation (3) Y t + 1 is used instead of Y t because Y t represents the number of extra reels to be used and due to the fact that one reel of each component type has already been assigned to the mandatory slots. To begin with, the number of boards that can be made for the states in the last stage, t = T, is determined using equations (2) and (3). Then for the states in the stage T- 1, the number of boards that can be made is determined using equation (1). Equation (1) uses the information obtained from the previous stage and the return of the current stage to determine the maximum number of boards that can be made for all the states in that stage. That is the return for a particular state and a stage t represents the best result for that stage t and the previous stage t+1. This kind of backward recursion is continued until stage 1 and the maximum number of boards obtained in stage t = 1 represents the optimal result over all the stages. In order to get the optimal allocation plan the results obtained in stage t = 1 would have to be back tracked. A diagrammatic representation of the DP model with four different component types and three surplus slots is shown in Figure 3.1. t=1 t=2 t=3 t=4 X 2 =3 3 3 3 21 In Figure 3.1, the numbers inside the circles represents the number of surplus slots (states) available. At the end of the stage t = 4 the number of surplus slots available is zero because of the assumption that in the last stage all the available slots have to be used. X t represents the states and Y t represents the decisions taken in each state. 3.4 Example In order to further illustrate the working of the dynamic programming model an example is presented below. The example consists of four different component types and three surplus slots. The data for the example problem are given in Table 3.1. 0 Figure 3.1: DP representation 3 2 1 0 2 1 0 2 1 0 Y t =3 Y t =0 X 2 =2 Y t =2 Y t =1 X 1 =3 Y t =2 X 2 =1 Y t =1 Y t =3 Y t =0 X 2 =0 22 Table 3.1: Example data Component type (t) Reel size (r t ) Demand (d t ) 1 3000 20 2 2000 10 3 1000 30 4 2000 10 Since this is a backward recursion, the DP starts from stage t = 4. This information is given in Tables 3.2, 3.3, 3.4, and 3.5. Table 3.2: Stage t = 4 X t Y t R t (Y t ) F t (Y t ) 3 3 800 800 2 2 600 600 1 1 400 400 0 0 200 200 Table 3.3: Stage t = 3 X t Y t R t (Y t ) (3) F t+1 (X t -Y t ) (4) Min (3),(4) F t (X t ) 0 33 800 33 1 66 600 66 2 100 400 100 3 3 133 200 133 133 0 33 600 33 1 66 400 66 2 2 100 200 100 100 0 33 400 33 1 1 66 200 66 66 0 0 33 200 33 33 23 Table 3.4: Stage t = 2 X t Y t R t (Y t ) (3) F t+1 (X t -Y t ) (4) Min (3),(4) F t (X t ) 0 200 133 133 1 400 100 100 2 600 66 66 3 3 800 33 33 133 0 200 100 100 1 400 66 66 2 2 600 33 33 100 0 200 66 66 1 1 400 33 33 66 0 0 200 33 33 33 Table 3.5: Stage t = 1 X t Y t R t (Y t ) (3) F t+1 (X t -Y t ) (4) Min (3),(4) F t (X t ) 0 150 133 133 133 1 300 100 100 100 2 450 66 66 66 3 3 600 33 33 33 Now in order to get the optimal allocation plan the results from Table 3.5 have to be back tracked. From the Table 3.5 it can be seen that the best result (maximum number of boards that can be manufactured by a single allocation of component type reels) is 133, which corresponds to X 1 = 3 and Y 1 = 0. This results in the system transforming to state 3 in stage 2 for which best result is 133, for Y 2 = 0. The system now transforms to state 3 in stage 3 for which the best result is 133 for Y 3 = 3. Finally the system transforms to state 0 in stage 4, corresponding to Y 4 = 0. In order to further illustrate the above sequence of events Figure 3.2 is presented. t=1 t=2 t=3 t=4 24 The above diagram can be interpreted as follows. The maximum number of boards that can me made by a single allocation of component reels is 133. In order to manufacture 133 boards, 0 extra reels (Y 1 =0) of component type 1(t = 1) are used. This results in three surplus slots available for component type 2 (t =2). Now zero extra reels (Y 2 = 0) of component type 2 (t = 2) are used. This results in three surplus slots available for component type 3 (t = 3). Now all the 3 extra reels (Y 3 = 3) of component type 3 are assigned to all the three surplus slots resulting in no surplus slot available for component type 4 (t = 4). (That is 0 extra reels of component type 4 are used). The example discussed above has 4 stages and 13 states. The number of stages for any problem is equal to the number of different component types. The total number of states for any problem can be obtained by using equation (4). T1)(T S +??=states ofnumber Total (4) 0 Figure 3.2: Optimal solution 3 X 2 =3 3 2 1 0 3 2 1 0 3 2 1 0 Y t =0 Y t =0 X 2 =2 X 2 =1 X 2 =0 Y t =0 Y t =3 133 X 1 =3 For example, by using equation (4), the number of states for a problem with 10 different component types (T = 10) and 5 surplus slots (S = 5), is 55. The complexity of the dynamic programming model proposed in this thesis can be evaluated by multiplying the number of cost calculations and the time for one cost calculation. Let n represent the number of cost calculations and z the time for one cost calculation. Then the number of cost calculations n can be obtained from equation (5). 2 2)(T2)(S1)(S 1)(S2n ??+?+ ++?= (5) For example, by using equation (5), the number of cost calculations for the example discussed is section 3.4 is 28. The time for one cost calculation, z, for the DP model proposed in this thesis can be obtained from equation (6). lez ?= (6) where e is the number of elementary operations (addition, subtraction, multiplication, division and comparison) performed for one cost calculation and l is the time taken by the computer for performing one elementary calculation. For the DP model proposed in this thesis, 3 elementary operations are performed to obtain one cost calculation and hence e is equal to 3. l is a constant and depends upon the computer hardware. The complexity of the proposed DP model can be evaluated by multiplying n and z. If r represents the maximum of S and T, it can be observed that since z is a constant, the complexity (worst case) of the model is O(r 3 ). 25 3.5 Alternative solution approaches In the following section two alternative solutions to solve the feeder allocation problem is presented. The first solution approach is the IP formulation proposed by Ahmadhi et al [1]. The second method is a sequential search method. 3.5.1 IP formulation Let b represent the number of boards that can be made before the first reel runs out. Then the IP formulation for the feeder allocation problem is given as (7) b Max S.T t tt d Y?r b )1( + ? (8) T ..t 2 1, =? SY t ??0 (9) T ..t 2 1, =? (10) ? = ? T t t SY 1 Y t and b are integer 3.5.2 Sequential search approach In this approach the number of boards that can be made without using any extra slot is computed for each of the component types. The minimum value of the number of boards indicates which component type would run out first. That particular component type is assigned to the first surplus slot. Next the number of boards that can be made using each of component types including the component type assigned to the surplus slot 26 is again computed. The minimum value of the boards would indicate which component type would run out next. That component type is assigned to the second surplus slot. This process is continued until all surplus slots are assigned. This procedure also gives the optimal solutions for the feeder allocation problem. The pseudo-code of this procedure is given below. For each surplus slot (S) Do ) 1)( (Argmin ? ? ? ? ? ? ? ? ? t tt d +Y?r =q Tt Y q = Y q + 1 Endfor 27 28 CHAPTER 4 IMPLEMENTATION METHODOLOGY This chapter deals with the second objective of this thesis. In the following sections a methodology of solving optimization problems using spreadsheets (spreadsheet based optimization) is presented. This is illustrated by building a user interface for the feeder allocation problem described in the previous section. To illustrate the methodology of spreadsheet based optimization using VBA, the DP model and the sequential search approach have been coded. The code of the DP model is presented in Appendix A and the code of the sequential search solution method in Appendix B. Furthermore to explain the use of the Excel solver, the IP model is implemented. 4.1 Need for spreadsheet based optimization Optimization problems are generally formulated as linear programming models or integer programming models. These models are commonly implemented using optimization packages such as Cplex, Lingo, and Lindo. The biggest disadvantage of this approach is that these software packages are expensive. Hence it is imperative that optimization problems be implemented keeping the cost involved in mind. This has been the main motivation for using spreadsheets in this research. Spreadsheets like Excel are comparatively cheaper than mathematical optimization packages. Though an IP formulation for the reel allocation problem exists, a dynamic programming model for the same has been formulated. The advantage of using the DP model is that it can be easily implemented using any of the available programming languages. In this research a user interface for the reel allocation problem has been built using Microsoft Excel. In today?s world almost every organization uses spreadsheets. The main reason for using Excel as an interface is that it is very versatile, simple to use, and requires little or no training. Apart from the feeder allocation problem, Excel can be used to solve a number of decision making problems [2]. It has many integrated functions like the Solver add-in and Visual Basic for application (VBA). For example, an IP formulation for the reel allocation problem can be solved using the Solver add- in or the DP model can be coded using VBA. The spreadsheets can be used as user interfaces. Moreover, these spreadsheet based interfaces, make managing data and interpreting results easy for the operators and the managers. This versatility and simplicity of Excel that have been the main reasons for spreadsheet based optimization gaining a lot of popularity of late. The difference between spreadsheet based optimization and non spreadsheet based optimization is illustrated by the Figures 4.1, 4.2 and 4.3. End User 29 Excel End User Input DP model Visual Basic Output Figure 4.1: Spread sheet based optimization 1 End User 30 Excel End User Input IP model Excel Solver Output Figure 4.2: Spread sheet based optimization 2 End User Mathematical optimization package Input Output End User Figure 4.3: Non spread sheet based optimization 4.2 Steps involved in spreadsheet based optimization In the following section, potential steps involved in spreadsheet based optimization are discussed. In the methodology proposed in this thesis, there are five basic steps in spreadsheet based optimization ; identifying end user requirements/defining the objectives, designing the worksheets, building the model, integrating the worksheets, and testing the model. A diagrammatic representation of the steps involved in Excel based optimization is shown in Figure 4.4. Identifying end user requirements/Defining the objectives Designing the worksheets Building the model Integrating 31 Figure 4.4: Steps involved in spreadsheet based optimization Testing End user 32 4.2.1 Identifying end user requirements/Defining the objectives The first step is identifying the requirements of the end user. This is a very crucial step owing to the fact that any errors committed in this stage would reflect in one of the latter stages and the entire process would have to be started from the beginning. This step involves meeting with the end users and finding out what exactly they want. Once the user requirements are identified, the problem has to be clearly understood and defined. In the reel allocation problem considered in this thesis, the user would want to determine how many reels of each component type should be used. This would be the problem statement or definition. After defining the problem, the method by which the problem would have to be solved should be determined. Since the optimization problem would have to be solved using Excel there are two options of doing this as described by Figure 4.1 and Figure 4.2. In this thesis, the decision was made to use DP to solve the model. Once the type of model to be used is decided upon, input data and output required for the model will have to be identified. While doing this it is imperative to keep the end user in mind and keep things simple. It is very important to identify only the relevant data. This is one of primary principles of spreadsheet based modeling [8]. Unnecessary information or data can be avoided. For example, the input data required for the reel allocation problem are the number of different component types, the number of surplus slots available, the demand per board of each component type and the number of components in each reel (reel size). The output generated by the model is the number of reels of each component type to be used. Finally the assumptions made will have to be specified. The steps described above are represented by means of Figure 4.5. 33 Figure 4.5: Identifying end user requirements 4.2.2 Designing the worksheets The second step in spreadsheet based optimization is the design of worksheets. This step requires a lot of planning and foresight as it determines the entire structure of the user interface. The importance of a good design cannot be overstated as it determines the ease with which end users can work with the interface. The first step in designing the worksheets is grouping like data together. This will usually result in three categories, input, output and calculation worksheets. The idea State the assumptions made Clearly define the problem/ problem statement Select appropriate model Meet with end users and Identify the required input data and output determine their needs behind doing this is to design separate worksheets for input, calculation and output so as to not to mix data and eliminate the possibility of any errors or confusion. After this is done, in the second step the introductory sheet can be designed, which gives the name of the model, briefly describes the purpose of the model, and gives the name(s) of the creators of the model. An introductory sheet designed for the reel allocation problem is shown below in Figure 4.6. Figure 4.6: Example of an introductory sheet The third step is designing the input sheet, calculation sheet and result sheet. It is imperative to note that a calculation sheet might not be needed if all the calculations are 34 35 performed using VBA. But if Excel solver is being used, a calculation sheet will be needed. In Excel when new sheets are created, default names for the sheets are automatically assigned. These sheets can be given a name, such that it conveys to the user what the sheets is being used for. For example input sheet, results sheet etc. The methodology followed for designing the input sheet is described below. If possible the input page should be used to take input from the end user and not for performing calculations. The beginning of the input page should list out the steps the end user would have to follow. This is done in order to help the user navigate through the input sheet with ease. An example of this is shown in Figure 4.7. Figure 4.7: Example (1) of input sheet Once the procedure is specified, the steps outlined in the procedure can be laid out one below the other in a logical manner. An example of this is shown in Figure 4.8. 36 Figure 4.8: Example (2) of input sheet It can be seen from Figure 4.8 that, the number of component types and surplus slots is asked from the user before asking for the reel sizes and demand values. Sometimes the data required from the user may be dynamic, that is it changes depending upon some parameter. For example, in the reel allocation problem, number of reel size values and demand values that has to obtained from the user depends upon the number of different component types. Hence the number of reel sizes and demand values are dynamic. Obtaining this kind of dynamic data can be made possible by use of ?buttons?. Buttons are objects that are provided by Visual Basic. These buttons can be used on any Excel sheet. Each button can be programmed (that is a Visual Basic code can 37 be written) to execute some action. That is why they are called event triggered procedures. This is illustrated by Figures 4.9 and 4.10. Button that generates the input area for the reel sizes and demand based on value entered in Step 1 Figure 4.9: Example (1) of use of buttons 38 39 On pressing the button ?Reel size and demand?, input space for 4 reel size and demand values are generated Figure 4.10: Example (2) of use of buttons It can be seen from Figures 4.9 and 4.10 that once, the number of component types is entered in Step 1 and the button ?Reel size and demand? is pressed, the required input area for entering the reel sizes and demand values is generated. The methodology described in the above sections can be used to design the results sheet and calculation sheet. Figure 4.11 shows the design of the results sheet. Figure 4.11: Example of results sheet It is imperative to note that, this research emphasizes on solving the reel allocation problem using DP. Hence a calculation sheet is not used. If the problem is solved using the solver, then a calculation sheet will have to be designed. When designing the calculation sheet, it would be better if separate modules are created for the decision variables, objective function and constraints [4] .An example of a calculation sheet is shown in Figure 4.12. 40 Figure 4.12: Example of calculation sheet There are few other design aspects that relate to design of any sheet. In order to be systematic the sheets can be designed in a sequential manner; that is the user input sheet can be designed first, then the calculation sheet, and finally the result sheet. The reasoning behind this is that, while solving any problem the input is collected first, then calculations are performed and finally results are presented. Colors can be used to help the users navigate through the worksheet. For example all the input cells can be in one color and all cells in which output is displayed in another color. All the cells except those which take input from the user or displays results can be hidden. This again can be done by using colors. If the user commits any mistake while entering data or wants to resolve the problem with different data, an option of automatically resetting the data or clearing 41 the data can be provided. This can be done by the use of buttons. An example of this is shown in Figures 4.13 and 4.14. On pressing this button all data entered in Steps 1, 2 and 4 will be cleared Figure 4.13: Example (1) of resetting data As shown in Figure 4.13 let us assume the user initially wants to solve the problem for 3 component types, but then decides there are 4 different component types. On pressing the ?Reset Data? button all the previously entered data will be lost as shown in Figure 4.14. 42 43 Previously entered data cleared Previously entered data cleared Figure 4.14: Example (2) of resetting data Another design related issue is that the end users should also be restricted from making any modifications to any of the worksheets. Most importantly the users should be prevented from adding or deleting rows or columns. This can be done by password protecting the worksheets. 4.2.3 Building the model As the choice of the model and the decisions pertaining to the model like the inputs and outputs have already been identified in Step 1 of the procedure, building the model is a relatively easy and a simple task. The first step in building the model, is formulating the model. For the reel allocation problem, the model has been formulated as a dynamic programming model which has been explained in chapter 3. After formulation, the second step involves 44 coding the model. Coding the model can be done using VBA. This is one of the advantages of using Excel. Almost all of the functions that Excel provides are also available in the VBA. The cells in the Excel worksheet can be referenced in the Visual Basic program and assigned to any variable by using the following syntax. Variable name = Application.SheetName.Cells (a, b) Or Variable name = Application.SheetName.Range (?Range Values?) where a and b are the cells coordinates. By referencing cells in the manner shown above, the integration of the worksheets and VBA is achieved. Excel also provides the flexibility of calling the Solver by using VBA so that the user would not have to do it manually. Moreover it also prevents the user from making changes to the Solver. The procedure of calling Solver from VBA is shown below. SolverOk SetCell:= Objective function cell MaxMinval:= 1,2 or 3 By changing:= decision variable cells Solver Add cellRef:= constraint cells The SolverOk command is used to define the objective function and the decision variables. The SetCell command is used to define objective function and the By changing command is used to define the decision variables. MaxMinval is used to denote whether the objective function is maximized (1), minimized (2) or solved for a particular value (3). The Solver Add cellRef command is used to specify the constraints. The SolverReset 45 command is used each time before the Solver is called to reset all the previously entered objective function, decision variables and constraints. While programming, it is advisable to use comments in appropriate places, in case some modification to the model would have to done by a different person in future. 4.2.4 Integration In the methodology proposed in this thesis, integration refers to two levels of integration. First the VBA must be integrated with the worksheets and then the different worksheets must be integrated together. This is done so that the entire interface works seamlessly. To begin with input sheet should be integrated with the VBA and then the VBA module should be integrated with the calculation sheet (if a calculation sheet exists) and the result sheets. As described in the previous step a part of this integration can be achieved by means of cell referencing. For achieving full integration, buttons can be used. By full integration, it is meant that the once all the data have been input, by just one click of the button, the interface must accept the input (integrating input sheet with the VBA), process the input (integrating the VBA with the calculation sheet) and finally display the results in the results sheet (integrating the VBA with the results sheet). For example in the user interface considered in this thesis, the functions stated above are achieved by means of the button named ?Solve?. Once the user enters all the required data and presses the ?Solve? button, the results are automatically displayed in the results page. Usually when the ?Solve? button is pressed the screen tends to flicker when processing the data. This can be avoided by using Excel?s screen updating command in the Visual Basic code, which is shown below. Application.ScreenUpdating = False In order to make the application user friendly, messages should be displayed to the user at appropriate times. For example when the user forgets to enter data and tries to solve the problem or when a solution is found, messages must be displayed indicating that. This can be done by using message boxes in the Visual Basic code. An example of this is shown below in Figures 4.15 and 4.16. Figure 4.15: Example (1) of messages When the user clicks on the ?Solve? button a message indicating the user to wait is displayed as shown in Figure 4.15. When the user clicks on ?OK?, another message indicating that the optimal allocation plan is obtained is displayed as shown in Figure 4.16. 46 Figure 4.16: Example (2) of messages The second level of integration deals with the integration of the individual worksheets; the introductory sheet, the input sheet, calculation sheet and the results sheet. At any point in time, it is advisable to make only one worksheet be visible to the user. That is the user can navigate from one sheet to another by the use of buttons. Thus buttons serve to integrate one sheet with another. For example in the interface constructed in this thesis, when Excel is opened each time, only the introductory or the welcome sheet is visible. This is achieved by using the following set of code. Worksheets ("Welcome").Visible = True For Each ws In ActiveWorkbook.Worksheets If ws.Name <> "Welcome" Then ws.Visible = False End If Next ws 47 48 The name of the introductory sheet is ?Welcome?. Each time Excel is opened, the ?Welcome? sheet is made visible and all other sheets are invisible. When the button ?Allocation Model? is pressed, the ?User Input? sheet is made visible and all other sheets are made invisible by the using same procedure described above, within the code of the button. Similarly when the ?Results? button is pressed, the ?Results? sheet becomes visible and all other sheets becomes invisible. To return back to the input sheet from the results sheet and back button is provided in the results sheet. By this way, just by using buttons all the sheets are integrated. But it is imperative to note that if a calculation sheet is used, it should always remain invisible to the user. 4.2.5 Testing After all the sheets have been integrated, it is always best to test the working of the model by running a few examples. This would help in identifying the bugs and correcting the problem. In order to check if the model is giving the correct results, a number of problems must be solved using the model constructed and another already established model (if one exists). For example, for the reel allocation problem considered in this thesis, the output of the dynamic programming model has been tested with the output of the IP formulation proposed by Ahmadhi et al [1]. 49 CHAPTER 5 EXPERIMENTATION AND RESULTS In this chapter the dynamic programming model for which an Excel based interface has been built is tested with a number of problems. The results of the model are tested with the integer programming model proposed by Ahmadhi et al [1]. The test problems have been divided into three categories based on the size of the problem; small, medium and large scale problems. The small problems deal with 10 to 20 slots for the feeder carriage, the medium size problems deal with 21 to 40 slots, and the large scale problems deal with 40 to 60 slots. 5.1 Small scale problems The input data for the small scale problems is presented below. Five different scenarios (different PCB types called S1, S2, S3, S4, S5) are presented which vary in the number of component types, number of surplus slots, the demand and the reel sizes. The data were generated from a uniform distribution. The parameters for demand values are between 1 and 30 and the parameters for the reel sizes are between 1000 and 6000. Tables 5.1, 5.2 and 5.3 give the details of each PCB type such as the number of components, number of surplus slots, demand and reel sizes. 50 Table 5.1: Number of components and surplus slots for small scale problem PCB type Number of components Number of surplus slots S1 10 10 S2 12 8 S3 15 5 S4 18 2 S5 19 1 Table 5.2: Demand for components of each PCB type for small scale problems Component type PCB Type 1 2 3 4 5 6 7 8 9 10 S1 10 3 15 22 22 24 1 10 21 4 S2 14 2 15 16 17 19 3 12 15 9 S3 16 4 23 12 12 15 10 16 14 15 S4 2 12 16 16 9 7 13 2 8 3 S5 11 9 7 4 2 13 2 14 12 7 Component type PCB Type 11 12 13 14 15 16 17 18 19 S1 - - - - - - - - - S2 14 4 - - - - - - - S3 22 5 4 16 3 - - - - S4 20 1 21 21 3 17 8 18 - S5 10 14 11 13 1 13 7 1 10 Table 5.3: Reel sizes for components of each PCB type for small scale problems Component type PCB Type 1 2 3 4 5 6 7 8 9 10 S1 2011 4160 2640 3884 3764 4652 4565 2459 2327 2011 S2 1949 2081 5809 4377 5541 5584 4936 5677 2833 1949 S3 3557 2350 4230 5401 4189 5227 4496 3284 3422 3557 S4 4710 3233 2459 1384 4345 5111 4800 4467 2683 4710 S5 3536 3046 4593 3905 4053 2042 2219 3406 4753 3536 Component type PCB Type 11 12 13 14 15 16 17 18 19 S1 - - - - - - - - - S2 3419 2419 - - - - - - - S3 2140 5165 1312 1423 5284 - - - - S4 3636 4709 4968 5416 2927 3752 3942 4652 - S5 3324 5278 2394 1664 5853 3228 5974 1540 5682 51 The problems were solved using the DP model implemented using VBA. In order to test the accuracy of the DP model, the IP proposed by Ahmadhi et al [1] model was solved using Cplex version 8. All the problems were solved using a Pentium IV, 2GHz, 256 MB RAM computer. Table 5.4 shows the number of boards that can be made by a single allocation of components with and without using extra slots. Table 5.4 also presents the result obtained from the IP model proposed by Ahmadhi et al [1]. Table 5.4: Solution for small scale problems Number of boards PCB type Without extra slots Using extra slots (DP model) Using extra slots (IP model-Cplex) S1 117 360 360 S2 138 378 378 S3 67 177 177 S4 153 181 181 S5 128 158 158 From Table 5.4 it can be seen that the DP model gives the same results as the IP model. Table 5.5 shows the component types allocated to the extra slots for each of the PCB types. Table 5.5: Component types allocated to the extra slots for small scale problems Component types PCB type DP model IP model S1 3,4,4,5,5,6,6,9,9,9 3,4,4,5,5,6,6,9,9,9 S2 1,3,3,4,5,6,10,11 1,3,3,4,5,6,10,11 S3 1,1,3,11,14 1,1,3,11,14 S4 4,5 4,5 S5 14 14 5.2 Medium scale problems The input data for the medium scale problems is presented below. All the data were randomly generated from uniform distribution. The parameters for demand values 52 are between 1 and 30 and the parameters for the reel sizes are between 1000 and 6000. Five different scenarios (PCB types called M1, M2, M3, M4 and M5) are considered. Tables 5.6, 5.7 and 5.8 give the number of components, number of surplus slots, the reel sizes and demand values for each of the PCB types. Table 5.6: Number of components and surplus slots for medium scale problem PCB type Number of components Number of surplus slots M1 22 18 M2 25 15 M3 30 10 M4 35 5 M5 38 2 Table 5.7: Demand for components of each PCB type for medium problems Component type PCB type 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 M1 1 2 2 1 3 1 3 3 1 2 3 3 1 2 3 M2 19 10 6 5 4 4 2 2 1 1 1 1 1 6 4 M3 8 2 12 18 17 19 1 8 17 3 5 1 1 4 5 M4 4 1 6 2 9 8 2 7 2 2 1 6 9 1 6 M5 9 4 4 9 1 6 5 1 1 9 8 5 5 6 7 Component type PCB type 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 M1 2 3 1 1 2 5 11 - - - - - - - - M2 4 2 2 1 1 1 1 1 1 1 - - - - - M3 1 6 7 11 7 8 7 18 9 9 6 19 16 19 5 M4 5 5 2 1 9 4 5 3 4 8 1 1 4 4 4 M5 5 5 6 8 2 2 5 1 6 9 1 7 2 9 9 Component type PCB type 31 32 33 34 35 36 37 38 M1 - - - - - - - - M2 - - - - - - - - M3 - - - - - - - - M4 2 6 9 7 9 - - - M5 5 7 9 7 2 6 1 7 53 Table 5.8: Reel sizes for components of each PCB type for medium scale problems Component type PCB type 1 2 3 4 5 6 7 8 9 10 M1 3669 3565 2128 1228 1958 1251 1381 1956 3184 1247 M2 4200 3000 3200 3800 2600 4400 3000 3000 4400 4500 M3 3152 3285 3661 4415 1882 4180 1540 1622 4108 4805 M4 4127 1194 4770 2563 3055 3687 2314 2316 4306 1408 M5 2192 2425 3148 4163 3218 2814 2559 3272 4658 1824 Component type PCB type 11 12 13 14 15 16 17 18 19 20 M1 3566 2615 1598 3365 1133 2028 1633 3737 1302 3182 M2 4800 3900 3200 4300 3900 3600 4900 4800 3800 4400 M3 3203 1695 1719 3466 1810 2885 4746 1694 3897 2231 M4 3702 1562 3126 2911 2407 4505 3039 3194 2713 4438 M5 4641 4387 1144 3132 1647 2898 4054 1958 1854 2164 Component type PCB type 21 22 23 24 25 26 27 28 29 30 M1 3456 4523 - - - - - - - - M2 4100 4400 4200 4400 3300 - - - - - M3 2146 2401 1371 4057 2804 3375 1556 2351 2887 3706 M4 3722 2583 3586 2651 4759 1960 1473 2511 3906 2471 M5 4765 1802 3862 1090 4424 3645 1479 1997 2838 1760 Component type PCB type 31 32 33 34 35 36 37 38 M1 - - - - - - - - M2 - - - - - - - - M3 - - - - - - - - M4 3684 3833 2488 3840 1964 - - - M5 4794 1900 1132 2249 1062 4333 2787 2431 It should be noted that the data for PCB type M2 were obtained from a high volume electronics manufacturer in Griffin, GA. The data for the rest of the PCB types were generated randomly. Table 5.9 shows the number of boards that can be made by a single allocation of components with and without using extra slots. Table 5.9 also presents the result obtained from the IP model proposed by Ahmadhi et al [1]. 54 Table 5.9: Solution for medium scale problems Number of boards PCB type Without extra slots Using extra slots (DP model) Using extra slots (IP model-Cplex) M1 377 1233 1233 M2 221 1105 1105 M3 76 228 228 M4 218 347 347 M5 125 195 195 Table 5.10 shows the component types allocated to the extra slots for each of the PCB types. Table 5.10: Component types allocated to the extra slots for medium scale problems Component types PCB type DP model IP model M1 3,4,5,7,7,8,10,11,12,15,15, 15,16,17,17,21,22,22 3,4,5,7,7,8,10,11,12,15,15, 15,16,17,17,21,22,22 M2 1,1,1,1,2,2,2,3,3, 4,5,6,14,15,16 1,1,1,1,2,2,2,3,3, 4,5,6,14,15,16 M3 5,5,6,8,23,23,27,27,28,29 5,5,6,8,23,23,27,27,28,29 M4 5,8,12,33,35 5,8,12,33,35 M5 24,33 24,33 5.3 Large scale problems The input data for the large scale problems is presented below in Tables 5.11, 5.12 and 5.13. All the data were randomly generated from a uniform distribution. The parameters for demand values are between 1 and 30 and the parameters for the reel sizes are between 1000 and 6000. Five different scenarios (PCB types called L1, L2, L3, L4 and L5) are considered. 55 Table 5.11: Number of components and surplus slots for large scale problem PCB type Number of components Number of surplus slots L1 40 20 L2 45 15 L3 50 5 L4 55 L5 58 2 Table 5.12: Demand for components of each PCB type for large scale problems Component type PCB type 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 L1 5 13 37105110617 13 10 84 L2 16 1 4941161 8136 3 16 114 L3 18 12 14171 27371 3 14 19 1016 L4 5 1 1588321 6154 9 5 1612 L5 5 12 1 6 10 5 13 8 10 3 9 4 9 2 10 Component type PCB type 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 L1 1 9 1314738102131 7 2 213 L2 12 13 7 16 6 15 10 16 8 6 12 12 5 10 2 L3 17 13 17964219116 15 1 35 L4 8 1 103714734112 14 4 1 6 L5 9 9 1 6 10 2 12 5 2 11 14 3 2 5 12 Component type PCB type 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 L1 2 7 791141274- - - - - L2 5 2 813143153738 17 16 86 L3 19 18 1915415124827 17 14 117 L4 6 4 10 7 15 9 15 16 11 14 4 5 4 11 2 L5 8 9 76132999813 9 4 22 Component type PCB type 46 47 48 49 50 51 52 53 54 55 56 57 58 L1 - - - - - - - - - - - - - L2 - - - - - - - - - - - - - L3 1 14 12916------ - - L4 13 3 1 15 12 8 11 8 5 10 - - - L5 9 1 714101104426 1 1 56 Table 5.13: Reel sizes for components of each PCB type for large scale problems Component type PCB type 1 2 3 4 5 6 7 8 9 10 L1 1493 2415 2310 1681 2785 5167 3398 2696 4948 3875 L2 4245 5474 1056 1056 4645 4133 4333 1950 4330 4360 L3 3943 5488 2316 4977 2454 1478 4046 2886 2840 2750 L4 1327 4758 4019 5009 5903 3583 1105 4410 1713 1153 L5 2317 2827 4499 1782 1327 3644 2426 1126 1146 2951 Component type PCB type 11 12 13 14 15 16 17 18 19 20 L1 4189 2051 4297 5831 1608 5058 4100 1090 3392 2303 L2 1681 3210 3459 4773 2436 3765 1941 3078 3706 4108 L3 3617 1997 3099 1006 1329 2672 5854 4737 5138 3289 L4 2271 2649 1675 2555 3240 2125 2402 4014 4631 5578 L5 3245 1331 3891 2586 2896 4219 1190 2374 3767 3032 Component type PCB type 21 22 23 24 25 26 27 28 29 30 L1 3726 5676 1603 4707 1578 3379 5346 1017 5745 4453 L2 5338 3954 4845 3503 1380 5148 2289 1103 4727 3821 L3 1756 2136 2512 2774 2507 5165 3878 3421 3026 1166 L4 4368 5529 4693 1031 2703 1601 2740 4594 4415 2710 L5 2066 2990 2601 1245 1009 4242 4145 2095 1865 3895 Component type PCB type 31 32 33 34 35 36 37 38 39 40 L1 2820 2263 3752 1966 5376 5210 5337 4107 3740 4330 L2 3656 4273 5135 2657 2522 4883 1693 2792 2778 1867 L3 3402 1645 4806 5930 5418 1844 4975 4621 2265 5994 L4 5341 5035 5293 2707 4774 1522 2304 4764 1798 3451 L5 1187 2976 3180 4151 3605 2795 4604 2927 1043 4444 Component type PCB type 41 42 43 44 45 46 47 48 49 50 L1 - - - - - - - - - - L2 3276 3071 3974 5818 2877 - - - - - L3 3113 4475 1827 4167 5329 5669 5545 3613 2658 4273 L4 4744 1049 2256 3758 4925 3776 4548 4617 1693 2788 L5 4000 1040 1847 4486 4861 2436 4885 4205 3687 2580 Component type PCB type 51 52 53 54 55 56 57 58 L1 - - - - - - - - L2 - - - - - - - - L3 - - - - - - - - L4 2504 1950 2542 2331 5694 - - - L5 2871 2119 4922 2137 1830 2108 1087 1067 57 Table 5.14 shows the number of boards that can be made by a single allocation of components with and without using extra slots. Table 5.14 also presents the result obtained from the IP model proposed by Ahmadhi et al [1]. Table 5.14: Solution for large scale problems Number of boards PCB type Without extra slots Using extra slots (DP model) Using extra slots (IP model) L1 83 342 342 L2 112 248 248 L3 83 166 166 L4 76 159 159 L5 91 98 98 Table 5.15 shows the component types allocated to the extra slots for each of the PCB types. Table 5.15: Component types allocated to the extra slots for large scale problems Component types PCB type DP model IP model L1 1,2,4,5,8,12,12,18,18,18,18, 19,20,23,23,25,25,26,32,34 1,2,4,5,8,12,12,18,18,18,18, 19,20,23,23,25,25,26,32,34 L2 4,4,8,13,15,17,19,25,27,28, 34,35,37,37,42 4,4,8,13,15,17,19,25,27,28, 34,35,37,37,42 L3 3,12,13,14,15,16,24,32,36,43 3,12,13,14,15,16,24,32,36,43 L4 10,10,26,37,49 10,10,26,37,49 L5 25,58 25,58 5.4 Analysis of results The results obtained from the dynamic programming model for all the problem scenarios are same as the results obtained from the IP model proposed by Ahmadhi et al [1]. That is the DP model gives optimal solutions for the feeder allocation problem. It can also be seen from the results obtained, that using the surplus slots and assigning the right component types to the surplus slots, increases the number of boards that can be made by 58 a single allocation of components to the feeder carriage and thus replenishment is delayed as much as possible. That is for a given batch size, using the allocation plan obtained from the DP model would result in lesser number of replenishments. In order to illustrate the reduction in the number of replenishments, an experiment was conducted with the medium scale problem. Let us assume the following batch sizes shown in Table 5.16 for the different PCB types of the medium scale problems. Table 5.16: Batch size for medium scale PCB types PCB type Batch Size M1 3000 M2 5000 M3 5000 M4 6000 M5 6000 Table 5.16 indicates that 3000 boards of PCB type M1 have to be manufactured, 5000 boards of PCB type M2 and so on. The allocation plan obtained from the DP model for each PCB type is used and the number of replenishments that occur during the manufacture of the given batch sizes is shown in Table 5.17. Table 5.17: Number of replenishments for medium scale problems Number of replenishments PCB type Without using extra slots Using extra slots % Reduction in replenishments M1 59 27 54.2 M2 70 31 55.7 M3 499 338 32.6 M4 307 257 16.2 M5 511 473 7.4 59 It can be seen from Table 5.17 that maximizing the number of boards that can be made by a single allocation of components decreases the number of replenishments. The percentage reduction in number of replenishments is also shown in Table 5.17. This reduction in number of replenishments basically translates into gain in production time. In order to further test the model, PCB type M2 was tested by varying the number of surplus slots and the number of boards that can be made by a single allocation of components is noted. This data, along with the percentage reduction in replenishments is provided in Table 5.18. Table 5.18: Number of surplus slots Vs Number of boards Number of surplus slots Number of boards % Reduction in replenishments 0 221 0.00 1 300 14.29 2 442 17.14 3 533 22.86 4 600 27.14 5 650 28.57 6 663 32.86 7 716 35.71 8 760 40.00 9 884 42.86 10 900 44.29 11 900 45.71 12 975 48.57 13 1066 50.00 14 1100 54.29 15 1105 55.71 0 100 200 300 400 500 600 700 800 900 1000 1100 1200 0 2 4 6 8 10 12 14 16 Number of surplus slots N u m b e r of boa r d s Figure 5.1: Number of boards Vs Number of surplus slots Figure 5.1 shows the relation between the number of surplus slots used and the number of boards that can be made before the first reel runs out. It can be observed from Figure 5.1 that as the number of surplus slots increases, the number of boards that can be made by a single allocation of components increases, but not at a linear rate. For example the number of boards that can be made by using 2 surplus slots is 442 and the number of boards that can be made by using 3 surplus slots is 533. If the increase in number of boards is linear, when a surplus slot is added each time the number of boards that can be made before the first reel runs out increases by 91. Therefore by using 15 surplus slots 1625 boards can be made. It can be observed from Figure 5.1 that since the increase in number of boards is not linear, the actual number of boards that can be made using 15 surplus slots is 1105. 60 0 10 20 30 40 50 60 0 200 400 600 800 1000 1200 Number of boards P e r c e n t a ge r e d u c t i on i n r e p l en i s h m en t s Figure 5.2: Percentage reduction in replenishments Vs Number of boards Figure 5.2 illustrates the relationship between number of boards that can be made by a single allocation of components and the percentage reduction in number of replenishments. It can be noted that as the number of boards increases, the number of replenishments decreases and the percentage reduction in replenishments increases. 5.4.1 Gain in production time To estimate the gain in total production time, two variables, T A and T B , are defined. The variable T A is the total time taken for the feeder carriage to move back and forth from the feeder position plus the average time taken for the operator to become available, and the variable T B is the time taken to replenish a reel. Let ? j represent the number of replenishments without using extra slots when j reels are replenished simultaneously and ? j the number of replenishments using extra slots when j reels are 61 replenished simultaneously. Let ? be the production cycle time of the assembly line, P o the total production time without using extra slots and P e the total production time using the extra slots. Then P, the relative gain in production time is given by equation (11). P = o eo P PP ? (11) where ?? ?++?= j jB j jAo jTTbatchsizeP ??? (12) ?? ?++?= j jB j jAe jTTbatchsizeP ??? (13) Table 5.19 gives the relative gain in production time for the medium scale problems. For each of the PCB?s it is assumed that T A =3 minutes, T B =1 minute, and ?=30 seconds. It should be noted that the relative gain in production time is dependent on the values chosen for the parameters?, T A and T B . Table 5.19: Relative gain in production time PCB type P o (secs) P e (secs) Relative gain in production time (P) M1 104220 96480 7.4% M2 168240 158220 6% M3 270900 231660 14.5% M4 254160 241860 4.8% M5 303720 294420 3.1% 5.5 Solution times The solution times for all the problems, solved using the DP model and IP model (proposed by Ahmadhi et al [1]) which was implemented using Cplex, were less than a second. 62 63 CHAPTER 6 CONCLUSION AND FUTURE WORK 6.1 Conclusion The optimization of turret head placement machines consists of three sub problems; determining component placement sequence, assigning component types to the feeder slots and determining component retrieval. In this thesis the second sub problem is considered. Another objective of this thesis is to develop a methodology of solving optimization problems using spreadsheets. Spreadsheet based optimization has been illustrated by considering the feeder allocation problem. As stated earlier, the first objective deals with the feeder allocation problem of a turret head placement machine. The objective of the model is to determine the number of reels of each component type to be used so that replenishment is delayed as much as possible. The model was formulated as a dynamic programming model. The DP model was coded using VBA provided by Excel. For illustrating the usage of the Solver add-in provided by Excel, a user interface was also built for the integer programming model proposed by Ahmadhi et al [1]. It should be noted that this was done only for illustration purposes, and is not the objective of this thesis. The disadvantage of using the standard version of Excel solver is that it cannot solve 64 problems that have more that 200 decision variables. Therefore for the feeder allocation problem, it can solve problems up to 199 component types. In order to test the DP model, a number of experiments were carried out. The model was tested with three different scale of problems; small scale, medium scale and large scale. The results obtained from the DP model were compared to the solutions obtained from the IP model which was solved using Cplex. The solutions obtained from the dynamic programming model were same as those obtained from the integer programming model. It was also shown that maximizing the number of boards that can be made by a single allocation of components to the feeder slots, delays replenishment as much as possible, leading to a reduction in the number of replenishments. This was illustrated by carrying out experiments on the medium scale problems. For example for the PCB type M2, the percentage reduction in number of replenishments was 55.71%. An important assumption made in this thesis is that there is no variation in reel sizes due to supplier allowances even though in reality reel size variations do occur. However the effect on the replenishments will be minimal since a replenishment might be advanced or delayed only be a couple of boards. The reduction in number of replenishments translates into gains in production time. For example optimal usage of the surplus slots for PCB type M3 resulted in an 14.5% gain in production time. The relationship between the number of surplus slots used and the number of boards that can me made was studied. It was found that as the number of surplus slots used increases, the number of boards that can be made by a single allocation of components, increases. The relationship between number of boards and the 65 number of replenishments was also studied. As the number of boards increases, the number of replenishments decreases. The second objective of this thesis is to develop a methodology of solving optimization problems using spreadsheets. Optimization problems should be solved keeping the cost involved and the end users in mind. Spreadsheets are widely used in every industry and are comparatively cheaper than the commercially available optimization packages. Excel is easy to use and can be used to effectively solve optimization problems. There are five basic steps in Excel based optimization; identifying end user requirements/defining the objectives, designing the worksheets, building the model, connecting the worksheets, and testing. Each of these steps has been discussed in detail. 6.2 Future work. The work described in the previous chapters can be extended by removing some of the assumptions that were made during the formulation of the dynamic programming model. For example, in this thesis it was assumed that each component type needs only one slot. A new model can be formulated by considering the possibility that component types may require more than one slot. Another assumption made in this thesis is that, there are no variations in the reel sizes due to supplier allowances. Future work can be done by considering the variation in reel sizes implicitly in the model. 66 BIBLIOGRAPHY 1. Ahmadi, J., S. Grotzinger, D. Johnson, ?Component allocation and partitioning for dual delivery placement research?, Operations Research, pp 176?191, 1988. 2. Albright, S. C., Winston, A., ?Spreadsheet Modeling and Applications: Essentials of Practical Management Science?, Thomson Brooks/Cole, 2005. 3. Ammons, J.C., M. Carlyle, L. Cranmer, G.W. DePuy, K.P. Ellis, L.F. McGinnis, C.A. Tovey, and H. Xu, ?Component allocation to balance workload in printed circuit card assembly systems?, IIE Transactions, pp 265-275, 1997. 4. Baker, K. R., ?Optimization Modeling with spreadsheets?, Thomson Brooks/Cole, 2006. 5. Bard, J. F., Clayton. R. W., Feo. T. A., ?Machine setup and component placement in printed circuit board assembly?, International Journal of Flexible Manufacturing Systems, vol. 6, pp 5-31, 1994. 6. Crama, Y., Flippo. O. E., Spieksma, F. C. R., ?The component retrieval problem in printed circuit board assembly?, International Journal of Flexible Manufacturing Systems, vol. 8, 287-312, 1996. 7. Crama, Y., Flippo. O. E., Spieksma, F. C. R., ?The assembly of printed circuit boards: A case with multiple machines and multiple board types?, European Journal of Operations Research, pp 457 ? 472, 1997. 67 8. Denardo, E. V., ?The Science of Decision Making: A Problem-Based Approach Using Excel?, John Wiley & Sons Inc, 2002. 9. DePuy, G.W., J.C. Ammons, and L.F. McGinnis, ?Multiple assignment of component types of feeder slots on automated printed circuit card placement machines?, IEEE transactions on Electronics Packaging Manufacturing, vol. 23 no. 3, pp 157 ? 164, 2000. 10. DePuy, G.W., M.W.P. Savelsbergh, J.C. Ammons, L.F. McGinnis, ?An integer programming heuristic for component allocation in printed circuit card assembly systems?, Journal of Heuristics, pp 351 ? 369, 2001. 11. Ellis, K. P., Kobza. J. E., Vittes. J., ?Optimizing the performance of a surface mount placement machine?, IEEE Transaction on Electronics Packaging Manufacturing, vol. 24, 2001. 12. Ellis, K. P., Kobza. J. E., Vittes. J., ?Development of a placement time estimator function for a turret style surface mount placement machine?, Robotics and Computer Integrated Manufacturing, pp 241-254, 2002. 13. Francis, R.L., Horak. T., ?A note on reel allocation problem, IIE Transactions, vol.26 no. 3, pp 111-114, 1994. 14. Gastel, S. V., ?A comparison of SMD placement machine concepts?, White paper - Assembl?on BV, 2002. 15. Gronalt, M., Grunow. M., Gunther. H. O., Zeller. H., ?A heuristic for component switching on SMT placement machines?, International Journal of Production Economics, pp 181-190, 1997. 68 16. Grunow, M., Gunther. H. O., Fohrenbach, A., ?Simulation-based performance analysis and optimization of electronics assembly equipment?, International Journal of Production Research, vol. 38, no. 17, pp 4247-4259, 2000. 17. Grunow, M., G?nther. H. O., Schleusener. M., ?Component allocation for printed circuit assembly using modular placement machines?, International Journal of Production Research, vol. 41, no. 6, 1311-1331, 2003. 18. Ho, P., Ji. P., ?Component scheduling for chip shooter machines: a hybrid genetic algorithm approach?, Computers and Operations Research, no. 30, pp 2175-2189, 2003. 19. Nakahara, H., ?PCB output 1998?, Printed Circuit Fabrication, 1999. 20. Neammanee, P., Sabah. U. R., ?Integrated methodology for board assignment and component allocation in printed circuit board assembly?, International Journal of Production Research, vol. 41, no. 5, 919-937, 2003. 21. Ramasamy, G., Valenzuela. J. F., Ramaswamy. H. K., ?A feeder replenishment policy for a turret head placement machine?, under review, International Journal of Production Research. 22. Valenzuela, J. F., Smith. J. S., Evans. J. L., ?Allocating solder paste printing inspection in high volume electronics manufacturing?, IIE Transactions. Vol. 36, No. 12, pp. 1171-1181, 2004. 23. Zijm, W., van Harten. A., ?Process planning for a modular component placement system?, International Journal of Production Economics, vol. 30-31, pp 123-135, 1993. 69 APPENDIX A VBA CODE FOR THE DP MODEL Function Ft(t As Integer, Xt As Integer) As Integer Dim Max As Integer Dim Yt As Integer If Fvalue(t, Xt) = -1 Then If t = T Then Fvalue(T, Xt) = Rt(T, Xt) Else Max = -1 For Yt = 0 To Xt Z = Minimum(Rt(t, Xt), Ft(t + 1, Xt - Yt)) If Z > Max Then Max = Z best(t, Xt) = Yt End If Next Yt Fvalue(t, Xt) = Max End If 70 Ft = Fvalue(t, Xt) End If End Function Function Rt(t As Integer, Yt As Integer) As Integer Rt = Int(r(t) * (Yt + 1) / d(t)) End Function The solution is obtained by calling the function Ft(1,S). 71 APPENDIX B VBA CODE FOR THE SEQUENTIAL SEARCH APPROACH Private Sub SequentialSearch( ) For t = 1 To T a(t) = Int(r(t) / d(t)) Next t For s = 1 To S Sort(a, I) ? Sort in ascending order where I is the array index q = I(1) Y(q) = Y(q) + 1 a(q) = Int(r(q) * (Y(q) + 1) / d(q)) Next s End Sub