

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBILITY DESIGN By MENG LI Bachelor of Engineer in Material Engineering Yanshan University Qinhuangdao, Hebei, China 2002 Master of Science in Applied Mathematics Tianjin University Tianjin, China 2005 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial ful¯llment of the requirements for the Degree of MASTER OF SCIENCE December, 2008 COPYRIGHT °c By MENG LI December, 2008 STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBILITY DESIGN Thesis Approved: Dr. Tieming Liu Thesis Advisor Dr. Manjunath Kamath Dr. Ricki G. Ingalls Dr. A. Gordon Emslie Dean of the Graduate College iii ACKNOWLEDGMENTS The past two years at OSU have been an immensely rewarding educational and intellectual experience. Much of the credit for this must go to my advisor Prof. Tieming Liu. Interacting with Dr. Liu has developed my analytical skills more than I could have imagined. Many thanks to Prof. Manjunath Kamath and Ricki G. Ingalls for their encouragement and help in the editing process. Their feedback has been invaluable. I would also like to thank Prof. Baski Balasundaram and Alan Noell for their helpful comments. I owe tremendous debt of gratitude to my parents Minzheng Li and Shujing Wang and to my sister Ye Li. The frequent weekend conversations with them were always eagerly anticipated. I thank my parents and sister for all their love and for everything they have done for me. I would like to thank my wife Yingzhe Wu, who always has con¯dence in me and always stays with me to overcome whatever di±culty I face in my daily life during my study in OSU. I have been very lucky to have had very pleasant, friendly and helpful o±cemates and classmates, namely, Dahai Xing, Sandeep Srivathsan, Peerapol Sittivijan, Karthik Ayodhiramanujan, Sharethram Hariharan, Chinnatat Methapatara, Mario Cornejo Barriere, Hui Yang and Xiaowei Yang. We have had some great moments together, and I would like to thank them for the help and encouragement. iv TABLE OF CONTENTS Chapter Page 1 Introduction 1 1.1 Research Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Research Objective and Scope . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organization of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Literature Review 6 2.1 Literature Review on Manufacturing Flexibility . . . . . . . . . . . . 6 2.2 Literature Review on Graph Expander . . . . . . . . . . . . . . . . . 8 3 Methodology 10 3.1 Manufacturing Flexibility Model . . . . . . . . . . . . . . . . . . . . . 10 3.2 Chain Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 SF Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3.1 SF Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Graph Expander . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.4.1 Expander Index . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Shrinking Capacity Case 18 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Model in Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . 18 4.3 SF Matrix of Shrinking Capacity Case . . . . . . . . . . . . . . . . . 20 4.3.1 Algorithm for SF Matrix Construction in Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 v 4.4 Graph Expander . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4.1 Graph Expander in the Shrinking Capacity Case . . . . . . . . 24 4.5 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.5.1 Chaining Structure . . . . . . . . . . . . . . . . . . . . . . . . 27 4.5.2 General Structures . . . . . . . . . . . . . . . . . . . . . . . . 32 5 Additional Cost Case 36 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Model in Additional Cost Case . . . . . . . . . . . . . . . . . . . . . 36 5.3 SF Matrix of Additional Cost Case . . . . . . . . . . . . . . . . . . . 38 5.3.1 Algorithm for SF Matrix Construction in Additional Cost Case 40 5.4 Graph Expander in Additional Cost Case . . . . . . . . . . . . . . . 40 5.5 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5.1 Chaining Structure . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5.2 General Structure . . . . . . . . . . . . . . . . . . . . . . . . . 47 6 Conclusion 51 BIBLIOGRAPHY 53 A Simulation Results in Shrinking Capacity Case 56 B Numerical Results in Additional Cost Case with Di®erent Price 59 C Numerical Results in Additional Cost Case with Same Price 62 vi LIST OF TABLES Table Page 4.1 Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 SF Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.1 Additional Cost Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Additional Cost Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.3 SF Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 vii LIST OF FIGURES Figure Page 3.1 Total Flexibility structure; n Suppliers Service All the m Demands. . 11 3.2 Two Manufacturing Flexibility Structures. . . . . . . . . . . . . . . . 13 3.3 Two Paths From Demand B to Demand D. . . . . . . . . . . . . . . . 14 4.1 nn Partial Flexibility Structure . . . . . . . . . . . . . . . . . . . . . 19 4.2 44 Manufacturing Flexibility Structure in Shrinking Capacity Case. . 21 4.3 SF Matrix Index (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4 Graph Expander Index(the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.5 SF Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.6 Indices for SF Structures (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.1 44 Manufacturing Flexibility Structure in Additional Cost Case. . . . 39 5.2 SF Matrix Indices for Additional Cost Case . . . . . . . . . . . . . . 44 5.3 SF Matrix Indices for Additional Cost Case (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . 45 5.4 Graph Expander Index (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.5 SF Indices, Up: Biggest Eigenvalue Index; Down: Mean Value Index (the number beside each node is the structure it is associated with). . 48 viii 5.6 Expander Indices for SF Structures (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . 48 ix CHAPTER 1 Introduction 1.1 Research Background In today's competitive business environment, enterprises are facing dramatic changes in customer requirement, shortened development cycle, and uncertainty in the oper ation environment. The demand a company is facing maybe di®erent each month or each year. To make things worse, there are probably no patterns to trace the demand. The traditional way to overcome uncertainties is to have inventory safety stock. Inventory provides a safety cushion only for a narrow segment of demand uncertainty. However accumulating inventory can leave manufacturers with inventory of unwanted products, and changes in technology can leave manufactures with stocks of obsolete inventory. In addition, the investment in the safety stock leads to lower investment in other parts of the company. In the current manufacturing environment, with increased customer expecta tions, along with the prevailing uncertainties, °exibility has emerged as an important method to achieve competitive advantage. Manufacturing °exibility (the ability of a plant or machine to process more than one product at the same time (Graves and Tomlin (2003)) is a key strategy for improving market responsiveness facing of un certain product demand. Leadingedge ¯rms are coming to understand requirements for manufacturing °exibility. Especially the Japanese companies ranked °exibility to introduce new products as their second, and to adjust production volume as their fourth competitive priorities (De Meyer et al. (1989)). Despite the growing importance of °exibility over the decades, ¯rms still struggle 1 to implement manufacturing °exibility (Gerwin (1993)). Many ¯rms struggle to make the costly investments in manufacturing °exibility due to the problem of recognizing the bene¯t of the °exibility. Flexibility is usually considered as a \backup" or an \insurance," and in many situations, °exibility does not contribute, or contributes very little, to manufacturers' revenue. At the same time, it is less common to quantify the bene¯ts, because demand uncertainty is usually not explicitly considered by the planners. Many manufacturers hesitate to invest a huge amount of money to achieve a high degree of °exibility. If plant can produce more than one product, then the degree of °exibility means the production e±ciency for products that can be produced by the plant. Hence, high degree of °exibility implies high productivity. In practice, °exibility does not come free, and higher the degree of °exibility, the higher is the cost. Manufacturers often seek a moderate degree of °exibility that would not cost much, but could hedge them against demand variability. Investing for the optimal degree of °exibility remains a crucial decision for many manufacturers. However, the academic literature often ignores the investment cost in °exibility. Most papers studying manufacturing °exibility do not consider the e±ciency loss incurred at switching, and they do not consider the possibly high costs associated with °exibility (Jordan and Graves (1995), Hopp et al. (2004), Iravani et al. (2005), etc.). Even with considerable degree of °exibility, changeover time (the time necessary for the process to be setup in order to change from making one product type to another) is still inevitable when the production is switched from one product to another. In some cases, the ability to build every product using same production capacity is impossible if the products are di®erent enough, although they share some common parts or procedures. 2 1.2 Research Objective and Scope The objective of this study is to model the e±ciency loss that occurred in the man ufacturing °exibility, and analyze the °exibility structure indices. We evaluate the structure performance based on structure index, which can rank structure perfor mance without precise information regarding the demand and capacity. In this thesis, we coin the term \cross production" to represent the ability to produce product A using a machine dedicated to product B, with certain e±ciency loss. For example, consider a ¯rm with two products and two types of partial °exible capacity. Each type of capacity is designed for a single product, but since the two products share some common features, the capacity for one product can also be used to produce the other product with some e±ciency loss. Cross production is a major source, and sometimes the only possibility, to realize °exibility on the supply side. The ability to conduct cross production to match supply with demand is crucial for a ¯rm. Lack of cross production may seriously decrease a ¯rm's market share, pro¯tability, and capacity utilization, which is illustrated by the following example. Chrysler's PT Cruiser was a new design based on the Neon, and it turned out to be a very fashionable model soon after its debut in 2000. Its dedi cated plant in Toluca, Mexico, was not able to satisfy the unexpected high demand. However, at the same time, the dedicated plant for the original Neon in Belvidere, Illinois, was underutilized. If Chrysler could make cross production, even with some e±ciency loss or additional costs, it has been estimated that up to $240M pretax pro¯t could have been gained. E±ciency loss in cross production may come from shrinking capacity, additional cost, or both. Shrinking capacity implies that fewer units of products will be pro duced if one type of capacity is used to produce the other type of product. The phenomenon of shrinking capacity in cross production is commonly observed in the industry. Productivity will decrease when a plant dedicated for one type of product is 3 used to produce another product, caused by speci¯cally designed machine, changeover time, or insu±ciently cross trained workers. Additional cost indicates that extra unit cost will be added if one type of product is produced using the other type of capacity. Production cost will increase when one type of product is produced in a plant that is dedicated for another type of product due to additional manufacturing process, changeover cost, or additional training to workers. Given that there are costs associated with creating and maintaining manufacturing °exibility, and di±culties managing the resulting complex system, it is desirable to understand the value of this °exibility in more depth. The following issues are relevant in the setting of manufacturing °exibility: °exibility type, °exibility mechanisms (how much °exibility, and where the °exibility should be introduced), and °exibility measurement. Gerwin(1993) argued persuasively that °exibility measurement is necessary to characterize and evaluate the uncertainty types, °exibility types and °exibility mech anisms. Without measurement, it is hard for the management to e®ectively assess °exibilityrelated choices, costs, achievability, performance bene¯ts and tradeo®s. Notwithstanding the importance and the constant interest raised by °exibility in academic and managerial circles, the measure of °exibility is still an underdeveloped subject, and no wellaccepted measure exists. Very limited work has been done on investigating the robustness of the suggested measurements (De Toni and Tonchia (1998)). In this study, we propose new measurements especially on the shrinking capacity case and the additional cost case. We are especially interested in developing simple methods that computes an index for each manufacturing structure, which can be used to predict which structure has better and more robust performance, without needing precise information regarding the patterns of the changes in the system. Specially, there are two goals in this work. First, we present an introduction 4 to cross production concept in the manufacturing °exibility design, especially the shrinking capacity and additional cost cases, and then model them in order to ¯t them into the manufacturing design. Second, we extend the work on the measurement of the manufacturing °exibility by new analysis and new constructions. 1.3 Organization of Thesis The thesis is arranged as follows. In Chapter 2, we review literature related to this thesis in two areas: manufacturing °exibility and graph expander theory. In chapter 3, we introduce the classical manufacturing °exibility model, SF(Structure Flexibility) matrix (Iravani et al. (2005)), and the basic concept in the subject of graph expansion (Fiedler (1973)). In Chapter 4, we set up the model of the shrinking capacity case, and establish the connection between it and SF matrix. We also demonstrate the graph expander theory in the shrinking capacity case. In chapter 5, we introduce another type of e±ciency loss, the additional cost case, in manufacturing °exibility, and model it using linear programming, then use the modi¯ed SF matrix and Laplacian matrix to get the structure index. Finally, we conclude and discuss future directions. 5 CHAPTER 2 Literature Review In this chapter, we review literature related to our research in the manufacturing °ex ibility and graph expander areas. Flexibility is emerging as one of the key competitive advantages for any manufacturing ¯rm in dealing with the increasingly complex man ufacturing environment. In the past two decades, numerous e®orts have been made to characterize and measure °exibility. These e®orts are classi¯ed and critically re viewed in the ¯rst part of this chapter. Graph expander has been a rapidly developing subject in discrete mathematics and computer science in the past three decades. It has been applied in many ¯elds, including network design, algorithms, coding, cryp tography, and pseudorandomness. We review the literature related to our study in manufacturing °exibility in the second part of this chapter. 2.1 Literature Review on Manufacturing Flexibility We organize the content of this part of the review into three basic streams: de¯nition and classi¯cation of manufacturing °exibility, manufacturing °exibility design, and manufacturing °exibility structure index. One stream of literature related to our research is de¯nition and classi¯cation of manufacturing °exibility. Sethi and Sethi (1990) categorized the °exibility application in eleven types, such as machine °exibility, operation °exibility, resource °exibility, etc. The literature often refers to manufacturing °exibility as \process °exibility." Shi and Daniels (2003) provided an extensive survey on the literature related to e business °exibility. \EBusiness °exibility," a new area of °exibility, becomes a key 6 interface between companies of all sizes and their supplies and customers. There are a series of papers about the °exibility design. Jordan and Graves (1995) have studied chain structure in supply chains in their classical °exibility design paper. They observed that well designed limited °exibility is almost as good as full °exibility in the singlestage manufacturing system with random demand and deterministic capacity. In addition, they proposed one measure, the maximal probability over all groupings or sets of products, to estimate the structure performance. Graves and Tomlin (2003) extended the former work to multistage manufacturing systems. The above two papers showed that limited °exibility has the greatest bene¯ts when con¯gured to chaining structure, which is de¯ned as a group of products and plants, which are all connected, directly or indirectly (Jordan and Graves (1995)). Many studies have been done about the application of chaining structure to design the manufacturing °exibility. Hopp et al. (2004) emphasized the power of chaining structures in CONWIP (CONstant WorkInProcess) production lines with cross trained workers. They proposed that if workers in the line are crosstrained according to a chain structure, then the line achieves a relatively high throughput compared to other crosstraining structures. Gurumurthi and Benjaafar (2004) viewed °exible queueing systems as a connected bipartite undirected graph, a similar representation of Aksin and Karaesmen (2007). Sheikhzadeh et al. (1998), Iravani et al. (2005, 2007), Jordan et al. (2004) and Chou et al. (2007) also highlight the properties of the chaining structure in di®erent production, maintenance and service environ ments. Lien et al. (2005) introduced the chained shipment structure and showed the superiority of this chain structure over the grouping con¯gurations. Aksin and Karaesmen (2007) provided analytical comparison results on °exibility structure in their paper. They applied network °ow problem to the study of maximal throughput of °exible structure, and provided a theoretical study on the symmet ric °exible system, and derived submodularity property on the °exibility structure. 7 They established certain °exibility design principles for service and manufacturing systems. In our work, we adopt their analytical approach. The performance measure is a key part of manufacturing °exibility. Flexibility measures are needed to test theories and make capital investment decisions. A key paper about the manufacturing °exibility index was written by Iravani et al. (2005). Their paper focused on strategiclevel issues of how °exibility can be created by using multipurpose resources such as crosstrained labor, °exible machines, or °exible factories. They proposed the SF indices as the measure for the °exibility structure. The SF indices are simple tractable measures, which can be used to rank the structures performance. Chou et al. (2007) proposed another index based on the concept of graph expander, which is widely used in graph theory ¯eld. This index has more theoretical background, and just has one index that has more use value than SF indices. In this thesis, we use the methods of Iravani et al. (2005) and Chou et al. (2007) to the shrinking capacity and additional cost cases. 2.2 Literature Review on Graph Expander We organize the content of the literature on graph expander into two basic streams: theory of graph expander and graph expander application. The ¯rst stream corre sponds to the basic concept of graph expander, the second stream is focused on its application in manufacturing design. Expander is a graph for which any small subset of vertices has a relatively large neighborhood. Bassalygo and Pinsker (1973) ¯rstly introduced graph expander in the ¯eld of communication networks. Intuitively, a regular undirected graph is an expander if it is highly connected. That is, it is easy to get from any vertex to any other vertex in very few steps. Normally, we also impose that they have low degree, because in many applications the cost of the graphs is related to their degree (Xiao (2003)). 8 Many measurements have been used to quantify this expansion property. Such measures include vertex expansion and edge expansion properties. They unfortu nately are hard to compute. However, a series of works by Alon (1986), Alon and Milman (1985), and Tanner (1984) built the relationship between the expansion of graph with the second largest eigenvalue of the graph. This provides us an e±ciently computable method of the expansion of a graph. More importantly, it allows us to apply the tools of linear algebra in analyzing expander graphs. Reingold et al. (2002) built large scale near optimal expanding graphs by \zigzag," which is a recursive construction of the expander graph families. Graph expander has spawned research in pure and applied mathematics, with wide applications in many areas. Expander graph found applications in the design of explicit supere±cient communication networks, constructions of errorcorrecting codes with very e±cient encoding and decoding algorithms, derandomization of ran dom algorithms, and analysis of algorithms in computational group theory (Sarnak (2004)). Chou et al. (2007) built the connection between graph expander and process °exibility, and showed that e±ciently expander gives rise to good process °exibility, and mathematically proved the existence of good partial °exibility structure in iden tical demand and supply case. The main di®erence of our work compared to other researchers is that we study the cross production, and model two special cases: shrinking capacity and additional cost { which are two main sources of e±ciency loss. In this thesis, we study the manufacturing °exibility models with random demand and deterministic capacity. In addition, we construct the indices for those two special cases using the SF matrix and the graph expander. 9 CHAPTER 3 Methodology In this chapter, two di®erent methods are investigated to create index for manufac turing °exibility in the shrinking capacity case and the additional cost case. This chapter provides a brief history of the two methods followed by the details of speci¯c implications for this research. 3.1 Manufacturing Flexibility Model In this section, we study the basic concept of the manufacturing °exibility model in a general nm (n suppliers and m demands) structure. We also introduce the optimal solutions for this nm structure. Aksin and Karaesmen (2007) and Chou et al. (2007) proposed a bipartite graph G = (A [ B; F) to represent the °exible structure. The lefthandside nodes A = f1; 2; ¢ ¢ ¢ ; ng with capacity (q1; q2; ¢ ¢ ¢ ; qn) denote the suppliers and the righthand side nodes B = f1; 2; ¢ ¢ ¢ ;mg with capacity (d1; d2; ¢ ¢ ¢ ; dm) represent the demands. Whenever a demand type j 2 B can be supplied by the supplier i 2 A, an arc (i; j) 2 F with in¯nite capacity is added to the the network. The network in Figure 3.1 illustrates a case where all the suppliers can serve all the demands. The decision variables xij denote the amount of demand for product j supplied by plant i; sj is the shortage of demand j, that is the amount of demand for product j that cannot be satis¯ed. We evaluate a manufacturing °exibility structure in term of the expected de mand shortage that cannot be covered by the supplies. The minimum shortage for a 10 G, S(G), can be acquired by solving the following linear program (Jordan and Graves (1995)): S(G) = min Xm i=1 sj s:t: X (i;j)2F xij + sj ¸ dj 8 j = 1; 2; ¢ ¢ ¢ m: X (i;j)2F xij · qi 8 i = 1; 2; ¢ ¢ ¢ n: (3.1) n1 n 2 3 1 m 2 3 1 4 Supply Demand s t q1 q2 qn1 qn d1 d2 dm q3 d3 d4 Figure 3.1: Total Flexibility structure; n Suppliers Service All the m Demands. By Jordan and Graves(1995), the optimal objective value of (3.1) equals to (3.2). The maximization in (3.2) is over all subsets M (including the null set) of the index set f1; 2; ¢ ¢ ¢ ;mg . That is, the maximization is over all combinations of the products. For any given subset of products M, P(M) is the subset of plants that can produce at least one of the products in M. That is, P(M) = fi 2 A : (i; j) 2 F; j 2 Mg. The 11 optimal objective value of (3.1) equals to: S(G) = max 8< :0; max M 2 4 X j2M dj ¡ X i2P(M) qi 3 5 9= ;: (3.2) The problem of maximizing the output generated by a given con¯guration for a demand realization (d1; d2; ¢ ¢ ¢ ; dm) is equivalent to the maximum °ow problem for this network. So the maximal output of above structure is : O(G) = Xm j=1 dj ¡ S(G) = min M 8< : Xm j=1 dj ¡ X j2M dj + X i2P(M) qi 9= ; = min M 8< : X j =2M dj + X i2P(M) qi 9= ;:(3.3) Jordan and Graves (1995) and Chou et al. (2007) showed similar results. Intuitively, we can think (3.3) is the consequence of the max°owmincut theorem where the arc between A and B has in¯nite capacity: the maximal output of a structure corresponds to the minimal cut in the capacitated production network. In this study, we adopt the manufacturing °exibility structure model as shown above, and apply it to the shrinking capacity and the additional cost case. 3.2 Chain Structure This section provides a brief study of chain structure, which is de¯ned as a group of products and plants which are all connected, directly or indirectly. As mentioned before, Jordan and Graves (1995) showed that chain structure can greatly increase the expected throughput of manufacturing °exibility structure. In a chain structure, excess capacity of any plant can be shipped to any other products via production assignment schedule. For example, in the right structure of Figure 3.2, if demand for A is greater than expected, and demand for D is less than expected, with one long chain the production capacity for product D can be transferred to demand A. So the chain structure can accommodate increased demand of node A and decreased demand of node D. However, the left structure in Figure 3.2 12 cannot ship the excess capacity of demand D to demand A because there is no link between node D and node A. 1 2 3 A B C 4 D 1 2 3 A B C 4 D Supply Demand Supply Demand Figure 3.2: Two Manufacturing Flexibility Structures. In the numerical analysis in subsequent chapters, we are particularly interested in the chain structure performance because of e®ectiveness of the chain structure compared to other structures. 3.3 SF Matrix In this section, we review the SF (Structure Flexibility) matrix, ¯rst introduced in Iravani et al. (2005). We use the °exibility structure shown in Figure 3.3 to describe this method. Figure 3.3 indicates two di®erent paths from demand B to demand D. The demand of each plant is random so that the demand B decreases ±, and the demand D increases ±. We assume the capacity is tight, so that the excess capacity ± for demand B need 13 1 2 3 A B C 4 D Supply Demand 1 2 3 A B C 4 D Supply Demand Figure 3.3: Two Paths From Demand B to Demand D. to be shipped to demand D. Each path represents a di®erent way of shipping the unused production capacity for product B to produce product D. The ¯rst path on the left, B ! 2 ! C ! 3 ! D, represents the following shipping of production capacity: there exist excess ± unit capacity available for demand B. Hence, supply 2 can produce amount ± more of product C, which can make supply 3 produces more ± units of demand D in order to respond the extra ± unit demand for demand D. The path on the right of Figure 3.3 is another way of transferring excess capacity for product B to satisfy the extra demand for demand node D: B ! 1 ! A ! 4 ! D. Iravani et al. (2005) measured structure °exibility by counting the total number of nonoverlapping paths a system can use to respond to a particular change in demand. They proposed SF matrix to quantify the ability to shift excess capacity to respond to change in demand. Let mij be the total number of nonoverlapping paths by which the excess capacity for product i can be transferred to produce product j. Iravani et al. (2005) argued that shipping excess capacity from product i to produce product i does not make clear sense. So they de¯ned mii be the total number of arcs connected 14 to demand node i. Consequently, the SF matrices for structures in Figure 3.2 become Mleft = 2 66666664 2 2 0 0 2 2 0 0 0 0 2 2 0 0 2 2 3 77777775 ; Mright = 2 66666664 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 77777775 : It is easy to see that right structure of Figure 3.2 to respond to changes uses more paths than left structure of Figure 3.2. In our study, we extend the de¯nition of mij to be total numbers of nonoverlapping paths by which the excess capacity of plant i can be shipped to produce product j. This de¯nition is applicable to mii because this de¯nition makes clear sense for the diagonal element of SF matrix. 3.3.1 SF Index To be able to compare the °exibility of two di®erent structures, Iravani et al. (2005) further compacted the information in SF matrix in the form of two scalars, \SF indices," which consists of mean value and dominant eigenvalue. Mean Value: It is clear, comparing Mleft and Mright of the structures shown in Figure 3.2, that SF matrices with larger elements represent more °exible structures. At the same time, matrices with larger elements will have a larger mean, which is de¯ned as the mean of all the elements in SF matrix. Although the mean of the elements of the SF matrix is an indicator of how large the elements of the matrix are, it is not sensitive to the location of the larger elements of the matrix. It is easy to see that di®erent matrix maybe have same mean value. This is one important reason why the authors considered another index, the dominant eigenvalue. Dominant Eigenvalue: Because SF matrix is real, symmetric, and nonnegative, its eigenvalues are real and nonnegative. So for a system with n supplies and n demands, the SF matrix has n eigenvalues ¸1; ¸2; ¢ ¢ ¢ ; ¸n. The biggest eigenvalue is 15 ¸ = maxf¸1; ¢ ¢ ¢ ; ¸ng, which is an indication of the magnitude of elements of a matrix. Iravani et al. (2005) showed that, as any element of the SF matrix increases (i.e., more °exibility), the dominant eigenvalue of the matrix increases. The eigenvalue index is sensitive to the location and variation of the elements of the SF matrix, and di®erent matrices with the same mean index may have di®erent dominant eigenvalues. In this study, we extend the SF matrix construction method to the shrinking capacity and additional cost case. In additional, we use SF indices to analyze the structures in these two special cases. As mentioned before, SF matrix lacks of theoretical support, so we consider an other index, expander index, which is much easier solved than SF index. 3.4 Graph Expander In this section, we introduce the basic concept about graph expander theory, and the connection between graph index and manufacturing °exibility. Expander graphs are one of the most useful tools of theoretical computer science and discrete mathematics, motivating many applications since their introduction in the 1970s. Let G = (V;E) be an directed graph with n nodes and m edges, where V and E represents vertices and edges. The incidence matrix of G is a n£m matrix such that Til = ¡1, if the edge l leaves node i, Tjl = 1, if it enters node j and 0 otherwise. The Laplacian matrix L of G is the n £ n matrix L = TT0. Clearly, the L is independent of what orientation is chosen for. L is positive semide¯nite, and L1 = 0, where 1 is the vector of all ones. Let 0 = ¸1 · ¸2 · ¢ ¢ ¢ · ¸n be the eigenvalues of L. The second smallest eigenvalue ¸2(L) has been used to measure connectivity, and is called the algebraic connectivity of the graph G (Fiedler (1973)). 16 3.4.1 Expander Index There are many reasons the algebraic connectivity is considered to be a measure of how wellconnected a graph is. For example, if G1 = (V;E1) and G = (V;E2) are such that E1 µ E2, then ¸2(L1) · ¸2(L2). That is, a better connected graph (on the same vertex set) has a greater algebraic connectivity. In addition, the algebraic connectivity has a direct connection to the number of connected components in a graph: G is connected if and only if ¸2(L) > 0; in fact, the multiplicity of the eigenvalue 0 is exactly equal to the number of connected components in G. ¸2(L) > 0 means that there is only one zero eigenvalue, then we can conclude that the graph is connected (Fiedler (1973))). Chou et al. (2007) found that many important results in the literature of graph expander are closely related to the results in the process °exibility ¯eld in the following two ways. First, Jordan and Graves (1995) suggested that a \welldesigned" sparse structure, which has a small °exibility, is almost as °exible as the total °exibility structure. Pinsker (1973), however, stated that there exists a sparse structure with O(n) arcs that has almost the same expansion as a complete graph. Actually the \welldesigned" sparse structure and total °exibility structure correspond with the sparse structure and the complete graph. Second, Iravani et al. (2005) proposed that the °exibility of a structure can be measured by the largest eigenvalue of its SF matrix. This statement corresponds to the ¯nding of Tanner (1984), that the expansion level of a graph is bounded by the spectral gap. Based on the two observations, Chou et al. (2007) built the relationship between the graph expander and the nn manufacturing °exibility structure. In this study, we extend their results to the shrinking capacity and additional cost case. 17 CHAPTER 4 Shrinking Capacity Case 4.1 Introduction In this chapter, we study the manufacturing °exibility index in shrinking capacity case. To evaluate the structural performance, we build up the SF(Structure Flexibil ity) matrix and Laplacian matrix in the shrinking capacity case, and examine the SF indices and expander indices in di®erent manufacturing structures. We ¯rst test the chaining structure. Then we test the performance of SF indices and expander indices in the general structure (nonchaining structure). 4.2 Model in Shrinking Capacity Case In this section, we de¯ne specialized production and cross production, and model the shrinking capacity case in linear programming. First, we de¯ne the specialized production and cross production as follows: De¯nition 4.1 Specialized Production: A plant can produce a product without e±ciency loss. De¯nition 4.2 Cross Production: For some plants, there exist demands that the plant produces with shrinking capacity. For simplicity, we use nn °exibility manufacturing in Figure 4.1 to illustrate the two de¯nitions mentioned above. In the nn structure, we distinguish them in the following way: specialized production(1¡1; 2¡2; 3¡3; :::; n¡n manufacturing) and cross production (i ¡ j(i 6= j) manufacturing). 18 n1 n 2 3 1 n1 n 2 3 1 n2 4 Supply Demand s t q1 q2 qn2 qn1 qn d1 d2 dn1 dn q3 d3 d4 Figure 4.1: nn Partial Flexibility Structure It is very common that the productivity of the plant could have some decrease in the cross production. Hence, we introduce the concept \shrinking factor." De¯nition 4.3 Shrinking Factor: In the manufacturing °exibility structure, the shrinking factor of i ¡ j manufacturing is kij = qj i qi , and qj i means the amount of product j we can produce with supply i. In our problems, specialized production does not cause a decrease in the capacity, and cross production cause the decrease in some degree. That is: kij ( = 1 if i = j, < 1 if i 6= j. Next, we set up the model of shrinking capacity in linear programming. In our op timization problem, we use the the minimal shortage, S(G), as the objective function. The minimal shortage of nm structures (n suppliers and m demands) in shrinking 19 capacity case can be acquired by solving the following linear program: S(G) = min Xm j=1 sj (4.2) s:t: X (i;j)2F xij + sj ¸ dj 8 i = 1; 2; ¢ ¢ ¢ n; X (i;j)2F xij kij · qi 8 j = 1; 2; ¢ ¢ ¢ m: The above formulation is used in the subsequent numerical analysis in this chapter. 4.3 SF Matrix of Shrinking Capacity Case In this section, we extend SF matrix to the shrinking capacity case, and introduce the algorithm for the construction of SF matrix in the shrinking capacity case. For simplicity, in this section, we focus on the nn °exibility manufacturing structure to show how to build the SF matrix in the shrinking capacity case. We assume that the full (noshrinking) capacity of each supply node is 1. SF matrix was proposed by Iravani et al. (2005), which is a key paper for the study of the °exibility manufacturing structure. They created the SF matrix in the following way: (1) for nondiagonal element: \the total number of nonoverlapping paths a system can use to respond to a particular change in demand," which can be obtained by solving the maximal °ow problem. (2) for diagonal element: the number of arcs connected to the corresponding supply node. In our model, we set the element of the SF matrix as the maximal °ow from each supply node to each demand node. Our method extends the work of Iravani et al. (2005) in the following way: (1) for nondiagonal element, for the demand node i, the total capacity of nonoverlapping paths a system can use to respond to a particular change in demand equals the maximal °ow from each supply node i to demand node j. (2) for diagonal element: the arc number connected to the corresponding supply node i is extended as the maximal °ow from supply node i to demand node i. Notice, 20 the maximal °ow here is di®erent from the traditional maximal °ow problem, because after passing through each arc, we need to consider the capacity loss. We use manufacturing °exibility structure shown in Figure 4.2 as example, the diagonal element, m11, of SF matrix is 1 £ (1 + k12k23k34k41) = (1 + k12k23k34k41), which is the maximal °ow from supply node 1 to demand node 1; the nondiagonal element, m12, of SF matrix equals 1 £ (k12 + k41k34k23) = (k12 + k41k34k23), which is the maximal °ow from the supply node 1 to demand node 2. 1 2 3 4 1 2 3 4 Plant Demand x11/1 x12/k12 x23/k23 x22/1 x33/1 x34/k34 X44/1 x41/k41 s t q1 q2 q3 q4 d1 d2 d3 d4 Figure 4.2: 44 Manufacturing Flexibility Structure in Shrinking Capacity Case. To get the elements of SF matrix, Iravani et al. (2005) used a maximal °ow formulation to ¯nd the maximum number of units of source e®ort that can be shipped from a demand start node, i, to a demand sink node, j, in a particular structure. Unfortunately, their methodology cannot be used directly to the shrinking capacity case, because of the multiplication of shrinking factors associated with each arc in the path. For example, if there exists a route R1 = 1 ¡ 2 ¡ 2 ¡ 3 from the source node 1 to demand node 3, as shown in Figure 4.2. The maximal °ow of this route is k12k23, 21 not min(k12; k23), given the full capacity of node 1 is 1. With the increasing of °exibility in the manufacturing structure, it is not easy to solve the maximal °ow between supply node and demand node. In chain structure, there are only two paths from each supply node to demand node. But for nonchaining structure, it is not easy to get the maximal °ow between two nodes. This motivates for our algorithm in the next section. 4.3.1 Algorithm for SF Matrix Construction in Shrinking Capacity Case The above maximal °ow problem can be transferred to the shortest path problem. We want to get the route p 2 P, so that Q (i;j)2p kij of the route be the maximal value in all routes P. Because log Q (i;j)2p kij = P (i;j)2p log kij , and the maximal points of Q (i;j)2p kij and log Q (i;j)2p kij are equal, the problem can be easily trans ferred into maxp2P P (i;j)2p log kij . Because 0 · kij · 1, maxp2P P (i;j)2p log kij = minp2P P (i;j)2p(¡log kij). Let ¡log(kij) represent the distance from node i to node j. The °ow between node i and j is transformed to solve the distance between i and j. For example, the °ow of route R1, as we mentioned in the last section, can be acquired by exp(¡d13), where d13 = (¡log k12) + (¡log k23) + (¡log k22) = (¡log k12) + (¡log k23). After getting the shortest route between two nodes by this method, we can delete the arcs that this route passes, and then ¯nd the second shortest path; repeat this until there are no paths available. The shortest path problem can be easily solved by several well established algorithms, such as Dijkstra's algorithm. The algorithm, which gets the maximal °ow from node s to t, is as follows: Step 1: To input incidence matrix T of the structure, s and t; Initialize i = 1. Step 2: Calculate the shortest path pi and its distance di, which is the summation of the absolute values of logarithms of shrinking factors that the path contains. Step 3: Delete the arcs that pi passes, and check if the node s is connected to t. If 22 they are disconnected, go to Step 4; if there are still routes from node s to t, then update the incidence matrix T, set i = i + 1, and go to Step 2. Step 4: Calculate the element of mst of SF matrix, mst = P i exp(¡di). 4.4 Graph Expander As mentioned before, SF matrix indices lack the mathematical support. At the same time, graph expander theory can help us get another structure index, which has more mathematical supports than SF matrix. This motivates for the graph expander index in this section. In this section, we study the relationship between graph expander theory and manufacturing °exibility in the shrinking capacity case. In addition, we propose a method to construct expander index in the shrinking capacity case. The expander graph is a graph G = (V; F), in which every subset S of vertices expands quickly, in the sense that it is connected to many vertices in the set S of complementary vertices. Chou et al. (2007) gave the formal de¯nition of the graph expander in the bipartite graph as shown in De¯nition 4.4. To make it clear, we need the following notation: The degree of a vertex v is deg(v), which is the number of edges incident to v. The number of vertices in set S is jSj. N(S) denotes the neighborhood of set S, that is, N(S) = fj 2 B : (i; j) 2 F, for some i 2 Sg . De¯nition 4.4 A bipartite graph G = (A S B; F), with partite sets A and B, and edge set F, is a (®; ´; ¢)expander if deg(º) · ¢ for every º 2 A, and for all S ½ A, with jSj · ®jAj, then jN(S)j ¸ ´jSj. For simplicity, we assume jBj = jAj = n. It is clear that ®´ · 1, because jAj ¸ jN(S)j ¸ ´jSj holds for any set S with jSj · ®jAj. Intuitively, a bipartite graph expander is a graph with high connectivity, i.e., the neighborhood of small 23 subsets in A is expanded by a factor ´ > 1. We are particularly interested in the graphs that have a low degree, because in the real world we expect less connectivity but more °exibility. A series of work initiated by Pinsker (1973), Friedman (2003) and Chou et al. (2007) showed that in fact there exist speci¯c graphs that have this property with high probability as indicated in as shown in Lemma 4.1. As mentioned before, Chou et al. (2007) indicated that the connection between the chain structure and the full °exibility structure in the graph expander perspective in the following lemma. Lemma 4.1 In the problem with n supplies (each with capacity qi) and n demands (with random demand Dj), if (i) E(Dj) = ¹ for all j, (ii) P(Dj > ´¹) = 0 for all j and (iii) qi = ¹ for all i, then there is a partial °exible structure F, with jFj · n¢, which attains nearly the bene¯ts of the full °exibility model. i.e., E[z¤(F)] · E[z¤(A£ B)] + n"¹, for any " > 0, and for all suitably large n. In this lemma, z¤(F) and z¤(A £ B), respectively, denote the excess °ow of a partial °exible structure F and full °exible structure A£B. We can see clearly, there exists partial °exible structure, which can get the most advantage of full °exibility structure. 4.4.1 Graph Expander in the Shrinking Capacity Case We extend Chou et al.'s (2007) work to the shrinking capacity case. The following analysis for the shrinking capacity case parallels with the analysis of Chou et al. (2007). We consider that there are n supply and n demand nodes in the °exibility problem. All demand nodes have demand Dj ; j 2 f1; 2; ¢ ¢ ¢ ; ng, with mean ¹, whereas all supply nodes have supply qi; i 2 f1; 2; ¢ ¢ ¢ ; ng. We use the results of Chou et al. (2007) to derive a few important insights for the process °exibility problem in the shrinking capacity case. 24 Theorem 4.1 In the nn shrinking capacity °exibility structure with shrinking factor kij , when supply i produces product j, if (i) qi = ¹ for all i, (ii) P(Dj > ´k¹) = 0 for all j and (iii) E(Dj) = ¹ for all j, then there is a partial °exible structure F, with jFj · n¢, which attains nearly the bene¯ts of the full °exibility model. i.e., E[S(G)] · E[S(A £ B)] + n"¹, for any " > 0, and for all suitably large n, where " = 1 ¡ ®´k, k = min(i;j)2F kij . Proof. In this proof, we apply the method of Chou et al. (2007) and extend their method to the shrinking capacity case. From (3.2), under the full °exibility (no shrinking capacity) model, we expect the shortage to be E " Xn j=1 Dj ¡ Xn i=1 qi #+ : For a partial °exibility model, let P(M) denote the set of demand nodes M is linked to. From (3.2), the average shortage is less than or equal to E 2 4max MµF 2 4 X j2M Dj ¡ X i2P(M) kqi 3 5 3 5 + ; where k = min kij . Let D¤ j = 8>< >: Dj ; if Pn i=1 Dj · n¹, Dj µ Pn¹ n i=1 Dj ¶ ; if Pn i=1 Dj > n¹. It is easy to see Pn i=1 Dj = Pn i=1 D¤ j , given Pn i=1 Dj · n¹. Then for each subset M, we have X j2M Dj ¡ X i2P(M) kqi = " X j2M Dj ¡ X j2M D¤ j # + 2 4 X j2M D¤ j ¡ X i2P(M) kqi 3 5 = " X j2M Dj ¡ X j2M D¤ j # I Ã Xn j=1 Dj > n¹ ! + 2 4 X j2M D¤ j ¡ X i2P(M) kqi 3 5; where I(¢) denotes the indicator function. 25 If the process structure corresponds to an expander graph (®; ´; ¢), then by the de¯nition of expander graph, we have X j2M D¤ j ¡ X i2P(M) kqi · X j2M D¤ j ¡ ´jMj¹k; if jMj · ®n; and by the assumption that P(Dj > ´k¹) = 0 for all j, then the following holds almost surely. X j2M D¤ j ¡ X i2P(M) kqi = X j2M Dj ¡ X i2P(M) kqi · 0; if jMj · ®n: Since P(M) must contain at least ´ min(jMj; ®n) supply nodes, then we have X j2M D¤ j ¡ X i2P(M) kqi · X j2M D¤ j ¡ ´®n¹k · (1 ¡ ®´k)n¹; if jMj ¸ ®n: Thus X j2M Dj ¡ X i2P(M) kqi · " X j2M Dj ¡ X j2M D¤ j # I Ã Xn j=1 Dj > n¹ ! + [(1 ¡ ®´k)n¹] : Therefore E(S(G)) · E " max MµF "Ã X j2M Dj ¡ X j2M D¤ j ! I Ã Xn j=1 Dj > n¹ ! + (1 ¡ ®´k)n¹ ##+ = E " max MµF "Ã X j2M Dj ¡ X j2M Dj Ã Pn¹ n j=1 Dj !! I Ã Xn j=1 Dj > n¹ ! + (1 ¡ ®´k)n¹ ##+ = E " Xn j=1 Dj ¡ n¹ #+ + (1 ¡ ®´k)n¹: It is clear that 1 ¡ ®´k < 1, then set " = 1 ¡ ®´k, which is a positive number. Then we get E[S(G)] · E[S(A £ B)] + n"¹ as claimed. Theorem 4.1 shows that there exists partial °exibility structure that can still attain the most of the bene¯t of full °exibility structure even with the shrinking in the capacity. Next, we will introduce the methodology for the graph expander index construction in the shrinking capacity case. 26 For a bipartite graph G = (A S B; F), the incidence matrix T is de¯ned in the following way: each column of T, Tl, characterizes an edge l 2 F, where edge l connects node i 2 A to j 2 B, by letting Tli = ¡1, Tlj = 1 and Tlk = 0, 8 k 6= i; j. The Laplacian matrix L = TT0 is a positive semide¯nite matrix. The connectivity of the graph G can be measured by the second smallest eigenvalue ¸2(L) of L, also known as the algebraic connectivity of G. For the shrinking capacity case, we consider it is a weighted graph and de¯ne the incidence matrix as the following way: Each column of T, say Tl, characterizes an edge l 2 F, where edge l connects node i 2 A to j 2 B, by letting Tli = kij , Tlj = ¡kij and Tlk = 0, 8 k 6= i; j (Merris (1994), Wallis (2000)). The relationship between ¸2(L) and the connectivity property of G is wellknown in graph theory ¯eld (Fiedler (1973), Ghosh and Boyd (2006)). Especially, Chou et al. (2007) proposed that ¸2(L) can be used as an index to rank process °exibility structures. In general, a graph with more links is more °exible, and connected graphs are generally more °exible than disconnected graphs. In the subsequent numerical study, we consider ¸2(G) of the weighted graph as the indicator of structure G. 4.5 Numerical Analysis In this section, we report the results of the computational study that we performed based on the shrinking SF matrix and graph expander. Our experiment consists two parts: one is about the chaining structure, and the other is about the general struc ture. To evaluate the e®ectiveness of various indices, we use E[S(G)], the expected shortage of structure G, as the indicator of how °exible structure G is. 4.5.1 Chaining Structure In this section, our numerical study tests a 44 manufacturing structure as shown in Figure 4.2. The arcs emanating from the source node s have capacities (q1; q2; q3; q4), 27 and the arcs, which end in the sink node t have capacities (d1; d2; d3; d4). The °ow in arcs between the plant i node and demand node j is xij . The shrinking factor between supply node i and demand node j is kij . In the simulations of this section, each demand is uniform distribution in the interval [0; 8); the capacity of each plant is 5. We use XpressIVE version 1.17.12 to implement the optimization problem, and create the random demand by function random. First, we test the SF indices in the chaining structure. Following our construction method, the shrinking SF matrix is M = (Mij)4£4: M = 2 66666664 1 + k12k23k34k41 k12 + k41k23k34 k12k23 + k41k34 k12k23k34 + k41 k12 + k23k34k41 1 + k23k34k41k12 k23 + k12k41k34 k23k34 + k12k41 k23k12 + k34k41 k23 + k34k41k12 1 + k23k12k41k34 k34 + k23k12k41 k41 + k33k23k12 k34k23 + k41k12 k34 + k41k12k23 1 + k41k12k23k34 3 77777775 : We have eight di®erent shrinking structures, and the mean value and dominant real eigenvalue of each structure is shown in Table 4.1. In Table 4.1, as for the mean values: structure 1 equals to structure 5, structure 2 equals to structure 6, structure 3 equals to structure 7, structure 4 equals to structure 8. Our numerical study consists of 100 cases generated by varying the demands. For each scenario, we calculate the minimal shortage facing the sampling demand. Hence we can get a average shortage for each structure after running 100 scenarios. The results are shown in Figure 4.3. In this graph, the horizontal axis represents the av erage shortage, and the vertical axis represents the mean value or biggest eigenvalue of SF matrix. The numbers beside nodes are structure numbers. We can see that: as the average shortage becomes smaller, the mean value becomes bigger. The same occurs for the biggest eigenvalue. The detail simulation results are attached in Ap pendix A. Simulation results provide evidence that SF index is useful in predicting the performance rank of manufacturing °exibility in shrinking capacity case. 28 3 6 2 1 8 4 5 7 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 80 90 100 110 120 130 140 150 160 170 180 190 Average Shortage Mean Value and Biggest Eigenvalue Mean Value Biggest Eigenvalue Figure 4.3: SF Matrix Index (the number beside each node is the structure it is associated with) 29 Structure 1 2 3 4 5 6 7 8 k12 0.5 0.5 0.3 0.3 0.4 0.65 0.4 0.47 k23 0.5 0.6 0.3 0.7 0.4 0.65 0.4 0.47 k34 0.5 0.7 0.3 0.3 0.6 0.65 0.2 0.47 k41 0.5 0.8 0.3 0.7 0.6 0.65 0.2 0.47 Mean Value 0.703 0.960 0.461 0.664 0.703 0.960 0.461 0.664 Biggest Eigenvalue 2.813 3.843 1.842 2.653 2.818 3.841 1.859 2.654 Table 4.1: Shrinking Capacity Case Next, we test the performance of expander index in the chaining structure. Based on our construction method, the incidence matrix of manufacturing °exibility struc ture shown in Figure 4.2 is the following T = 2 6666666666666666666664 ¡1 ¡k12 0 0 0 0 0 0 0 0 ¡1 ¡k23 0 0 0 0 0 0 0 0 ¡1 ¡k34 0 0 0 0 0 0 0 0 ¡1 ¡k41 1 0 0 0 0 0 0 k41 0 k12 1 0 0 0 0 0 0 0 0 k23 1 0 0 0 0 0 0 0 0 k34 1 0 3 7777777777777777777775 : We compute the second smallest eigenvalue of Laplacian matrix of weighted graph, which is L = TT0. The results are shown in Table 4.2. We plot the results shown in Table 4.2 in Figure 4.4. In this graph, the horizontal axis represents the average shortage, and the vertical axis represents the second smallest eigenvalue of Laplacian matrix. The numbers beside nodes are structure numbers. We can see that the main trend is: as the shortage becomes bigger, the second smallest eigenvalue becomes 30 smaller. Simulation results provide evidence that expander index is useful in pre dicting the performance rank of manufacturing °exibility in shrinking capacity case. Structures 1 2 3 4 5 6 7 8 k12 0.5 0.5 0.3 0.3 0.4 0.65 0.4 0.47 k23 0.5 0.6 0.3 0.5 0.4 0.65 0.4 0.47 k34 0.5 0.7 0.3 0.3 0.6 0.65 0.2 0.47 k41 0.5 0.8 0.3 0.5 0.6 0.65 0.2 0.47 ¸2(G) 0.219 0.279 0.086 0.086 0.181 0.337 0.05 0.197 Table 4.2: Shrinking Capacity Case 6 2 1 8 5 4 7 3 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 80 100 120 140 160 180 200 Average Shortage Second Smallest Eigenvalue Figure 4.4: Graph Expander Index(the number beside each node is the structure it is associated with) However, there are small oscillations of expander index curve, such as Structure 5, 8 and Structure 7, 3. This phenomenon probably is caused by the nature of expander index, which is a bound for the connectivity property of graph, not the exact value of graph connectivity. We can see similar result for the nonchaining structure. 31 4.5.2 General Structures In this section, we will analyze the nonchaining structure, and use our indices to the shrinking capacity case. We use a set of numerical examples from Iravani et al. (2005) to test the performance of expander index and the SF index. Consid ering the set of structures facing uniform demand in the interval [0; 8), ¯xed ca pacities q = (5; 5; 5; 5; 5; 5; 5; 5), and the same shrinking factor kij = 0:5; 8 i; j 2 f1; 2; 3; 4; 5; 6; 7; 8g as shown in Figure 4.5. We use XpressIVE version 1.17.12 to implement the optimization problem. Structures 1 2 3 4 5 6 7 8 9 ¸2(G) 0.06 0.05 0.07 0.25 0.09 0.08 0.59 0.25 0.52 Mean Value 0.37 0.37 0.59 0.76 0.74 0.78 1.11 1.12 1.42 Biggest Eigenvalue 2.9883 3.29 5.56 6.11 6.33 6.33 8.86 9.29 11.5 E(S(G)) 187.096 571.145 323.468 112.827 110.464 107.289 87.229 86.468 79.674 Table 4.3: SF Structures The performance of various indices are as shown in Table 4.3. We plot the results shown in Table 4.3 in Figure 4.6. The numbers beside nodes are structure numbers. From the Figure 4.6, we can see that biggest eigenvalue of SF matrix ranks the structures almost in line with the order obtained from the sampling estimation: as the shortage increase, the index decreases. But the biggest eigenvalue has a signi¯cant decrease at Structure 1 (Figure 4.5) as shown in Figure 4.6. Iravani et al. (2005) mentioned that the biggest eigenvalues can be considered as an indication of the magnitude of elements of a matrix. As any element of the SF matrix increases (i.e., more °exibility), the biggest eigenvalue of the matrix increases. Because Structure 1 is a chaining structure which has less arcs compared to other structures with similar performance. So dominant eigenvalue has a 32 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 11 12 13 14 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 4 5 6 7 8 A B C D E F G H 1 2 3 4 5 6 7 8 A B C D E F G H 1 2 3 4 5 6 7 8 A B C D E F G H 15 16 17 18 19 Figure 4.5: SF Structures 33 big decrease at Structure 1. Another potential reason for this phenomenon is that in structures 2 and 3, there are very few arcs for specialized production (Structure 2 has 3 arcs, and Structure 3 has 6 arcs), and this makes E[S(G)] of these two structures very high when e±ciency loss exits in cross production. While, for other seven structures, each product has dedicated plant. Therefore, it is not fair to compare structures 2 and 3 to other structures directly. On the other hand, the mean value index ranks the structures in a similar order. This implies SF matrix does not perform good to compare chaining and nonchaining structure. 5 2 3 1 6 4 7 8 9 0 2 4 6 8 10 12 50 150 250 350 450 550 Indices Expander Biggest Eigenvalue of SF Matrix Mean Value of SF matrix Figure 4.6: Indices for SF Structures (the number beside each node is the structure it is associated with) We can see that expander index ranks the structures almost in line with the order obtained from the sampling estimation: as the shortage increases, the expander index decreases. Especially, expander index perform well to compare chain and nonchain structure well. However, there are small oscillations in the expander index curve, such as Structure 7, 8 and 9. As mentioned before, this phenomenon probably is caused by the nature of expander index, which is a bound for the connectivity property of 34 graph, not the exact value of graph connectivity. However, we noticed that the performance di®erence among some di®erent struc tures is quite small, it is possible that the slight di®erence in ordering actually arises from the small number of sampling. The results, however, suggest that the concept of graph expander and SF matrix can be used as the index to rank process °exibility structures in the shrinking capacity case. 35 CHAPTER 5 Additional Cost Case 5.1 Introduction In this chapter, we study the manufacturing °exibility index in the additional cost case. We model the additional cost in linear programming, and develop a general formula to express the pro¯t of the additional cost case. We build up the modi¯ed SF(Structure Flexibility) matrix and Laplacian matrix in the additional cost case, and examine the SF indices and expander indices in di®erent manufacturing structures. We ¯rst test the chaining structure. Then we test the performance of SF indices and expander indices in the general structure (nonchaining structure). 5.2 Model in Additional Cost Case In this section, we ¯rst model the additional cost case in linear programming, then give a general formula to express the optimal solutions of the additional cost case. For simplicity, we use the same notations as shown in Chapter 4, and also consider the nm manufacturing °exibility structure in this section. The objective is to maximize the total pro¯t when the suppliers face the demands. Due to additional production processes or additional training for workers, an extra cost may be incurred if one type of product is produced in a plant that is not speci¯ed. We use cij to denote the additional cost for each unit of product j produced at plant i, hence cij = 0, if i = j, and cij > 0, if i 6= j. In addition, pj denotes the price of product j. We assume that cij < pj , 8 i 2 f1; 2; ¢ ¢ ¢ ; ng, 8 j 2 f1; 2; ¢ ¢ ¢ ;mg. The 36 maximal pro¯t of n¡m structures in additional cost case can be acquired by solving the following linear program: max Xm j=1 pj Xn i=1 xij ¡ Xn i=1 Xm j=1 cijxij (5.1) s:t: X (i;j)2F xij · qi 8 i = 1; 2; ¢ ¢ ¢ n; X (i;j)2F xij · dj 8 j = 1; 2; ¢ ¢ ¢ m: We get a general formula (5.2) for the optimal solution of the above problem in the following theorem. Theorem 5.1 The maximal pro¯t of °exibility nm structure with additional cost is: min ¹j ( X j dj¹j + X i qi max j fpj ¡ cij ¡ ¹jg ) ; ¹j ¸ 0; i = f1; ¢ ¢ ¢ ; ng; j = f1; ¢ ¢ ¢ ;mg (5.2) Proof. The problem (5.1) is same to the following: max Xn i=1 Xm j=1 (pj ¡ cij)xij (5.3) s:t: X (i;j)2F xij · qi 8 i = 1; 2; ¢ ¢ ¢ n; X (i;j)2F xij · dj 8 j = 1; 2; ¢ ¢ ¢ m: The dual of the linear program has the following form: min : d1¹1 + ¢ ¢ ¢ + dm¹m + q1v1 + ¢ ¢ ¢ + qnvn (5.4) s:t: ¹j + ºi ¸ pj ¡ cij 8(i; j) 2 F ¹j ; ºi ¸ 0 8 j = 1; 2; ¢ ¢ ¢ m; i = 1; 2; ¢ ¢ ¢ ; n: We observe that the optimal solutions should satisfy the following condition: in a optimal solution to (5:4), we can have ºi's as follows: ºi = max j fpj ¡ cij ¡ ¹jg (5.5) 37 provided that cj ¸ 0. That is, for a given speci¯cation of f¹1; ¢ ¢ ¢ ; ¹mg, we set ºi as small as possible. The case when cj < 0 is not meaningful, since it implies negative capacity. Since the optimal objective value to (5.4) equals the optimal objective value for (5.1), then we can get the solution of problem (5.1) has the form as (5.2). As for this study, we use the above theorem to analyze the structure index in the chaining structure. 5.3 SF Matrix of Additional Cost Case In this section, we set up SF matrix in the additional cost case, and introduce an algorithm for the construction of SF matrix in this special case. For simplicity, we focus on the nn additional cost case to show how to build the SF matrix. In this section, we assume that the capacity of each supply node is 1. Recall that Iravani et al. (2005) created the SF matrix in the following way: (1) for nondiagonal element: \the total number of nonoverlapping paths a system can use to respond to a particular change in demand," which can be obtained by solving the maximal °ow problem. (2) for diagonal element: the number of arcs connected to the corresponding supply node. We set the element of the SF matrix as the maximal pro¯t from each supply node to each demand node. Our method extends the work of Iravani et al. (2005) in the following way: (1) we set the nondiagonal element as the total pro¯t for one unit of product from supply node i to demand node j; (2)we set the diagonal element to be the total pro¯t for one unit of product from supply node i to demand node i. For example, as shown in Figure 5.1, the diagonal element M11 = 1 £ [p1 + (p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41)] = 2p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41, and the nondiagonal element M12 = 1 £ [p2 + (p2 ¡ c12 ¡ c41 ¡ c34 ¡ c23)] = 2p2 ¡ c12 ¡ c41 ¡ c34 ¡ c23. To get the elements of SF matrix, Iravani et al. (2005) used a maximal °ow 38 1 2 3 4 1 2 3 4 Plant Demand c11=0 c12 c23 c22=0 C33 =0 c34 c44=0 c41 s t q1 q2 q3 q4 P1/d1 P2/d2 P3/d3 P4/d4 Figure 5.1: 44 Manufacturing Flexibility Structure in Additional Cost Case. formulation to ¯nd the maximum number of units of source e®ort that can be shipped from a demand start node, i, to a demand sink node, j, in a particular structure. Unfortunately, their methodology cannot be used directly to the additional cost case, because of the addition of additional cost associated with each arc in the path. For example, if there exists a route R1 = 1¡2¡2¡3 from the source node 1 to demand node 3, as shown in Figure 5.1. The maximal pro¯t of this route can be solved as p3 ¡ c12 ¡ c23, not p3 ¡ max(c12; c23). With the increasing of °exibility in the manufacturing structure, it is not easy to solve the maximal pro¯t between supply node and demand node. In the chaining structure, there are only two paths from each supply node to demand node. But for nonchaining structure, it is not easy to get the maximal pro¯t between two nodes. This motivates for our algorithm in the next section. 39 5.3.1 Algorithm for SF Matrix Construction in Additional Cost Case The above maximal °ow problem can be transferred to the shortest path problem. We want to get the route r 2 R from source node s to demand node t, so that (pt ¡ P (i;j)2r cij) of the route be the maximal value in all routes R from s to t. That is, we want to get the route r, so that P (i;j)2r cij of the route be the minimal value in all routes R. Let cij represent the distance from node i to node j. The maximal pro¯t from node s to t is transformed to solve the distance from s to t. For example, the maximal °ow of route R1, as we mentioned in the last section, can be acquired by p3 ¡ d13, where d13 = c12 + c23 + c22 = c12 + c23. For our methodology, we use the maximal pro¯t, from a supply node, s, to a demand node, t, to present the element mst of SF matrix. The algorithm, which gets the element mst of SF matrix, is as follows: Step 1: To input incidence matrix T of the structure, s and t; initialize i = 1. Step 2: To calculate the shortest path ri and the distance di from s to t, which equals the summation of additional cost of arcs that this path passes. Step 3: Delete the arcs that ri passes, and check if the node s is connected to t. If they are disconnected, go to Step 4; if there are still routes from node s to t, then update the incidence matrix T, set i = i + 1, and go to Step 2. Step 4: Calculate P i(pt ¡di), which is mst, where pt denotes the price of product t. 5.4 Graph Expander in Additional Cost Case As mentioned before, SF matrix indices lack the mathematical support. At the same time, graph expander theory can help us get another structure index, which has more mathematical supports than SF matrix. This motivates for the graph expander index in this section. In this section, we extend the results of Chou et al. (2007) to the additional cost case. In addition, we propose a method to construct expander index in the additional 40 cost case. Similar with the shrinking capacity case, for the additional capacity case, we consider that the °exibility structure is a weighted graph, and de¯ne the additional cost incidence matrix, similar to the weighted incidence matrix, in the following way: each column of T, say Tl, characterizes an edge l 2 F, where edge l connects node i 2 A to j 2 B, by letting Tli = cij=pj ¡ 1, Tlj = (1 ¡ cij=pj) and Tlk = 0, 8 k 6= i; j. In this de¯nition, we use pj¡cij pj = (1 ¡ cij=pj), the ratio between the net pro¯t of shipping one unit of supply i to product j and the product price j, to represent the weight of the arc from supply node i to the demand node j. We de¯ne L = TT0, a positive semide¯nite matrix, motivated by Laplacian ma trix. In the subsequent numerical analysis, we consider ¸2(L), the second smallest eigenvalue of L, as the indicator. 5.5 Numerical Analysis In this section, we report the results of the computational study that we performed based on the additional cost SF matrix. Our experiment is consisted of two parts: one is about the chaining structure, and the other is about the general structure. To evaluate the e®ectiveness of various indices, we estimate the expected pro¯t of structure G, as the indicator of how °exible structure G is. 5.5.1 Chaining Structure In this section, we use, as an example, a 44 manufacturing structure shown in Figure 5.1 to test the structure indices. The arcs emanating from the source node s have capacities (q1; q2; q3; q4), and the arcs, which end in the sink node t have capacities (d1; d2; d3; d4). The °ows and additional costs in the arcs between plant node i and demand node j are xij and cij . The price of product j is pj . In the simulations of this section, each demand is uniform distribution on the 41 interval [0; 8); the capacity of each plant is 5. We use XpressIVE version 1.17.12 to implement the optimization problem and function random to generate the demand. First, we test the SF indices in the chaining structure. Following our construction method, the additional cost SF matrix isM = (Mij)4£4 = 2B¡(c12+c23+c34+c41)A = 2 6664 2p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41 2p2 ¡ c12 ¡ c41 ¡ c34 ¡ c23 2p3 ¡ c21 ¡ c32 ¡ c41 ¡ c34 2p4 ¡ c12 ¡ c23 ¡ c34 ¡ c41 2p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41 2p2 ¡ c23 ¡ c34 ¡ c41 ¡ c12 2p3 ¡ c23 ¡ c12 ¡ c41 ¡ c34 2p4 ¡ c23 ¡ c34 ¡ c12 ¡ c41 2p1 ¡ c23 ¡ c12 ¡ c34 ¡ c41 2p2 ¡ c23 ¡ c34 ¡ c41 ¡ c12 2p3 ¡ c23 ¡ c12 ¡ c41 ¡ c34 2p4 ¡ c34 ¡ c23 ¡ c12 ¡ c41 2p1 ¡ c41 ¡ c33 ¡ c23 ¡ c12 2p2 ¡ c34 ¡ c23 ¡ c41 ¡ c12 2p3 ¡ c34 ¡ c41 ¡ c12 ¡ c23 2p4 ¡ c41 ¡ c12 ¡ c23 ¡ c34 3 7775 where B = 2 66666664 p1 p2 p3 p4 p1 p2 p3 p4 p1 p2 p3 p4 p1 p2 p3 p4 3 77777775 ; and A is the matrix with all elements equal to 1. If two di®erent 44 manufacturing °exibility structures have the same c12 + c23 + c34 + c41, and the prices of all products of each structure are identical, then SF matrix of each structure is same. The SF matrix of structure shown in Figure 5.1 is M = (2p ¡ c12 ¡ c23 ¡ c34 ¡ c41)A, given p1 = p2 = p3 = p4 = p. We can get the insights from Theorem 5.1. The maximal pro¯t of additional cost case has the form X j dj¹j + X i qi max j fpj ¡ cij ¡ ¹jg: For simplicity, we set qi = q and pj = p for i; j 2 f1; 2; ¢ ¢ ¢ ; ng, and consider the following: X i qi max j fpj ¡ cij ¡ ¹jg = q X i max j fp ¡ cij ¡ ¹jg = q X i (p ¡ ¹j¤ ¡ cij¤) = qnp ¡ X i (¹j¤ ¡ cij¤) = qnp ¡ n¹j¤ + X i cij¤ ; where p ¡ ¹j¤ ¡ cij¤ = maxjfp ¡ cij ¡ ¹jg. Besides ¹j , P i cij¤ is a major factor to the value of maximal pro¯t ³P j dj¹j + P i qi maxj fpj ¡ cij ¡ ¹jg ´ , because the 42 two di®erent structures has the same qnp, n¹j¤ and P j dj¹j . That means, in the numerical study, If two di®erent 44 manufacturing °exibility structures have the same c12+c23+c34+c41, and the prices of all products of each structure are identical, then the maximal pro¯t of each structure should be same. Structures 1 2 3 4 5 6 7 8 c12 0.1 0.1 0.1 0.3 0.1 0.1 0.1 0.3 c23 0.1 0.2 0.1 0.5 0.1 0.2 0.1 0.5 c34 0.1 0.3 0.3 0.3 0.1 0.3 0.3 0.3 c41 0.1 0.4 0.2 0.5 0.1 0.4 0.2 0.5 p1 1 1 1 1 1.1 1.1 1.1 1.1 p2 1 1 1 1 1.1 1.1 1.1 1.1 p3 1 1 1 1 1.1 1.1 1.1 1.1 p4 1 1 1 1 1.1 1.1 1.1 1.1 Mean Value 1.6 1 1.3 0.4 1.8 1.2 1.5 0.6 Biggest Eigenvalue 6.4 4 4.2 1.6 7.2 4.8 6 2.4 Table 5.1: Additional Cost Case In this numerical study, we have eight di®erent additional cost structures, and the mean value and dominant real eigenvalue of each structure is shown in Table 5.1. We set up the model and ran 100 scenarios to analyze the maximal pro¯t of each scenario. Hence we can get a average shortage for each structure after running 100 scenarios. The results are shown in Figure 5.2. In this graph, the horizontal axis represents pro¯t, and the vertical axis represents mean value of SF matrix. We can see that: the mean value of SF matrix becomes greater, as the pro¯t becomes larger, given the prices are same. The detailed simulation results are attached in Appendix B. 43 0 1 2 3 4 5 6 7 8 1450 1500 1550 1600 1650 1700 1750 Prof it Mean Value Price = 1.1 Price = 1 Figure 5.2: SF Matrix Indices for Additional Cost Case From Figure 5.2, we can see that price can greatly a®ect the index. For simplicity, we set all the prices at the same value (price = 1) and use the structures shown in Table 5.2. We ran another 100 scenarios and show the results in Figure 5.3. The numbers beside nodes are structure numbers. In this graph, we can see the mean values increases as the pro¯t increases. If the mean values of di®erent structures are the same (0:4), pro¯ts are similar. The detailed simulation results are attached in Appendix C. The above two simulation results provide evidences that SF index is useful in predicting the performance rank of manufacturing °exibility in the additional cost case. Next, we test the performance of expander index in the chaining structure. The 44 Structures 1 2 3 4 5 6 7 8 c12 0.1 0.1 0.1 0.3 0.4 0.1 0.3 0.4 c23 0.1 0.2 0.1 0.5 0.1 0.7 0.1 0.5 c34 0.1 0.3 0.3 0.3 0.5 0.6 0.3 0.6 c41 0.1 0.4 0.2 0.5 0.1 0.2 0.7 0.7 Mean Value 1.6 1 1.3 0.4 0.9 0.4 0.6 0.2 Biggest Eigenvalue 6.4 4 4.2 1.6 3.6 1.6 2.4 0.8 ¸2(G) 0.5231 0.3606 0.4393 0.2192 0.2549 0.1463 0.1982 0.1283 Table 5.2: Additional Cost Case 6 1 3 2 7 4 8 5 0.5 0 0.5 1 1.5 2 1320 1340 1360 1380 1400 1420 1440 Average Prof it Mean Value Figure 5.3: SF Matrix Indices for Additional Cost Case (the number beside each node is the structure it is associated with) 45 modi¯ed additional cost incidence matrix is the following: T = 2 6666666666666666666664 ¡1 c12 p2 ¡ 1 0 0 0 0 0 0 0 0 ¡1 c23 p3 ¡ 1 0 0 0 0 0 0 0 0 ¡1 c34 p4 ¡ 1 0 0 0 0 0 0 0 0 ¡1 c41 p1 ¡ 1 1 0 0 0 0 0 0 1 ¡ c41 p1 0 1 ¡ c12 p2 1 0 0 0 0 0 0 0 0 1 ¡ c23 p3 1 0 0 0 0 0 0 0 0 1 ¡ c34 p4 1 0 3 7777777777777777777775 : We compute the second smallest eigenvalue of L = TT0. The results are shown in Table 5.2. We plot the results shown in Table 5.2 in Figure 5.4. In this graph, the horizontal axis represents the pro¯t and the vertical axis represents the second smallest eigenvalue of L. The numbers beside nodes are structure numbers. We can see that the main trend is: as the pro¯t becomes higher, the second smallest eigenvalue of L becomes higher. Simulation results provide evidence that expander index is useful in predicting the performance rank of structure °exibility in the additional cost case. 1 3 2 5 6 7 4 8 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 1320 1340 1360 1380 1400 1420 1440 Profit Expander Index Figure 5.4: Graph Expander Index (the number beside each node is the structure it is associated with) However, there are small oscillations of expander index line, such as Structure 4, 46 6 and Structure 7. As mentioned before, this phenomenon probably is caused by the nature of expander index, which is a bound for the connectivity property of graph, not the exact value of graph connectivity. We can see similar result for the nonchaining structure. 5.5.2 General Structure In this section, we will analyze the general structure and use our indices to the additional cost case. We use a set of numerical examples from Iravani et al. (2005), shown in Figure 4.5, to test the performance of the expander index and the SF index. We analyze the set of structures facing random uniform distribution demand in the interval [0; 8), ¯xed capacity q = (5; 5; 5; 5; 5; 5; 5; 5), the additional cost cij = 0:1, 8 i; j 2 f1; 2; ¢ ¢ ¢ ; 8g and pj = 1, 8 j = f1; 2 ¢ ¢ ¢ ; 8g. We use XpressIVE version 1.17.12 to implement the optimization problem and random function to generate the demand. To evaluate the e®ectiveness of various indices, we estimate the expected pro¯t of the structure G, by sampling 100 scenarios, and use this estimate as the indicator of how °exible structure G is. The performance of various indices are as shown in Table 5.3. Structures 1 2 3 4 5 6 7 8 9 Mean Value 1.2 1.334 1.755 2.283 2.045 2.205 3.152 2.981 3.786 Biggest Eigenvalue 64.32 53.20 62.04 61.69 56.02 70.04 56.95 68.45 62.606 ¸2(G) 0.1362 0.1631 0.1892 0.5258 0.2607 0.2236 1.2336 0.7845 1.5025 Pro¯t 3063.05 2961.81 3034.65 3098.33 3098.10 3100.09 3107.24 3107.57 3109.544 Table 5.3: SF Structures We plot the results shown in Table 5.3 in Figure 5.5 and 5.6. The numbers beside nodes are structure numbers. From these two ¯gures, we can see that SF index 47 2 3 1 5 4 6 8 7 9 8 13 18 23 28 33 2960 2980 3000 3020 3040 3060 3080 3100 3120 Profit Biggest Eigenvalue 2 3 1 6 5 4 8 7 9 1 1.5 2 2.5 3 3.5 4 2960 2980 3000 3020 3040 3060 3080 3100 Profit Mean Value of SF Matrix Figure 5.5: SF Indices, Up: Biggest Eigenvalue Index; Down: Mean Value Index (the number beside each node is the structure it is associated with). 2 3 1 9 7 8 4 6 5 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 2960 2980 3000 3020 3040 3060 3080 3100 Profit Expander Index Figure 5.6: Expander Indices for SF Structures (the number beside each node is the structure it is associated with) 48 and expander index rank the structures almost in line with the order obtained from the sampling estimation: as the pro¯t increases, the SF index and expander index increase. Simulation results provide evidence that SF index and expander index are useful in predicting the performance rank of manufacturing °exibility in the additional cost case. However, the biggest eigenvalue has a signi¯cant decrease at Structure 1 (Figure 4.5) as shown in Figure 5.5. Iravani et al. (2005) mentioned that the biggest eigenval ues can be considered as an indication of the magnitude of elements of a matrix. As any element of the SF matrix increases (i.e., more °exibility), the biggest eigenvalue of the matrix increases. Because Structure 1 is a chaining structure which has less arcs compared to other structures with similar performance. So dominant eigenvalue has a big decrease at Structure 1. Another potential reason for this phenomenon is that in structures 2 and 3, there are very few arcs for specialized production (Struc ture 2 has 3 arcs, and Structure 3 has 6 arcs), and this makes expected pro¯t of these two structures very low when e±ciency loss exits in cross production. While, for other seven structures, each product has dedicated plant. Therefore, it is not fair to compare structures 2 and 3 to other structures directly. On the other hand, the mean value index ranks the structures in a similar order. This implies SF matrix does not perform good to compare chaining and nonchaining structure. From Figure 5.6, we can see that expander index has small oscillations, such as Structure 7, 8 and 9, in the expander index line. This probably is caused by the nature of expander index, which is a bound for the connectivity property of graph, not the exact value of graph connectivity. However, we notice that the performance di®erence among some di®erent struc tures is quite small, it is possible that the slight di®erence in ordering actually arises from the small number of sampling. The results, however, suggest that the concept of SF matrix and Laplacian matrix can be used as the index to rank process °exibility 49 structures in the additional cost case. 50 CHAPTER 6 Conclusion Our main contribution of this study is that we model e±ciency loss occurred in manufacturing °exibility. We focus on the shrinking capacity and additional cost cases, the two main sources for e±ciency loss. We develop new indices, for the shrinking capacity and additional cost cases, which are simple and traceable numbers, and can rank the structure performance. First, we include the shrinking capacity and the additional cost into the current classical maximal °ow models, and build up the shrinking capacity case and additional cost case in linear programming. We characterize the optimal solutions, and present e±cient methods to solve the above two problems. Second, we provide an approach to extend SF matrix to the shrinking capacity and additional cost case. Based on this method, we can develop a simple performance index for the both cases. Indeed, this approach can also be applied in general nm system. Extensive numerical studies show that our method can get useful index for the structure performance. Third, we analyze the shrinking capacity and additional cost cases using graph expander theory, which is a direct extension of Chou et al. (2007). We evaluate the manufacturing °exibility structure in the shrinking capacity and additional cost cases as the weighted graph. Extensive numerical studies show that our index is simple and useful for the structure performance. The structure indices capture important information about a structure, and how well it can respond to demand variability. Our experiments suggest that SF indices 51 and expander indices are purely deterministic metrics, and quite robust, because they work no matter the demand realization. They are powerful in predicting system performance ranking at demand variation. In reality, the concept of SF index and graph expander index can be used to help managers to design good manufacturing °exibility structure, and does not require intensive simulation. Finally, we discuss some future research directions. (1) Combination of shrinking capacity and additional cost. This work raises an important future direction, the combination of shrinking capacity and ad ditional cost. So far, we consider individually the cases of shrinking capacity and additional cost. In reality, they often occur in the manufacturing °exibility at the same time. Another important issue is to develop useful index for the manufacturing °exibility structure in this combination case. (2) E±ciency loss in correlated demand situation. In this thesis, we assume that the demand of di®erent plant is independent. In reality, the demand of di®er ent plant is often positive correlated or negative correlated. If it happens, the chain structure maybe not bene¯cial as in the independent demand case. In addition, the manufacturers may adjust the capacity allocation between each plant in order to ¯t the correlated demand. Hence, the challenge is to study the in°uence of correlated demand to the manufacturing °exibility in the e±ciency loss manufacturing envi ronment. Another important issue is to build new index for the correlated demand case. 52 BIBLIOGRAPHY [1] Aksin, O. Z., F. Karaesmen. 2007. Characterizing the performance of process °exibility structures. Operations Research Letters 35(4) 477484. [2] Alon, N. 1986. Eigenvalues and expanders. Combinatorica 6(2) 8396. [3] Alon, N., V.D. Milman. 1985. ¸1, isopermitric inequalities for graphs, and su perconcentrators. Journal of Combinatorial Theory Series A 38(1) 7388. [4] Bassalygo, L. A., M. S. Pinsker. 1973. Complexity of an optimum nonblocking switching network without reconnections. Problem Information Transmission 9 8487. [5] Chou, M., C. Teo, H. Zheng. 2007. Process °exibility revisited: graph expander and foodfromtheheart.Working paper, National University of Singapore, Sin gapore. [6] De Meyer, A., J. Nakane, J. G. Miller K. Ferdows. 1989. Flexibility: the next competitive battle. Strategic Management Journal 10(2) 135144. [7] De Toni, A., S. Tonchia. 1998. Manufacturing °exibility: a literature review. International Journal of Production Research 36(6) 15871617. [8] Fiedler, M. 1973. Algebraic connectivity of graphs. Czechoslovak Mathematics Jornal 23 298305. [9] Gerwin, D. 1993. Manufacturing °exibility: a strategic perspective. Manage ment Science 39(4) 395410. 53 [10] Graves, S. C., B. T. Tomlin. 2003. Process °exibility in supply chains. Manage ment Science 49(7) 907919. [11] Gurumurthi, S., S. Benjaafar. 2004. Modeling and analysis of °exible queueing systems. Naval Research Logistics 51(5) 755782. [12] Hopp, W. J., E. Tekin, M. P. Van Oyen. 2004. Bene¯ts of skill chaining in production lines with crosstrained workers. Management Science 50(1) 8398. [13] Iravani, S. M., M. P. Van Oyen, K. T. Sims. 2005. Structural °exibility: a new perspective on the design of manufacturing and service operations. Management Science 51(2) 151166. [14] Iravani, S.M., R. B. Kolfal, M. P. Van Oyen. 2007. Call center labor cross training: It's a small world after all. Management Science 53(7) 11021112. [15] Jordan, W.C., R. P. Inman, D. E. Blumenfeld. 2004. Chained crosstraining of workers for robust performance. IIE Transactions 36(10) 953967. [16] Jordan, W. C., S. C. Graves. 1995. Principles on the bene¯ts of manufacturing process fexibility. Management Science 41(4) 577594. [17] Lien, R., S. M. Iravani, K. Smilowitz, M. Tzur. 2005. E±cient and robust design for transshipment networks. Working paper, Northwestern University, Evanston, IL. [18] Merris R. Laplacian matrics of graphs: a survey. 1994. Linear Algebra and its Applications 197,198 143176. [19] Reingold, O., S. Vadhan, A. Wigderson. 2002. Entropy waves, the zigzag graph product, and new constantdegree expanders and extractors. Ann. of Math 155 157187. 54 [20] Sarnak, P. 2004. What is an expander? Notices of the AMS 51(7) 62763. [21] Sethi, A. K., S. P. Sethi. 1990. Flexibility manufacturing: a survey. Internat. J. Flexible Manufacturing Systems 2 289328. [22] Sheikhzadeh, M., S. Benjaafar, D. Gupta. 1998. Machine sharing in manufac turing systems: °exibility versus chaining. International Journal of Flexible Manufacturing Systems 10(4) 351378. [23] Shi, D., R. L. Daniels. 2003. A survey of manufacturing °exibility: implications for ebusiness. IBM Systems Journal 42(3) 414427. [24] Tanner, M. 1984. Explicit construction of concentrators from generalized N gons. SIAM Journal on Algebraic Discrete Methods 5(3) 287293. [25] Wallis W.D. 2000. A beginners guide to graph theory, BirkhÄauser, Boston, MA. [26] Xiao, D.Y. 2003. The evolution of expander graphs. BA Thesis, Harvard Uni versity, http://www.cs.princeton.edu/dxiao. 55 APPENDIX A Simulation Results in Shrinking Capacity Case Appendix A data goes here Demand Strucuture 1 2 3 4 1 2 3 4 5 6 7 8 1 7.632 1.098 7.35 6.243 4.273 3.883 5.054 3.76 4.664 3.764 4.664 4.38 2 3.436 2.092 6.792 4.407 0 0 0.763 0 0.321 0 0.359 0.005 3 2.644 2.364 3.881 2.46 0 0 0 0 0 0 0 0 4 2.555 4.044 6.142 3.683 0 0 0.599 0 0.241 0 0.325 0.004 5 1.755 7.476 1.441 7.318 1.392 0.784 2.753 2.753 1.342 0.398 2.771 1.577 6 6.976 7.398 4.044 0.125 2.136 1.386 2.874 1.941 1.978 1.588 3.355 2.215 7 2.275 3.082 0.422 6.884 0 0 0.384 0.384 0 0 0.865 0 8 1.894 7.249 2.555 3.291 0 0 1.097 0.804 0.249 0 0.826 0.14 9 1.457 3.069 1.405 3.304 0 0 0 0 0 0 0 0 10 0.353 5.791 3.422 7.616 1.444 0.867 2.088 2.016 1.402 0.673 2.207 1.555 11 7.476 0.125 7.345 7.925 5.355 4.995 6.283 5.081 5.796 4.881 5.796 5.441 12 3.881 0.025 6.734 7.35 1.967 1.464 2.584 1.82 2.189 1.383 2.296 2.052 13 1.457 5.254 6.243 1.398 0.12 0 0.903 0.371 0.545 0 0.66 0.245 14 7.249 7.692 6.792 7.318 9.051 9.051 9.051 9.051 9.051 9.051 9.051 9.051 15 6.407 7.634 4.038 1.89 2.439 1.823 3.021 2.342 2.302 1.984 3.366 2.502 16 3.916 4.622 1.356 2.114 0 0 0 0 0 0 0 0 17 2.46 6.142 1.784 1.755 0 0 0.001 0 0 0 0 0 18 6.243 7.319 7.692 3.645 5.577 5.17 5.848 5.306 5.434 5.379 5.978 5.613 19 0.039 7.476 1.441 7.634 0.853 0.14 2.554 2.554 0.971 0.029 2.4 1.081 20 3.683 1.89 4.501 7.35 1.158 0.417 1.884 1.464 1.167 0.373 1.951 1.279 21 0.081 0.742 0.353 1.529 0 0 0 0 0 0 0 0 22 2.307 1.391 1.405 2.842 0 0 0 0 0 0 0 0 23 3.082 2.275 5.973 4.792 0 0 0 0 0 0 0 0 24 7.249 0.125 3.304 6.884 2.158 1.168 3.185 2.633 2.054 1.443 3.39 2.245 25 7.925 4.27 3.069 1.706 0.704 0 1.743 0.107 0.117 0 2.161 0.859 26 7.856 1.098 7.634 7.632 6.17 5.78 6.951 5.459 6.561 5.6 6.561 6.276 27 3.683 2.092 7.476 6.449 2.141 1.785 2.934 1.612 2.551 1.496 2.551 2.255 28 3.436 2.114 1.875 7.692 0.212 0 1.453 1.192 0 0 1.769 0.404 29 1.89 1.876 2.17 7.398 0 0 1.184 0.898 0 0 1.465 0.034 30 6.378 4.044 2.46 6.792 1.661 1.068 2.322 2.207 1.401 1.217 2.574 1.755 31 5.791 4.706 3.082 1.405 0 0 0 0 0 0 0 0 32 3.304 2.307 0.081 2.842 0 0 0 0 0 0 0 0 33 7.853 0.422 5.973 7.99 5.185 4.602 5.723 5.174 5.324 4.561 5.668 5.28 34 4.253 1.894 0.742 7.616 0.116 0 1.116 1.116 0 0 1.596 0.252 35 4.792 2.275 6.458 1.392 0 0 0.524 0 0 0 0.217 0 36 7.616 5.532 0.522 4.043 1.55 0.203 2.458 1.537 0.928 0.66 2.767 1.694 37 1.529 7.99 4.706 2.65 0.631 0.49 1.73 1.49 0.99 0 1.405 0.793 38 2.769 1.58 3.722 0.353 0 0 0 0 0 0 0 0 56 Demand Strucuture 39 6.458 1.894 7.853 7.985 5.743 5.432 6.364 5.122 6.054 5.289 6.054 5.827 40 0.303 7.465 4.038 3.082 0 0 0.965 0.965 0.465 0 0.465 0.101 41 1.894 2.275 4.038 6.976 0.425 0 1.358 0.919 0.433 0 1.456 0.583 42 2.082 6.884 0.742 0.522 0 0 0.558 0.384 0 0 0.309 0 43 1.777 2.65 5.532 7.925 2.201 1.634 2.786 2.388 2.366 1.418 2.736 2.31 44 2.17 0.353 2.307 0.081 0 0 0 0 0 0 0 0 45 1.405 5.791 0.125 6.921 0 0 0.433 0.421 0 0 0.902 0 46 1.529 3.943 1.706 6.048 0 0 0 0 0 0 0.177 0 47 0.353 6.877 0.081 6.569 0 0 0.576 0.576 0 0 0.584 0 48 2.533 2.739 5.212 7.616 1.848 1.296 2.409 2.049 1.957 1.143 2.394 1.95 49 1.405 3.082 4.043 7.99 1.582 0.759 2.433 2.074 1.598 0.601 2.521 1.729 50 2.307 2.769 6.458 0.742 0 0 0.431 0 0 0 0 0 51 1.777 3.082 2.739 4.253 0 0 0 0 0 0 0 0 52 1.706 3.722 4.043 0.019 0 0 0 0 0 0 0 0 53 6.048 7.465 0.081 7.244 3.405 2.553 4.281 4.281 3.069 2.909 4.754 3.474 54 1.529 3.343 6.458 3.304 0 0 0.603 0 0.076 0 0.184 0 55 4.584 7.99 5.791 1.58 2.718 2.205 3.349 2.938 2.787 2.084 3.336 2.82 56 3.683 4.501 1.398 2.555 0 0 0 0 0 0 0 0 57 1.89 6.378 3.881 6.243 0.639 0.385 1.352 1.352 0.699 0.256 1.148 0.693 58 6.792 5.681 7.692 1.755 3.543 2.971 4.192 3.229 3.304 3.177 4.504 3.631 59 7.345 2.092 1.875 3.291 0.345 0 1.472 0.099 0 0 1.818 0.531 60 5.254 7.318 6.976 1.457 3.535 3.003 4.051 3.626 3.537 2.978 4.106 3.621 61 2.204 4.177 6.963 5.623 1.476 1.254 2.088 1.423 1.81 0.887 1.81 1.572 62 6.673 3.059 7.475 4.988 3.171 2.973 3.562 2.78 3.364 2.886 3.369 3.224 63 1.452 3.503 5.177 7.887 2.157 1.636 2.709 2.402 2.288 1.419 2.685 2.261 64 5.987 2.556 6.428 6.917 3.11 2.877 3.599 2.819 3.355 2.807 3.355 3.177 65 2.715 5.145 4.032 3.748 0 0 0 0 0 0 0 0 66 3.069 3.291 4.792 7.345 1.572 1.076 2.076 1.802 1.618 0.976 2.1 1.66 67 7.398 1.405 5.532 2.082 0.623 0 1.474 0 0.3 0 1.766 0.758 68 1.392 2.65 6.407 3.422 0 0 0.335 0 0 0 0 0 69 0.522 2.275 7.249 1.876 0 0 0.981 0 0.359 0 0.359 0 70 1.391 0.742 1.58 4.706 0 0 0 0 0 0 0 0 71 2.918 2.08 0.848 4.342 0 0 0 0 0 0 0 0 72 7.759 3.082 3.221 1.896 0.522 0 1.616 0 0 0 2.02 0.691 73 6.112 6.048 0.251 1.332 0.354 0 0.932 0.332 0.282 0 1.215 0.456 74 2.809 3.702 0.053 1.006 0 0 0 0 0 0 0 0 75 7.867 6.33 2.533 5.809 3.985 3.463 4.266 4.266 3.783 3.69 4.504 4.028 76 3.291 5.791 4.038 0.522 0 0 0 0 0 0 0 0 77 2.842 0.081 7.99 1.706 0.49 0 1.49 0 0.99 0 0.99 0.626 78 1.777 3.304 0.019 2.769 0 0 0 0 0 0 0 0 79 2.739 1.529 7.787 4.253 0.393 0 1.523 0 0.965 0 1.013 0.562 80 1.057 7.616 6.976 1.392 2.091 2.091 3.091 3.091 2.591 1.578 2.72 2.227 81 1.006 1.296 1.896 4.465 0 0 0 0 0 0 0 0 82 2.809 7.867 5.105 0.848 0.839 0.473 1.942 1.473 1.091 0 1.758 1.009 83 5.335 4.584 6.429 1.57 0.876 0.456 1.242 0.704 0.984 0.375 1.204 0.944 84 6.33 6.53 0.053 3.044 1.088 0.195 1.828 1.207 0.864 0.302 2.256 1.199 85 5.454 2.007 4.826 6.112 0.731 0.24 1.244 0.885 0.736 0.292 1.286 0.815 86 6.877 2.739 5.105 7.985 4.349 3.986 4.69 4.419 4.378 3.986 4.699 4.406 87 0.019 4.584 0.848 3.221 0 0 0 0 0 0 0 0 88 6.133 7.787 2.918 0.303 2.104 1.354 2.677 2.077 2.03 1.432 2.901 2.205 89 5.809 3.943 6.048 7.867 4.196 4.09 4.407 3.985 4.302 4.042 4.302 4.225 90 3.702 7.465 4.043 2.533 1.079 0.56 1.827 1.497 1.208 0.337 1.728 1.198 57 Demand Strucuture 91 5.105 3.082 7.465 0.019 0.909 0.15 1.764 0.412 1.232 0 1.552 1.055 92 2.08 5.809 4.253 0.774 0 0 0 0 0 0 0 0 93 0.053 6.429 2.739 6.133 0 0 0.449 0.443 0 0 0.627 0 94 2.769 1.762 3.343 6.048 0 0 0.199 0 0 0 0.373 0 95 3.702 2.533 7.867 7.99 4.299 3.988 5 3.858 4.663 3.721 4.663 4.401 96 3.142 2.918 4.342 4.584 0 0 0 0 0 0 0 0 97 5.809 7.244 0.303 1.896 1.399 0.649 2.081 1.539 1.357 0.68 2.237 1.509 98 7.867 7.465 6.133 5.212 6.676 6.676 6.676 6.676 6.676 6.676 6.676 6.676 99 3.221 0.251 0.486 2.48 0 0 0 0 0 0 0 0 100 1.332 5.335 1.57 3.702 0 0 0 0 0 0 0 0 Total 130.766 103.501 182.445 141.585 135.149 100.421 180.61 137.141 58 APPENDIX B Numerical Results in Additional Cost Case with Di®erent Price Appendix B data goes here Demand Strucuture 1 4.571 3.614 7.308 6.648 19.776 19.594 19.776 18.964 21.776 21.594 21.776 20.964 2 3.111 0.619 5.024 1.471 10.222 10.22 10.222 10.212 11.244 11.242 11.244 11.235 3 1.713 1.695 1.569 3.463 8.439 8.439 8.439 8.439 9.283 9.283 9.283 9.283 4 2.193 0.628 7.936 2.299 12.763 12.469 12.763 11.588 14.069 13.775 14.069 12.894 5 2.988 0.795 1.357 1.823 6.964 6.964 6.964 6.964 7.66 7.66 7.66 7.66 6 0.209 0.913 7.106 7.7 15.105 14.085 14.565 12.571 16.698 15.677 16.158 14.092 7 7.115 1.961 6.107 4.114 18.729 17.615 18.272 17.071 20.659 19.545 20.202 18.878 8 1.42 1.921 4.137 6.71 13.933 13.506 13.591 13.252 15.351 14.925 15.009 14.67 9 2.91 6.163 0.509 7.636 16.839 16.311 16.311 16.079 18.56 18.033 18.033 17.8 10 0.427 1.345 7.888 5.234 14.558 14.199 14.511 13.262 16.048 15.688 16.001 14.752 11 5.057 0.578 7.888 6.633 19.404 18.655 19.098 17.329 21.404 20.655 21.098 19.329 12 0.687 1.798 0.427 7.834 10.462 9.895 9.895 9.895 11.536 10.969 10.969 10.969 13 3.168 0.209 7.878 5.251 16.167 15.804 16.117 14.866 17.818 17.455 17.767 16.516 14 2.529 2.696 4.469 1.921 11.615 11.615 11.615 11.615 12.777 12.777 12.777 12.777 15 6.672 6.785 0.206 3.565 16.502 15.06 15.752 14.536 18.225 16.783 17.475 16.08 16 3.516 1.921 2.696 1.345 9.477 9.477 9.477 9.477 10.425 10.425 10.425 10.425 17 1.961 7.878 5.379 2.414 17.246 17.143 17.224 16.421 19.009 18.906 18.987 18.163 18 0.209 6.71 7.888 3.168 17.226 16.937 17.226 15.151 19.024 18.735 19.024 16.949 19 7.106 5.057 6.163 0.206 17.961 16.847 17.628 16.27 19.814 18.7 19.481 18.007 20 6.672 6.037 7.653 4.944 19.994 19.977 19.989 19.972 21.994 21.977 21.989 21.972 21 7.878 4.723 3.168 0.05 15.531 14.668 15.243 14.38 17.113 16.25 16.825 15.962 22 5.663 7.831 2.933 3.565 19.154 17.694 18.393 16.984 21.153 19.693 20.392 18.778 23 6.037 7.888 7.917 7.45 20 20 20 20 22 22 22 22 24 0.427 3.422 5.251 6.633 15.35 14.835 15.024 14.24 16.924 16.409 16.597 15.782 25 0.509 1.789 4.684 2.333 9.316 9.316 9.316 9.316 10.248 10.248 10.248 10.248 26 0.509 6.633 6.163 2.529 15.439 15.322 15.439 14.414 17.022 16.906 17.022 15.998 27 0.427 4.626 7.106 3.48 15.254 15.043 15.254 14.065 16.818 16.607 16.818 15.629 28 2.696 6.037 6.672 1.378 16.305 16.016 16.264 15.054 17.983 17.694 17.943 16.691 29 7.888 1.42 3.898 0.209 13.127 12.261 12.838 11.972 14.469 13.602 14.18 13.313 30 1.798 3.168 4.723 0.05 9.739 9.739 9.739 9.739 10.713 10.713 10.713 10.713 31 7.653 2.696 0.05 1.789 11.923 11.127 11.658 10.862 13.142 12.346 12.877 12.081 32 3.422 6.672 1.297 4.684 15.899 15.871 15.889 15.527 17.506 17.478 17.497 17.134 33 4.626 7.917 0.913 7.959 19.328 18.172 18.398 17.872 21.328 20.172 20.398 19.759 34 5.757 6.71 4.363 1.798 18.21 17.47 17.963 16.881 20.073 19.333 19.826 18.744 35 2.333 3.565 1.378 5.001 12.277 12.277 12.277 12.277 13.505 13.505 13.505 13.505 36 7.636 1.345 0.495 3.898 12.957 11.859 12.387 11.596 14.295 13.197 13.724 12.933 37 4.626 7.834 1.508 3.565 16.901 15.958 16.45 15.248 18.654 17.711 18.203 16.898 38 1.798 0.05 7.959 2.933 12.444 12.148 12.444 11.261 13.718 13.422 13.718 12.535 39 1.378 1.789 4.363 7.878 14.895 14.096 14.32 13.424 16.436 15.637 15.861 14.965 59 Demand Strucuture 40 7.917 1.584 2.333 6.037 17.056 15.261 15.973 14.97 18.843 17.048 17.76 16.628 41 4.363 3.103 2.933 2.333 12.732 12.732 12.732 12.732 14.006 14.006 14.006 14.006 42 3.75 3.422 7.831 6.785 19.592 19.31 19.592 18.211 21.592 21.31 21.592 20.211 43 5.251 4.684 1.508 6.571 17.807 17.367 17.417 17.342 19.608 19.168 19.218 19.143 44 0.05 2.292 2.714 7.339 12.156 11.683 11.688 11.667 13.396 12.923 12.928 12.907 45 6.672 4.6 4.04 1.789 16.933 16.432 16.766 16.264 18.643 18.142 18.476 17.975 46 5.757 2.933 2.292 7.351 17.907 17.018 17.21 16.943 19.74 18.852 19.043 18.736 47 1.508 2.714 3.75 4.802 12.774 12.774 12.774 12.774 14.051 14.051 14.051 14.051 48 5.001 4.363 6.571 3.422 19.013 18.575 18.919 18.104 20.948 20.511 20.855 19.946 49 1.584 7.298 6.6 3.768 18.651 18.347 18.603 17.184 20.576 20.272 20.528 19.061 50 1.58 7.633 7.959 3.898 19.249 18.729 19.139 17.479 21.249 20.729 21.139 19.369 51 2.933 3.707 2.678 7.922 16.889 16.244 16.304 16.064 18.613 17.968 18.028 17.788 52 5.663 5.757 6.571 4.363 19.936 19.745 19.873 19.681 21.936 21.745 21.873 21.681 53 2.292 2.61 4.091 3.75 12.743 12.743 12.743 12.743 14.017 14.017 14.017 14.017 54 7.351 2.674 1.782 6.063 17.274 15.866 16.356 15.631 19.061 17.653 18.143 17.399 55 7.917 5.853 3.358 4.222 19.594 18.54 19.023 18.298 21.594 20.54 21.023 20.298 56 5.518 1.219 0.269 4.267 11.222 11.067 11.17 11.015 12.35 12.194 12.298 12.142 57 0.845 0.908 1.886 4.198 7.838 7.838 7.838 7.838 8.621 8.621 8.621 8.621 58 4.923 4.794 3.708 2.582 16.007 16.007 16.007 16.007 17.608 17.608 17.608 17.608 59 2.41 6.603 1.569 7.593 17.755 17.236 17.236 16.916 19.572 19.054 19.054 18.733 60 4.377 1.622 1.025 3.299 10.323 10.323 10.323 10.323 11.355 11.355 11.355 11.355 61 2.714 4.04 5.853 1.584 14.106 14.021 14.106 13.765 15.526 15.44 15.526 15.184 62 6.284 4.802 7.351 5.001 19.98 19.96 19.98 19.901 21.98 21.96 21.98 21.901 63 3.75 3.707 7.922 7.339 19.621 19.367 19.621 18.354 21.621 21.367 21.621 20.354 64 7.795 3.236 1.93 4.624 17.063 15.741 16.3 15.462 18.822 17.499 18.058 17.22 65 2.678 3.768 4.128 3.358 13.932 13.932 13.932 13.932 15.325 15.325 15.325 15.325 66 6.284 3.707 7.298 7.351 19.871 19.741 19.871 19.354 21.871 21.741 21.871 21.354 67 1.557 7.633 3.75 6.6 19.047 18.693 18.728 18.026 21.002 20.647 20.682 19.945 68 2.714 4.091 2.846 7.894 17.181 16.529 16.603 16.307 18.936 18.283 18.357 18.061 69 2.292 5.853 2.61 1.711 12.381 12.381 12.381 12.211 13.628 13.628 13.628 13.457 70 1.301 6.291 3.236 1.58 12.279 12.279 12.279 12.02 13.519 13.519 13.519 13.261 71 5.001 5.663 1.789 2.293 14.614 14.415 14.547 14.216 16.088 15.889 16.022 15.69 72 7.45 7.653 0.495 2.714 17.183 15.14 16.14 14.385 19.004 16.961 17.961 15.951 73 4.802 7.831 3.565 7.922 19.837 19.55 19.55 19.51 21.837 21.55 21.55 21.51 74 7.298 0.228 3.707 2.674 13.677 12.988 13.448 12.758 15.068 14.379 14.838 14.149 75 6.284 7.959 1.58 2.292 17.241 15.661 16.51 14.799 19.053 17.473 18.321 16.457 76 4.091 7.298 4.222 1.557 16.799 16.383 16.66 15.784 18.516 18.1 18.377 17.501 77 5.334 0.228 3.236 6.045 14.671 14.295 14.362 14.262 16.156 15.78 15.847 15.746 78 1.93 6.291 2.61 3.768 14.47 14.47 14.47 14.211 15.929 15.929 15.929 15.671 79 2.674 2.212 7.633 2.678 14.934 14.671 14.934 13.881 16.454 16.19 16.454 15.4 80 5.844 6.063 5.075 4.6 19.96 19.84 19.92 19.8 21.96 21.84 21.92 21.8 81 2.61 1.58 0.228 2.674 7.092 7.092 7.092 7.092 7.801 7.801 7.801 7.801 82 7.894 7.831 3.358 2.714 19.34 17.833 18.619 17.337 21.34 19.833 20.619 19.233 83 3.768 2.678 5.334 7.45 18.661 17.892 18.17 17.01 20.584 19.815 20.093 18.887 84 2.333 1.93 4.04 7.351 15.28 14.671 14.81 14.253 16.846 16.236 16.375 15.819 85 4.128 6.045 6.571 5.001 19.913 19.913 19.913 19.738 21.913 21.913 21.913 21.738 86 1.584 3.768 4.624 4.04 14.016 14.016 14.016 14.016 15.417 15.417 15.417 15.417 87 4.6 3.236 7.298 2.292 17.129 16.859 17.115 16.09 18.871 18.602 18.858 17.819 88 7.894 2.597 1.58 4.128 15.707 14.434 15.013 14.145 17.326 16.054 16.633 15.765 89 6.045 2.714 4.991 6.063 19.288 18.343 18.762 17.922 21.269 20.325 20.743 19.799 90 1.682 1.711 5.844 3.707 12.86 12.776 12.86 12.522 14.155 14.07 14.155 13.817 91 2.293 4.6 4.222 3.707 14.823 14.823 14.823 14.823 16.305 16.305 16.305 16.305 60 Demand Strucuture 92 2.61 0.228 5.853 3.768 12.374 12.289 12.374 12.033 13.62 13.535 13.62 13.279 93 7.922 4.363 2.714 1.782 16.489 15.612 16.197 15.32 18.167 17.291 17.875 16.998 94 6.284 7.45 7.917 2.846 19.698 19.052 19.482 18.662 21.698 21.052 21.482 20.662 95 4.04 6.291 0.21 7.795 17.861 17.136 17.202 16.878 19.694 18.97 19.036 18.679 96 2.212 1.072 2.639 6.184 11.989 11.752 11.752 11.752 13.2 12.963 12.963 12.963 97 5.563 4.991 1.682 3.009 15.189 15.02 15.132 14.963 16.713 16.544 16.657 16.488 98 5.242 5.075 0.273 7.275 17.567 16.953 17.017 16.914 19.353 18.74 18.803 18.693 99 3.236 5.854 4.044 1.425 14.472 14.472 14.472 14.302 15.928 15.928 15.928 15.757 100 4.182 3.568 4.984 1.493 14.227 14.227 14.227 14.227 15.65 15.65 15.65 15.65 Total 1553.704 1507.743 1529.807 1470.2 1711.998 1666.038 1688.102 1626.264 61 APPENDIX C Numerical Results in Additional Cost Case with Same Price Appendix C data goes here Demand Strucuture 1 4.339 6.219 7.523 1.137 18.284 17.107 17.975 16.05 17.161 16.462 15.939 15.872 2 0.874 5.793 0.839 2.246 9.673 9.673 9.673 9.514 9.435 9.673 9.514 9.435 3 3.87 5.331 7.443 0.867 16.824 16.087 16.66 15.128 15.992 15.194 15.448 15.015 4 1.151 4.327 1.084 5.127 11.677 11.651 11.651 11.651 11.626 11.613 11.651 11.613 5 2.104 1.046 0.651 7.633 11.17 10.644 10.644 10.644 10.117 9.854 10.644 9.854 6 0.575 6.533 7.443 7.523 19.223 18.844 19.133 17.136 17.716 17.443 18.248 16.739 7 3.128 1.59 2.432 0.874 8.024 8.024 8.024 8.024 8.024 8.024 8.024 8.024 8 1.084 4.06 7.65 3.75 16.108 15.843 16.108 14.706 15.595 14.518 15.766 14.535 9 3.875 4.437 2.246 5.793 16.271 16.112 16.112 16.112 15.954 15.874 16.112 15.874 10 3.576 0.878 5.127 5.331 14.832 14.72 14.766 14.583 14.7 14.492 14.766 14.517 11 3.875 3.714 5.331 0.089 12.975 12.942 12.975 12.843 12.975 12.777 12.975 12.843 12 2.432 6.65 4.459 3.576 16.952 16.952 16.952 16.622 16.457 16.952 16.622 16.457 13 1.084 6.743 2.246 0.878 10.777 10.777 10.777 10.428 10.254 10.777 10.428 10.254 14 0.874 1.063 1.046 5.127 8.097 8.072 8.072 8.072 8.047 8.034 8.072 8.034 15 7.443 1.137 7.098 0.867 16.09 15.147 15.846 14.274 16.09 14.587 14.624 13.785 16 1.016 6.966 5.9 7.254 19.288 18.863 19.064 17.572 17.646 17.965 18.268 17.286 17 4.437 0.541 6.712 3.033 14.551 14.38 14.551 13.867 14.551 13.524 14.551 13.867 18 1.561 1.582 0.231 0.318 3.692 3.692 3.692 3.692 3.692 3.692 3.692 3.692 19 0.549 1.59 2.629 1.063 5.831 5.831 5.831 5.831 5.831 5.831 5.831 5.831 20 7.093 2.597 0.789 1.226 11.496 10.868 11.287 10.659 11.496 11.287 10.24 10.24 21 0.549 6.494 5.496 3.362 15.653 15.603 15.653 15.057 15.056 15.355 15.255 14.858 22 1.582 1.071 0.429 5 8.082 8.082 8.082 8.082 8.082 8.082 8.082 8.082 23 1.561 6.559 0.405 7.528 15.644 15.139 15.139 14.827 14.165 14.38 14.827 13.913 24 7.254 4.153 1.746 5.523 18.173 16.942 17.392 16.716 17.062 16.559 16.265 16.108 25 6.309 0.231 1.59 6.929 14.604 13.564 13.826 13.434 13.31 12.855 13.172 12.593 26 6.918 4.327 7.098 0.149 17.805 16.593 17.471 15.772 17.378 16.212 15.657 15.388 27 6.309 3.362 2.597 0.131 12.268 11.875 12.137 11.744 12.268 12.137 11.483 11.483 28 1.063 0.405 4.667 5.127 11.249 11.224 11.224 11.224 11.198 11.186 11.224 11.186 29 1.063 4.41 1.561 5.962 12.899 12.707 12.707 12.707 12.515 12.418 12.707 12.418 30 1.046 1.016 0.429 6.966 9.26 8.867 8.867 8.867 8.474 8.277 8.867 8.277 31 6.219 7.18 1.063 6.918 19.324 17.931 18.335 17.65 17.51 17.154 17.406 16.83 32 3.714 5.793 0.575 1.046 11.049 11.049 11.049 10.89 10.811 11.049 10.89 10.811 33 7.098 5.127 0.878 1.151 14.018 13.351 13.796 13.103 13.98 13.796 12.658 12.658 34 5.9 4.437 2.323 1.084 13.654 13.384 13.564 13.294 13.654 13.564 13.114 13.114 35 7.254 3.576 7.87 2.104 19.44 18.364 19.15 17.519 19.247 17.91 17.638 17.068 36 3.991 0.92 0.789 4.05 9.75 9.75 9.75 9.75 9.75 9.75 9.75 9.75 37 0.429 6.32 1.582 6.559 14.602 14.29 14.29 14.026 13.582 13.822 14.026 13.426 38 7.044 1.746 7.514 5.703 19.597 19.112 19.445 18.143 19.3 17.5 19.43 18.002 39 1.226 7.528 0.651 5.523 14.623 14.518 14.518 14.012 13.655 14.361 14.012 13.603 62 Demand Strucuture 40 5.223 1.016 2.744 5.147 14.071 13.93 13.974 13.907 13.922 13.863 13.863 13.818 41 0.549 7.093 3.938 5.703 17.004 16.863 16.863 16.444 16.094 16.652 16.444 16.024 42 5.496 0.541 5 6.309 16.935 16.245 16.524 15.803 16.213 15.541 16.326 15.541 43 5.962 0.405 0.429 7.528 13.878 12.892 13.084 12.796 12.482 12.037 12.603 11.845 44 3.033 1.53 6.712 4.153 15.256 15.085 15.256 14.572 15.256 14.229 15.256 14.572 45 1.561 6.677 7.044 1.59 16.268 15.979 16.24 14.678 15.151 15.013 15.382 14.334 46 0.651 1.582 1.063 1.53 4.825 4.825 4.825 4.825 4.825 4.825 4.825 4.825 47 1.016 0.318 4.41 5.962 11.572 11.342 11.379 11.231 11.187 10.979 11.379 10.979 48 5.9 6.494 4.437 0.92 17.362 16.644 17.123 16.106 16.914 17.123 15.627 15.627 49 3.991 0.405 0.429 2.629 7.454 7.454 7.454 7.454 7.454 7.454 7.454 7.454 50 3.362 0.541 6.712 7.87 17.727 16.695 17.153 15.308 16.543 14.417 17.129 14.759 51 7.528 1.582 6.32 1.016 16.061 15.17 15.808 14.521 16.061 15.016 14.544 14.016 52 7.044 6.966 1.226 5.472 19.167 17.421 18.082 16.965 17.28 16.949 16.556 16.415 53 0.429 6.929 0.651 4.05 11.865 11.865 11.865 11.479 11.286 11.865 11.479 11.286 54 1.071 5.223 0.92 1.758 8.95 8.95 8.95 8.905 8.883 8.95 8.905 8.883 55 5.523 7.093 7.431 4.41 19.934 19.757 19.875 19.685 19.914 19.875 19.567 19.567 56 1.561 4.41 7.254 1.063 13.896 13.671 13.896 12.662 13.397 12.544 13.563 12.495 57 1.063 1.016 0.318 3.991 6.387 6.387 6.387 6.387 6.387 6.387 6.387 6.387 58 5.962 4.437 1.226 0.549 12.078 11.789 11.982 11.693 12.078 11.982 11.501 11.501 59 1.53 6.966 5.127 3.033 16.434 16.421 16.434 15.964 15.806 16.358 16.015 15.755 60 5.496 5.9 0.92 1.746 13.832 13.413 13.692 13.093 13.562 13.692 12.814 12.814 61 7.633 7.523 1.151 1.084 16.39 14.673 15.673 13.808 15.246 15.348 13.025 13.025 62 3.75 0.878 6.533 2.104 13.112 12.958 13.112 12.499 13.112 12.192 13.112 12.499 63 6.918 7.443 0.839 2.789 17.094 15.356 16.228 14.646 15.501 15.583 14.204 14.204 64 6.743 5.127 2.416 5.793 19.558 18.503 18.862 18.32 18.51 18.086 17.971 17.733 65 6.219 3.576 3.87 1.063 14.606 14.24 14.484 14.118 14.606 14.484 13.874 13.874 66 5.086 2.094 0.831 5.872 13.779 13.561 13.579 13.553 13.396 13.291 13.536 13.274 67 3.702 1.308 6.822 2.272 13.922 13.74 13.922 13.193 13.922 12.829 13.922 13.193 68 4.767 6.826 1.201 4.888 17.193 16.418 16.737 16.042 16.052 16.293 16.019 15.996 69 3.12 1.445 1.647 4.71 10.923 10.923 10.923 10.923 10.923 10.923 10.923 10.923 70 1.065 7.482 4.025 0.084 12.408 12.408 12.408 11.912 11.663 12.408 11.912 11.663 71 6.91 4.06 1.063 7.254 18.657 17.228 17.633 17.037 16.991 16.361 16.701 16.025 72 2.432 2.597 4.437 7.098 16.201 15.628 15.781 15.167 15.362 14.691 15.781 14.691 73 6.65 1.084 6.309 6.533 19.24 18.005 18.611 17.045 18.197 16.477 18.182 16.738 74 1.746 0.131 0.405 5.496 7.727 7.628 7.628 7.628 7.529 7.479 7.628 7.479 75 6.918 0.541 5.962 4.327 17.211 16.166 16.77 15.686 16.713 15.695 15.936 15.551 76 2.744 2.564 3.022 0.276 8.605 8.605 8.605 8.605 8.605 8.605 8.605 8.605 77 6.025 6.929 7.044 6.677 20 20 20 20 20 20 20 20 78 1.758 1.929 3.793 5.223 12.681 12.636 12.636 12.636 12.591 12.569 12.636 12.569 79 7.514 5.523 5.09 5.154 20 20 20 20 20 20 20 20 80 6.922 1.976 6.343 4.05 18.769 17.767 18.383 17.172 18.381 17.188 17.519 16.982 81 2.744 6.7 4.05 5.223 18.524 18.48 18.48 18.14 17.925 18.413 18.14 17.903 82 2.933 2.564 5.314 7.514 17.751 16.965 17.248 16.078 16.628 15.591 17.17 15.653 83 6.32 6.929 1.758 6.611 19.482 18.344 18.67 18.15 18.091 17.697 17.886 17.402 84 4.732 7.431 6.677 6.988 19.973 19.973 19.973 19.92 19.893 19.973 19.92 19.893 85 1.258 3.304 0.276 3.591 8.429 8.429 8.429 8.429 8.429 8.429 8.429 8.429 86 7.528 2.629 0.651 0.279 10.834 10.075 10.581 9.823 10.834 10.581 9.317 9.317 87 1.929 1.386 4.056 5.09 12.452 12.434 12.434 12.434 12.416 12.407 12.434 12.407 88 1.758 3.591 7.514 3.304 15.805 15.554 15.805 14.578 15.473 14.297 15.584 14.468 89 2.933 7.431 2.166 2.744 14.994 14.885 14.958 14.362 14.265 14.958 14.29 14.083 90 0.125 6.611 5.092 5.314 16.869 16.766 16.806 16.272 16.138 16.594 16.403 16.101 91 1.976 1.073 4.389 1.258 8.696 8.696 8.696 8.696 8.696 8.696 8.696 8.696 63 Demand Strucuture 92 7.956 2.301 4.408 0.771 15.141 14.255 14.846 13.959 15.141 14.846 13.368 13.368 93 4.382 3.123 2.638 6.456 16.454 16.163 16.163 16.163 15.871 15.726 16.163 15.726 94 4.732 6.343 6.989 3.022 19.487 18.804 19.289 18.156 18.813 18.748 17.941 17.915 95 0.687 1.645 1.382 5.548 9.207 9.097 9.097 9.097 8.987 8.933 9.097 8.933 96 4.859 1.859 0.771 3.123 10.612 10.612 10.612 10.612 10.612 10.612 10.612 10.612 97 1.442 0.34 3.608 4.382 9.773 9.773 9.773 9.773 9.773 9.773 9.773 9.773 98 1.382 7.922 4.76 6.989 19.475 19.218 19.287 18.355 18.015 18.867 18.564 17.991 99 5.154 4.408 4.816 5.889 19.863 19.649 19.708 19.471 19.553 19.298 19.708 19.298 100 2.638 1.142 6.396 3.556 13.591 13.452 13.591 13.033 13.591 12.754 13.591 13.033 Total 1429.973 1389.439 1409.455 1354.194 1381.495 1358.386 1364.069 1328.257 64 VITA Meng Li Candidate for the Degree of Master of Science Thesis: STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBIL ITY DESIGN Major Field: Industrial Engineering and Management Biographical: Personal Data: Born in Hengshui, Hebei, China on March 11, 1981. Education: Yanshan University, China B.E. in Material Engineering July, 2002 Tianjin University, China M.S. in Applied Math March, 2005 Oklahoma State University, USA M.S. in IEM December, 2008 Experience: Oklahoma State University Research Assistant 2007=09 ¡ 2008=05 SoftTech Development Inc. Software Engineer 2006=02 ¡ 2006=07 Beijing Nantian Software Co.,Ltd Software Engineer 2005=03 ¡ 2005=09 Name: Meng Li Date of Degree: December, 2008 Institution: Oklahoma State University Location: Stillwater, Oklahoma Title of Study: STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBILITY DESIGN Pages in Study: 64 Candidate for the Degree of Master of Science Major Field: Industrial Engineering and Management This thesis examines structure index for process °exibility design with e±ciency loss in cross production. We conducted numerical experiments to study the performance of the SF (Structure Flexibility) Matrix Index and the Graph Expander Index with two types of e±ciency loss: shrinking capacity or additional cost in cross production. Our experiments suggest that SF index and expander index are purely robust and powerful in predicting system performance ranking at demand variation. This suggests that the SF index and graph expander index can help managers to design good manufacturing °exibility structure, without requiring intensive simulation. ADVISOR'S APPROVAL:
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Study of Flexibility Indices in Manufacturing Flexibility Design 
Date  20081201 
Author  Li, Meng 
Department  Industrial Engineering & Management 
Document Type  
Full Text Type  Open Access 
Abstract  This thesis examines structure index for process flexibility design with efficiency loss in cross production. We conducted numerical experiments to study the performance of the SF (Structure Flexibility) Matrix Index and the Graph Expander Index with two types of efficiency loss: shrinking capacity or additional cost in cross production. Our experiments suggest that SF index and expander index are purely robust and powerful in predicting system performance ranking at demand variation. This suggests that the SF index and graph expander index can help managers to design good manufacturing flexibility structure, without requiring intensive simulation. 
Note  Thesis 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBILITY DESIGN By MENG LI Bachelor of Engineer in Material Engineering Yanshan University Qinhuangdao, Hebei, China 2002 Master of Science in Applied Mathematics Tianjin University Tianjin, China 2005 Submitted to the Faculty of the Graduate College of Oklahoma State University in partial ful¯llment of the requirements for the Degree of MASTER OF SCIENCE December, 2008 COPYRIGHT °c By MENG LI December, 2008 STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBILITY DESIGN Thesis Approved: Dr. Tieming Liu Thesis Advisor Dr. Manjunath Kamath Dr. Ricki G. Ingalls Dr. A. Gordon Emslie Dean of the Graduate College iii ACKNOWLEDGMENTS The past two years at OSU have been an immensely rewarding educational and intellectual experience. Much of the credit for this must go to my advisor Prof. Tieming Liu. Interacting with Dr. Liu has developed my analytical skills more than I could have imagined. Many thanks to Prof. Manjunath Kamath and Ricki G. Ingalls for their encouragement and help in the editing process. Their feedback has been invaluable. I would also like to thank Prof. Baski Balasundaram and Alan Noell for their helpful comments. I owe tremendous debt of gratitude to my parents Minzheng Li and Shujing Wang and to my sister Ye Li. The frequent weekend conversations with them were always eagerly anticipated. I thank my parents and sister for all their love and for everything they have done for me. I would like to thank my wife Yingzhe Wu, who always has con¯dence in me and always stays with me to overcome whatever di±culty I face in my daily life during my study in OSU. I have been very lucky to have had very pleasant, friendly and helpful o±cemates and classmates, namely, Dahai Xing, Sandeep Srivathsan, Peerapol Sittivijan, Karthik Ayodhiramanujan, Sharethram Hariharan, Chinnatat Methapatara, Mario Cornejo Barriere, Hui Yang and Xiaowei Yang. We have had some great moments together, and I would like to thank them for the help and encouragement. iv TABLE OF CONTENTS Chapter Page 1 Introduction 1 1.1 Research Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Research Objective and Scope . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organization of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Literature Review 6 2.1 Literature Review on Manufacturing Flexibility . . . . . . . . . . . . 6 2.2 Literature Review on Graph Expander . . . . . . . . . . . . . . . . . 8 3 Methodology 10 3.1 Manufacturing Flexibility Model . . . . . . . . . . . . . . . . . . . . . 10 3.2 Chain Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 SF Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3.1 SF Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Graph Expander . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.4.1 Expander Index . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Shrinking Capacity Case 18 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Model in Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . 18 4.3 SF Matrix of Shrinking Capacity Case . . . . . . . . . . . . . . . . . 20 4.3.1 Algorithm for SF Matrix Construction in Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 v 4.4 Graph Expander . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4.1 Graph Expander in the Shrinking Capacity Case . . . . . . . . 24 4.5 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.5.1 Chaining Structure . . . . . . . . . . . . . . . . . . . . . . . . 27 4.5.2 General Structures . . . . . . . . . . . . . . . . . . . . . . . . 32 5 Additional Cost Case 36 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Model in Additional Cost Case . . . . . . . . . . . . . . . . . . . . . 36 5.3 SF Matrix of Additional Cost Case . . . . . . . . . . . . . . . . . . . 38 5.3.1 Algorithm for SF Matrix Construction in Additional Cost Case 40 5.4 Graph Expander in Additional Cost Case . . . . . . . . . . . . . . . 40 5.5 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5.1 Chaining Structure . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5.2 General Structure . . . . . . . . . . . . . . . . . . . . . . . . . 47 6 Conclusion 51 BIBLIOGRAPHY 53 A Simulation Results in Shrinking Capacity Case 56 B Numerical Results in Additional Cost Case with Di®erent Price 59 C Numerical Results in Additional Cost Case with Same Price 62 vi LIST OF TABLES Table Page 4.1 Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Shrinking Capacity Case . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 SF Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.1 Additional Cost Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Additional Cost Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.3 SF Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 vii LIST OF FIGURES Figure Page 3.1 Total Flexibility structure; n Suppliers Service All the m Demands. . 11 3.2 Two Manufacturing Flexibility Structures. . . . . . . . . . . . . . . . 13 3.3 Two Paths From Demand B to Demand D. . . . . . . . . . . . . . . . 14 4.1 nn Partial Flexibility Structure . . . . . . . . . . . . . . . . . . . . . 19 4.2 44 Manufacturing Flexibility Structure in Shrinking Capacity Case. . 21 4.3 SF Matrix Index (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4 Graph Expander Index(the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.5 SF Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.6 Indices for SF Structures (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.1 44 Manufacturing Flexibility Structure in Additional Cost Case. . . . 39 5.2 SF Matrix Indices for Additional Cost Case . . . . . . . . . . . . . . 44 5.3 SF Matrix Indices for Additional Cost Case (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . 45 5.4 Graph Expander Index (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.5 SF Indices, Up: Biggest Eigenvalue Index; Down: Mean Value Index (the number beside each node is the structure it is associated with). . 48 viii 5.6 Expander Indices for SF Structures (the number beside each node is the structure it is associated with) . . . . . . . . . . . . . . . . . . . 48 ix CHAPTER 1 Introduction 1.1 Research Background In today's competitive business environment, enterprises are facing dramatic changes in customer requirement, shortened development cycle, and uncertainty in the oper ation environment. The demand a company is facing maybe di®erent each month or each year. To make things worse, there are probably no patterns to trace the demand. The traditional way to overcome uncertainties is to have inventory safety stock. Inventory provides a safety cushion only for a narrow segment of demand uncertainty. However accumulating inventory can leave manufacturers with inventory of unwanted products, and changes in technology can leave manufactures with stocks of obsolete inventory. In addition, the investment in the safety stock leads to lower investment in other parts of the company. In the current manufacturing environment, with increased customer expecta tions, along with the prevailing uncertainties, °exibility has emerged as an important method to achieve competitive advantage. Manufacturing °exibility (the ability of a plant or machine to process more than one product at the same time (Graves and Tomlin (2003)) is a key strategy for improving market responsiveness facing of un certain product demand. Leadingedge ¯rms are coming to understand requirements for manufacturing °exibility. Especially the Japanese companies ranked °exibility to introduce new products as their second, and to adjust production volume as their fourth competitive priorities (De Meyer et al. (1989)). Despite the growing importance of °exibility over the decades, ¯rms still struggle 1 to implement manufacturing °exibility (Gerwin (1993)). Many ¯rms struggle to make the costly investments in manufacturing °exibility due to the problem of recognizing the bene¯t of the °exibility. Flexibility is usually considered as a \backup" or an \insurance," and in many situations, °exibility does not contribute, or contributes very little, to manufacturers' revenue. At the same time, it is less common to quantify the bene¯ts, because demand uncertainty is usually not explicitly considered by the planners. Many manufacturers hesitate to invest a huge amount of money to achieve a high degree of °exibility. If plant can produce more than one product, then the degree of °exibility means the production e±ciency for products that can be produced by the plant. Hence, high degree of °exibility implies high productivity. In practice, °exibility does not come free, and higher the degree of °exibility, the higher is the cost. Manufacturers often seek a moderate degree of °exibility that would not cost much, but could hedge them against demand variability. Investing for the optimal degree of °exibility remains a crucial decision for many manufacturers. However, the academic literature often ignores the investment cost in °exibility. Most papers studying manufacturing °exibility do not consider the e±ciency loss incurred at switching, and they do not consider the possibly high costs associated with °exibility (Jordan and Graves (1995), Hopp et al. (2004), Iravani et al. (2005), etc.). Even with considerable degree of °exibility, changeover time (the time necessary for the process to be setup in order to change from making one product type to another) is still inevitable when the production is switched from one product to another. In some cases, the ability to build every product using same production capacity is impossible if the products are di®erent enough, although they share some common parts or procedures. 2 1.2 Research Objective and Scope The objective of this study is to model the e±ciency loss that occurred in the man ufacturing °exibility, and analyze the °exibility structure indices. We evaluate the structure performance based on structure index, which can rank structure perfor mance without precise information regarding the demand and capacity. In this thesis, we coin the term \cross production" to represent the ability to produce product A using a machine dedicated to product B, with certain e±ciency loss. For example, consider a ¯rm with two products and two types of partial °exible capacity. Each type of capacity is designed for a single product, but since the two products share some common features, the capacity for one product can also be used to produce the other product with some e±ciency loss. Cross production is a major source, and sometimes the only possibility, to realize °exibility on the supply side. The ability to conduct cross production to match supply with demand is crucial for a ¯rm. Lack of cross production may seriously decrease a ¯rm's market share, pro¯tability, and capacity utilization, which is illustrated by the following example. Chrysler's PT Cruiser was a new design based on the Neon, and it turned out to be a very fashionable model soon after its debut in 2000. Its dedi cated plant in Toluca, Mexico, was not able to satisfy the unexpected high demand. However, at the same time, the dedicated plant for the original Neon in Belvidere, Illinois, was underutilized. If Chrysler could make cross production, even with some e±ciency loss or additional costs, it has been estimated that up to $240M pretax pro¯t could have been gained. E±ciency loss in cross production may come from shrinking capacity, additional cost, or both. Shrinking capacity implies that fewer units of products will be pro duced if one type of capacity is used to produce the other type of product. The phenomenon of shrinking capacity in cross production is commonly observed in the industry. Productivity will decrease when a plant dedicated for one type of product is 3 used to produce another product, caused by speci¯cally designed machine, changeover time, or insu±ciently cross trained workers. Additional cost indicates that extra unit cost will be added if one type of product is produced using the other type of capacity. Production cost will increase when one type of product is produced in a plant that is dedicated for another type of product due to additional manufacturing process, changeover cost, or additional training to workers. Given that there are costs associated with creating and maintaining manufacturing °exibility, and di±culties managing the resulting complex system, it is desirable to understand the value of this °exibility in more depth. The following issues are relevant in the setting of manufacturing °exibility: °exibility type, °exibility mechanisms (how much °exibility, and where the °exibility should be introduced), and °exibility measurement. Gerwin(1993) argued persuasively that °exibility measurement is necessary to characterize and evaluate the uncertainty types, °exibility types and °exibility mech anisms. Without measurement, it is hard for the management to e®ectively assess °exibilityrelated choices, costs, achievability, performance bene¯ts and tradeo®s. Notwithstanding the importance and the constant interest raised by °exibility in academic and managerial circles, the measure of °exibility is still an underdeveloped subject, and no wellaccepted measure exists. Very limited work has been done on investigating the robustness of the suggested measurements (De Toni and Tonchia (1998)). In this study, we propose new measurements especially on the shrinking capacity case and the additional cost case. We are especially interested in developing simple methods that computes an index for each manufacturing structure, which can be used to predict which structure has better and more robust performance, without needing precise information regarding the patterns of the changes in the system. Specially, there are two goals in this work. First, we present an introduction 4 to cross production concept in the manufacturing °exibility design, especially the shrinking capacity and additional cost cases, and then model them in order to ¯t them into the manufacturing design. Second, we extend the work on the measurement of the manufacturing °exibility by new analysis and new constructions. 1.3 Organization of Thesis The thesis is arranged as follows. In Chapter 2, we review literature related to this thesis in two areas: manufacturing °exibility and graph expander theory. In chapter 3, we introduce the classical manufacturing °exibility model, SF(Structure Flexibility) matrix (Iravani et al. (2005)), and the basic concept in the subject of graph expansion (Fiedler (1973)). In Chapter 4, we set up the model of the shrinking capacity case, and establish the connection between it and SF matrix. We also demonstrate the graph expander theory in the shrinking capacity case. In chapter 5, we introduce another type of e±ciency loss, the additional cost case, in manufacturing °exibility, and model it using linear programming, then use the modi¯ed SF matrix and Laplacian matrix to get the structure index. Finally, we conclude and discuss future directions. 5 CHAPTER 2 Literature Review In this chapter, we review literature related to our research in the manufacturing °ex ibility and graph expander areas. Flexibility is emerging as one of the key competitive advantages for any manufacturing ¯rm in dealing with the increasingly complex man ufacturing environment. In the past two decades, numerous e®orts have been made to characterize and measure °exibility. These e®orts are classi¯ed and critically re viewed in the ¯rst part of this chapter. Graph expander has been a rapidly developing subject in discrete mathematics and computer science in the past three decades. It has been applied in many ¯elds, including network design, algorithms, coding, cryp tography, and pseudorandomness. We review the literature related to our study in manufacturing °exibility in the second part of this chapter. 2.1 Literature Review on Manufacturing Flexibility We organize the content of this part of the review into three basic streams: de¯nition and classi¯cation of manufacturing °exibility, manufacturing °exibility design, and manufacturing °exibility structure index. One stream of literature related to our research is de¯nition and classi¯cation of manufacturing °exibility. Sethi and Sethi (1990) categorized the °exibility application in eleven types, such as machine °exibility, operation °exibility, resource °exibility, etc. The literature often refers to manufacturing °exibility as \process °exibility." Shi and Daniels (2003) provided an extensive survey on the literature related to e business °exibility. \EBusiness °exibility," a new area of °exibility, becomes a key 6 interface between companies of all sizes and their supplies and customers. There are a series of papers about the °exibility design. Jordan and Graves (1995) have studied chain structure in supply chains in their classical °exibility design paper. They observed that well designed limited °exibility is almost as good as full °exibility in the singlestage manufacturing system with random demand and deterministic capacity. In addition, they proposed one measure, the maximal probability over all groupings or sets of products, to estimate the structure performance. Graves and Tomlin (2003) extended the former work to multistage manufacturing systems. The above two papers showed that limited °exibility has the greatest bene¯ts when con¯gured to chaining structure, which is de¯ned as a group of products and plants, which are all connected, directly or indirectly (Jordan and Graves (1995)). Many studies have been done about the application of chaining structure to design the manufacturing °exibility. Hopp et al. (2004) emphasized the power of chaining structures in CONWIP (CONstant WorkInProcess) production lines with cross trained workers. They proposed that if workers in the line are crosstrained according to a chain structure, then the line achieves a relatively high throughput compared to other crosstraining structures. Gurumurthi and Benjaafar (2004) viewed °exible queueing systems as a connected bipartite undirected graph, a similar representation of Aksin and Karaesmen (2007). Sheikhzadeh et al. (1998), Iravani et al. (2005, 2007), Jordan et al. (2004) and Chou et al. (2007) also highlight the properties of the chaining structure in di®erent production, maintenance and service environ ments. Lien et al. (2005) introduced the chained shipment structure and showed the superiority of this chain structure over the grouping con¯gurations. Aksin and Karaesmen (2007) provided analytical comparison results on °exibility structure in their paper. They applied network °ow problem to the study of maximal throughput of °exible structure, and provided a theoretical study on the symmet ric °exible system, and derived submodularity property on the °exibility structure. 7 They established certain °exibility design principles for service and manufacturing systems. In our work, we adopt their analytical approach. The performance measure is a key part of manufacturing °exibility. Flexibility measures are needed to test theories and make capital investment decisions. A key paper about the manufacturing °exibility index was written by Iravani et al. (2005). Their paper focused on strategiclevel issues of how °exibility can be created by using multipurpose resources such as crosstrained labor, °exible machines, or °exible factories. They proposed the SF indices as the measure for the °exibility structure. The SF indices are simple tractable measures, which can be used to rank the structures performance. Chou et al. (2007) proposed another index based on the concept of graph expander, which is widely used in graph theory ¯eld. This index has more theoretical background, and just has one index that has more use value than SF indices. In this thesis, we use the methods of Iravani et al. (2005) and Chou et al. (2007) to the shrinking capacity and additional cost cases. 2.2 Literature Review on Graph Expander We organize the content of the literature on graph expander into two basic streams: theory of graph expander and graph expander application. The ¯rst stream corre sponds to the basic concept of graph expander, the second stream is focused on its application in manufacturing design. Expander is a graph for which any small subset of vertices has a relatively large neighborhood. Bassalygo and Pinsker (1973) ¯rstly introduced graph expander in the ¯eld of communication networks. Intuitively, a regular undirected graph is an expander if it is highly connected. That is, it is easy to get from any vertex to any other vertex in very few steps. Normally, we also impose that they have low degree, because in many applications the cost of the graphs is related to their degree (Xiao (2003)). 8 Many measurements have been used to quantify this expansion property. Such measures include vertex expansion and edge expansion properties. They unfortu nately are hard to compute. However, a series of works by Alon (1986), Alon and Milman (1985), and Tanner (1984) built the relationship between the expansion of graph with the second largest eigenvalue of the graph. This provides us an e±ciently computable method of the expansion of a graph. More importantly, it allows us to apply the tools of linear algebra in analyzing expander graphs. Reingold et al. (2002) built large scale near optimal expanding graphs by \zigzag," which is a recursive construction of the expander graph families. Graph expander has spawned research in pure and applied mathematics, with wide applications in many areas. Expander graph found applications in the design of explicit supere±cient communication networks, constructions of errorcorrecting codes with very e±cient encoding and decoding algorithms, derandomization of ran dom algorithms, and analysis of algorithms in computational group theory (Sarnak (2004)). Chou et al. (2007) built the connection between graph expander and process °exibility, and showed that e±ciently expander gives rise to good process °exibility, and mathematically proved the existence of good partial °exibility structure in iden tical demand and supply case. The main di®erence of our work compared to other researchers is that we study the cross production, and model two special cases: shrinking capacity and additional cost { which are two main sources of e±ciency loss. In this thesis, we study the manufacturing °exibility models with random demand and deterministic capacity. In addition, we construct the indices for those two special cases using the SF matrix and the graph expander. 9 CHAPTER 3 Methodology In this chapter, two di®erent methods are investigated to create index for manufac turing °exibility in the shrinking capacity case and the additional cost case. This chapter provides a brief history of the two methods followed by the details of speci¯c implications for this research. 3.1 Manufacturing Flexibility Model In this section, we study the basic concept of the manufacturing °exibility model in a general nm (n suppliers and m demands) structure. We also introduce the optimal solutions for this nm structure. Aksin and Karaesmen (2007) and Chou et al. (2007) proposed a bipartite graph G = (A [ B; F) to represent the °exible structure. The lefthandside nodes A = f1; 2; ¢ ¢ ¢ ; ng with capacity (q1; q2; ¢ ¢ ¢ ; qn) denote the suppliers and the righthand side nodes B = f1; 2; ¢ ¢ ¢ ;mg with capacity (d1; d2; ¢ ¢ ¢ ; dm) represent the demands. Whenever a demand type j 2 B can be supplied by the supplier i 2 A, an arc (i; j) 2 F with in¯nite capacity is added to the the network. The network in Figure 3.1 illustrates a case where all the suppliers can serve all the demands. The decision variables xij denote the amount of demand for product j supplied by plant i; sj is the shortage of demand j, that is the amount of demand for product j that cannot be satis¯ed. We evaluate a manufacturing °exibility structure in term of the expected de mand shortage that cannot be covered by the supplies. The minimum shortage for a 10 G, S(G), can be acquired by solving the following linear program (Jordan and Graves (1995)): S(G) = min Xm i=1 sj s:t: X (i;j)2F xij + sj ¸ dj 8 j = 1; 2; ¢ ¢ ¢ m: X (i;j)2F xij · qi 8 i = 1; 2; ¢ ¢ ¢ n: (3.1) n1 n 2 3 1 m 2 3 1 4 Supply Demand s t q1 q2 qn1 qn d1 d2 dm q3 d3 d4 Figure 3.1: Total Flexibility structure; n Suppliers Service All the m Demands. By Jordan and Graves(1995), the optimal objective value of (3.1) equals to (3.2). The maximization in (3.2) is over all subsets M (including the null set) of the index set f1; 2; ¢ ¢ ¢ ;mg . That is, the maximization is over all combinations of the products. For any given subset of products M, P(M) is the subset of plants that can produce at least one of the products in M. That is, P(M) = fi 2 A : (i; j) 2 F; j 2 Mg. The 11 optimal objective value of (3.1) equals to: S(G) = max 8< :0; max M 2 4 X j2M dj ¡ X i2P(M) qi 3 5 9= ;: (3.2) The problem of maximizing the output generated by a given con¯guration for a demand realization (d1; d2; ¢ ¢ ¢ ; dm) is equivalent to the maximum °ow problem for this network. So the maximal output of above structure is : O(G) = Xm j=1 dj ¡ S(G) = min M 8< : Xm j=1 dj ¡ X j2M dj + X i2P(M) qi 9= ; = min M 8< : X j =2M dj + X i2P(M) qi 9= ;:(3.3) Jordan and Graves (1995) and Chou et al. (2007) showed similar results. Intuitively, we can think (3.3) is the consequence of the max°owmincut theorem where the arc between A and B has in¯nite capacity: the maximal output of a structure corresponds to the minimal cut in the capacitated production network. In this study, we adopt the manufacturing °exibility structure model as shown above, and apply it to the shrinking capacity and the additional cost case. 3.2 Chain Structure This section provides a brief study of chain structure, which is de¯ned as a group of products and plants which are all connected, directly or indirectly. As mentioned before, Jordan and Graves (1995) showed that chain structure can greatly increase the expected throughput of manufacturing °exibility structure. In a chain structure, excess capacity of any plant can be shipped to any other products via production assignment schedule. For example, in the right structure of Figure 3.2, if demand for A is greater than expected, and demand for D is less than expected, with one long chain the production capacity for product D can be transferred to demand A. So the chain structure can accommodate increased demand of node A and decreased demand of node D. However, the left structure in Figure 3.2 12 cannot ship the excess capacity of demand D to demand A because there is no link between node D and node A. 1 2 3 A B C 4 D 1 2 3 A B C 4 D Supply Demand Supply Demand Figure 3.2: Two Manufacturing Flexibility Structures. In the numerical analysis in subsequent chapters, we are particularly interested in the chain structure performance because of e®ectiveness of the chain structure compared to other structures. 3.3 SF Matrix In this section, we review the SF (Structure Flexibility) matrix, ¯rst introduced in Iravani et al. (2005). We use the °exibility structure shown in Figure 3.3 to describe this method. Figure 3.3 indicates two di®erent paths from demand B to demand D. The demand of each plant is random so that the demand B decreases ±, and the demand D increases ±. We assume the capacity is tight, so that the excess capacity ± for demand B need 13 1 2 3 A B C 4 D Supply Demand 1 2 3 A B C 4 D Supply Demand Figure 3.3: Two Paths From Demand B to Demand D. to be shipped to demand D. Each path represents a di®erent way of shipping the unused production capacity for product B to produce product D. The ¯rst path on the left, B ! 2 ! C ! 3 ! D, represents the following shipping of production capacity: there exist excess ± unit capacity available for demand B. Hence, supply 2 can produce amount ± more of product C, which can make supply 3 produces more ± units of demand D in order to respond the extra ± unit demand for demand D. The path on the right of Figure 3.3 is another way of transferring excess capacity for product B to satisfy the extra demand for demand node D: B ! 1 ! A ! 4 ! D. Iravani et al. (2005) measured structure °exibility by counting the total number of nonoverlapping paths a system can use to respond to a particular change in demand. They proposed SF matrix to quantify the ability to shift excess capacity to respond to change in demand. Let mij be the total number of nonoverlapping paths by which the excess capacity for product i can be transferred to produce product j. Iravani et al. (2005) argued that shipping excess capacity from product i to produce product i does not make clear sense. So they de¯ned mii be the total number of arcs connected 14 to demand node i. Consequently, the SF matrices for structures in Figure 3.2 become Mleft = 2 66666664 2 2 0 0 2 2 0 0 0 0 2 2 0 0 2 2 3 77777775 ; Mright = 2 66666664 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 77777775 : It is easy to see that right structure of Figure 3.2 to respond to changes uses more paths than left structure of Figure 3.2. In our study, we extend the de¯nition of mij to be total numbers of nonoverlapping paths by which the excess capacity of plant i can be shipped to produce product j. This de¯nition is applicable to mii because this de¯nition makes clear sense for the diagonal element of SF matrix. 3.3.1 SF Index To be able to compare the °exibility of two di®erent structures, Iravani et al. (2005) further compacted the information in SF matrix in the form of two scalars, \SF indices," which consists of mean value and dominant eigenvalue. Mean Value: It is clear, comparing Mleft and Mright of the structures shown in Figure 3.2, that SF matrices with larger elements represent more °exible structures. At the same time, matrices with larger elements will have a larger mean, which is de¯ned as the mean of all the elements in SF matrix. Although the mean of the elements of the SF matrix is an indicator of how large the elements of the matrix are, it is not sensitive to the location of the larger elements of the matrix. It is easy to see that di®erent matrix maybe have same mean value. This is one important reason why the authors considered another index, the dominant eigenvalue. Dominant Eigenvalue: Because SF matrix is real, symmetric, and nonnegative, its eigenvalues are real and nonnegative. So for a system with n supplies and n demands, the SF matrix has n eigenvalues ¸1; ¸2; ¢ ¢ ¢ ; ¸n. The biggest eigenvalue is 15 ¸ = maxf¸1; ¢ ¢ ¢ ; ¸ng, which is an indication of the magnitude of elements of a matrix. Iravani et al. (2005) showed that, as any element of the SF matrix increases (i.e., more °exibility), the dominant eigenvalue of the matrix increases. The eigenvalue index is sensitive to the location and variation of the elements of the SF matrix, and di®erent matrices with the same mean index may have di®erent dominant eigenvalues. In this study, we extend the SF matrix construction method to the shrinking capacity and additional cost case. In additional, we use SF indices to analyze the structures in these two special cases. As mentioned before, SF matrix lacks of theoretical support, so we consider an other index, expander index, which is much easier solved than SF index. 3.4 Graph Expander In this section, we introduce the basic concept about graph expander theory, and the connection between graph index and manufacturing °exibility. Expander graphs are one of the most useful tools of theoretical computer science and discrete mathematics, motivating many applications since their introduction in the 1970s. Let G = (V;E) be an directed graph with n nodes and m edges, where V and E represents vertices and edges. The incidence matrix of G is a n£m matrix such that Til = ¡1, if the edge l leaves node i, Tjl = 1, if it enters node j and 0 otherwise. The Laplacian matrix L of G is the n £ n matrix L = TT0. Clearly, the L is independent of what orientation is chosen for. L is positive semide¯nite, and L1 = 0, where 1 is the vector of all ones. Let 0 = ¸1 · ¸2 · ¢ ¢ ¢ · ¸n be the eigenvalues of L. The second smallest eigenvalue ¸2(L) has been used to measure connectivity, and is called the algebraic connectivity of the graph G (Fiedler (1973)). 16 3.4.1 Expander Index There are many reasons the algebraic connectivity is considered to be a measure of how wellconnected a graph is. For example, if G1 = (V;E1) and G = (V;E2) are such that E1 µ E2, then ¸2(L1) · ¸2(L2). That is, a better connected graph (on the same vertex set) has a greater algebraic connectivity. In addition, the algebraic connectivity has a direct connection to the number of connected components in a graph: G is connected if and only if ¸2(L) > 0; in fact, the multiplicity of the eigenvalue 0 is exactly equal to the number of connected components in G. ¸2(L) > 0 means that there is only one zero eigenvalue, then we can conclude that the graph is connected (Fiedler (1973))). Chou et al. (2007) found that many important results in the literature of graph expander are closely related to the results in the process °exibility ¯eld in the following two ways. First, Jordan and Graves (1995) suggested that a \welldesigned" sparse structure, which has a small °exibility, is almost as °exible as the total °exibility structure. Pinsker (1973), however, stated that there exists a sparse structure with O(n) arcs that has almost the same expansion as a complete graph. Actually the \welldesigned" sparse structure and total °exibility structure correspond with the sparse structure and the complete graph. Second, Iravani et al. (2005) proposed that the °exibility of a structure can be measured by the largest eigenvalue of its SF matrix. This statement corresponds to the ¯nding of Tanner (1984), that the expansion level of a graph is bounded by the spectral gap. Based on the two observations, Chou et al. (2007) built the relationship between the graph expander and the nn manufacturing °exibility structure. In this study, we extend their results to the shrinking capacity and additional cost case. 17 CHAPTER 4 Shrinking Capacity Case 4.1 Introduction In this chapter, we study the manufacturing °exibility index in shrinking capacity case. To evaluate the structural performance, we build up the SF(Structure Flexibil ity) matrix and Laplacian matrix in the shrinking capacity case, and examine the SF indices and expander indices in di®erent manufacturing structures. We ¯rst test the chaining structure. Then we test the performance of SF indices and expander indices in the general structure (nonchaining structure). 4.2 Model in Shrinking Capacity Case In this section, we de¯ne specialized production and cross production, and model the shrinking capacity case in linear programming. First, we de¯ne the specialized production and cross production as follows: De¯nition 4.1 Specialized Production: A plant can produce a product without e±ciency loss. De¯nition 4.2 Cross Production: For some plants, there exist demands that the plant produces with shrinking capacity. For simplicity, we use nn °exibility manufacturing in Figure 4.1 to illustrate the two de¯nitions mentioned above. In the nn structure, we distinguish them in the following way: specialized production(1¡1; 2¡2; 3¡3; :::; n¡n manufacturing) and cross production (i ¡ j(i 6= j) manufacturing). 18 n1 n 2 3 1 n1 n 2 3 1 n2 4 Supply Demand s t q1 q2 qn2 qn1 qn d1 d2 dn1 dn q3 d3 d4 Figure 4.1: nn Partial Flexibility Structure It is very common that the productivity of the plant could have some decrease in the cross production. Hence, we introduce the concept \shrinking factor." De¯nition 4.3 Shrinking Factor: In the manufacturing °exibility structure, the shrinking factor of i ¡ j manufacturing is kij = qj i qi , and qj i means the amount of product j we can produce with supply i. In our problems, specialized production does not cause a decrease in the capacity, and cross production cause the decrease in some degree. That is: kij ( = 1 if i = j, < 1 if i 6= j. Next, we set up the model of shrinking capacity in linear programming. In our op timization problem, we use the the minimal shortage, S(G), as the objective function. The minimal shortage of nm structures (n suppliers and m demands) in shrinking 19 capacity case can be acquired by solving the following linear program: S(G) = min Xm j=1 sj (4.2) s:t: X (i;j)2F xij + sj ¸ dj 8 i = 1; 2; ¢ ¢ ¢ n; X (i;j)2F xij kij · qi 8 j = 1; 2; ¢ ¢ ¢ m: The above formulation is used in the subsequent numerical analysis in this chapter. 4.3 SF Matrix of Shrinking Capacity Case In this section, we extend SF matrix to the shrinking capacity case, and introduce the algorithm for the construction of SF matrix in the shrinking capacity case. For simplicity, in this section, we focus on the nn °exibility manufacturing structure to show how to build the SF matrix in the shrinking capacity case. We assume that the full (noshrinking) capacity of each supply node is 1. SF matrix was proposed by Iravani et al. (2005), which is a key paper for the study of the °exibility manufacturing structure. They created the SF matrix in the following way: (1) for nondiagonal element: \the total number of nonoverlapping paths a system can use to respond to a particular change in demand," which can be obtained by solving the maximal °ow problem. (2) for diagonal element: the number of arcs connected to the corresponding supply node. In our model, we set the element of the SF matrix as the maximal °ow from each supply node to each demand node. Our method extends the work of Iravani et al. (2005) in the following way: (1) for nondiagonal element, for the demand node i, the total capacity of nonoverlapping paths a system can use to respond to a particular change in demand equals the maximal °ow from each supply node i to demand node j. (2) for diagonal element: the arc number connected to the corresponding supply node i is extended as the maximal °ow from supply node i to demand node i. Notice, 20 the maximal °ow here is di®erent from the traditional maximal °ow problem, because after passing through each arc, we need to consider the capacity loss. We use manufacturing °exibility structure shown in Figure 4.2 as example, the diagonal element, m11, of SF matrix is 1 £ (1 + k12k23k34k41) = (1 + k12k23k34k41), which is the maximal °ow from supply node 1 to demand node 1; the nondiagonal element, m12, of SF matrix equals 1 £ (k12 + k41k34k23) = (k12 + k41k34k23), which is the maximal °ow from the supply node 1 to demand node 2. 1 2 3 4 1 2 3 4 Plant Demand x11/1 x12/k12 x23/k23 x22/1 x33/1 x34/k34 X44/1 x41/k41 s t q1 q2 q3 q4 d1 d2 d3 d4 Figure 4.2: 44 Manufacturing Flexibility Structure in Shrinking Capacity Case. To get the elements of SF matrix, Iravani et al. (2005) used a maximal °ow formulation to ¯nd the maximum number of units of source e®ort that can be shipped from a demand start node, i, to a demand sink node, j, in a particular structure. Unfortunately, their methodology cannot be used directly to the shrinking capacity case, because of the multiplication of shrinking factors associated with each arc in the path. For example, if there exists a route R1 = 1 ¡ 2 ¡ 2 ¡ 3 from the source node 1 to demand node 3, as shown in Figure 4.2. The maximal °ow of this route is k12k23, 21 not min(k12; k23), given the full capacity of node 1 is 1. With the increasing of °exibility in the manufacturing structure, it is not easy to solve the maximal °ow between supply node and demand node. In chain structure, there are only two paths from each supply node to demand node. But for nonchaining structure, it is not easy to get the maximal °ow between two nodes. This motivates for our algorithm in the next section. 4.3.1 Algorithm for SF Matrix Construction in Shrinking Capacity Case The above maximal °ow problem can be transferred to the shortest path problem. We want to get the route p 2 P, so that Q (i;j)2p kij of the route be the maximal value in all routes P. Because log Q (i;j)2p kij = P (i;j)2p log kij , and the maximal points of Q (i;j)2p kij and log Q (i;j)2p kij are equal, the problem can be easily trans ferred into maxp2P P (i;j)2p log kij . Because 0 · kij · 1, maxp2P P (i;j)2p log kij = minp2P P (i;j)2p(¡log kij). Let ¡log(kij) represent the distance from node i to node j. The °ow between node i and j is transformed to solve the distance between i and j. For example, the °ow of route R1, as we mentioned in the last section, can be acquired by exp(¡d13), where d13 = (¡log k12) + (¡log k23) + (¡log k22) = (¡log k12) + (¡log k23). After getting the shortest route between two nodes by this method, we can delete the arcs that this route passes, and then ¯nd the second shortest path; repeat this until there are no paths available. The shortest path problem can be easily solved by several well established algorithms, such as Dijkstra's algorithm. The algorithm, which gets the maximal °ow from node s to t, is as follows: Step 1: To input incidence matrix T of the structure, s and t; Initialize i = 1. Step 2: Calculate the shortest path pi and its distance di, which is the summation of the absolute values of logarithms of shrinking factors that the path contains. Step 3: Delete the arcs that pi passes, and check if the node s is connected to t. If 22 they are disconnected, go to Step 4; if there are still routes from node s to t, then update the incidence matrix T, set i = i + 1, and go to Step 2. Step 4: Calculate the element of mst of SF matrix, mst = P i exp(¡di). 4.4 Graph Expander As mentioned before, SF matrix indices lack the mathematical support. At the same time, graph expander theory can help us get another structure index, which has more mathematical supports than SF matrix. This motivates for the graph expander index in this section. In this section, we study the relationship between graph expander theory and manufacturing °exibility in the shrinking capacity case. In addition, we propose a method to construct expander index in the shrinking capacity case. The expander graph is a graph G = (V; F), in which every subset S of vertices expands quickly, in the sense that it is connected to many vertices in the set S of complementary vertices. Chou et al. (2007) gave the formal de¯nition of the graph expander in the bipartite graph as shown in De¯nition 4.4. To make it clear, we need the following notation: The degree of a vertex v is deg(v), which is the number of edges incident to v. The number of vertices in set S is jSj. N(S) denotes the neighborhood of set S, that is, N(S) = fj 2 B : (i; j) 2 F, for some i 2 Sg . De¯nition 4.4 A bipartite graph G = (A S B; F), with partite sets A and B, and edge set F, is a (®; ´; ¢)expander if deg(º) · ¢ for every º 2 A, and for all S ½ A, with jSj · ®jAj, then jN(S)j ¸ ´jSj. For simplicity, we assume jBj = jAj = n. It is clear that ®´ · 1, because jAj ¸ jN(S)j ¸ ´jSj holds for any set S with jSj · ®jAj. Intuitively, a bipartite graph expander is a graph with high connectivity, i.e., the neighborhood of small 23 subsets in A is expanded by a factor ´ > 1. We are particularly interested in the graphs that have a low degree, because in the real world we expect less connectivity but more °exibility. A series of work initiated by Pinsker (1973), Friedman (2003) and Chou et al. (2007) showed that in fact there exist speci¯c graphs that have this property with high probability as indicated in as shown in Lemma 4.1. As mentioned before, Chou et al. (2007) indicated that the connection between the chain structure and the full °exibility structure in the graph expander perspective in the following lemma. Lemma 4.1 In the problem with n supplies (each with capacity qi) and n demands (with random demand Dj), if (i) E(Dj) = ¹ for all j, (ii) P(Dj > ´¹) = 0 for all j and (iii) qi = ¹ for all i, then there is a partial °exible structure F, with jFj · n¢, which attains nearly the bene¯ts of the full °exibility model. i.e., E[z¤(F)] · E[z¤(A£ B)] + n"¹, for any " > 0, and for all suitably large n. In this lemma, z¤(F) and z¤(A £ B), respectively, denote the excess °ow of a partial °exible structure F and full °exible structure A£B. We can see clearly, there exists partial °exible structure, which can get the most advantage of full °exibility structure. 4.4.1 Graph Expander in the Shrinking Capacity Case We extend Chou et al.'s (2007) work to the shrinking capacity case. The following analysis for the shrinking capacity case parallels with the analysis of Chou et al. (2007). We consider that there are n supply and n demand nodes in the °exibility problem. All demand nodes have demand Dj ; j 2 f1; 2; ¢ ¢ ¢ ; ng, with mean ¹, whereas all supply nodes have supply qi; i 2 f1; 2; ¢ ¢ ¢ ; ng. We use the results of Chou et al. (2007) to derive a few important insights for the process °exibility problem in the shrinking capacity case. 24 Theorem 4.1 In the nn shrinking capacity °exibility structure with shrinking factor kij , when supply i produces product j, if (i) qi = ¹ for all i, (ii) P(Dj > ´k¹) = 0 for all j and (iii) E(Dj) = ¹ for all j, then there is a partial °exible structure F, with jFj · n¢, which attains nearly the bene¯ts of the full °exibility model. i.e., E[S(G)] · E[S(A £ B)] + n"¹, for any " > 0, and for all suitably large n, where " = 1 ¡ ®´k, k = min(i;j)2F kij . Proof. In this proof, we apply the method of Chou et al. (2007) and extend their method to the shrinking capacity case. From (3.2), under the full °exibility (no shrinking capacity) model, we expect the shortage to be E " Xn j=1 Dj ¡ Xn i=1 qi #+ : For a partial °exibility model, let P(M) denote the set of demand nodes M is linked to. From (3.2), the average shortage is less than or equal to E 2 4max MµF 2 4 X j2M Dj ¡ X i2P(M) kqi 3 5 3 5 + ; where k = min kij . Let D¤ j = 8>< >: Dj ; if Pn i=1 Dj · n¹, Dj µ Pn¹ n i=1 Dj ¶ ; if Pn i=1 Dj > n¹. It is easy to see Pn i=1 Dj = Pn i=1 D¤ j , given Pn i=1 Dj · n¹. Then for each subset M, we have X j2M Dj ¡ X i2P(M) kqi = " X j2M Dj ¡ X j2M D¤ j # + 2 4 X j2M D¤ j ¡ X i2P(M) kqi 3 5 = " X j2M Dj ¡ X j2M D¤ j # I Ã Xn j=1 Dj > n¹ ! + 2 4 X j2M D¤ j ¡ X i2P(M) kqi 3 5; where I(¢) denotes the indicator function. 25 If the process structure corresponds to an expander graph (®; ´; ¢), then by the de¯nition of expander graph, we have X j2M D¤ j ¡ X i2P(M) kqi · X j2M D¤ j ¡ ´jMj¹k; if jMj · ®n; and by the assumption that P(Dj > ´k¹) = 0 for all j, then the following holds almost surely. X j2M D¤ j ¡ X i2P(M) kqi = X j2M Dj ¡ X i2P(M) kqi · 0; if jMj · ®n: Since P(M) must contain at least ´ min(jMj; ®n) supply nodes, then we have X j2M D¤ j ¡ X i2P(M) kqi · X j2M D¤ j ¡ ´®n¹k · (1 ¡ ®´k)n¹; if jMj ¸ ®n: Thus X j2M Dj ¡ X i2P(M) kqi · " X j2M Dj ¡ X j2M D¤ j # I Ã Xn j=1 Dj > n¹ ! + [(1 ¡ ®´k)n¹] : Therefore E(S(G)) · E " max MµF "Ã X j2M Dj ¡ X j2M D¤ j ! I Ã Xn j=1 Dj > n¹ ! + (1 ¡ ®´k)n¹ ##+ = E " max MµF "Ã X j2M Dj ¡ X j2M Dj Ã Pn¹ n j=1 Dj !! I Ã Xn j=1 Dj > n¹ ! + (1 ¡ ®´k)n¹ ##+ = E " Xn j=1 Dj ¡ n¹ #+ + (1 ¡ ®´k)n¹: It is clear that 1 ¡ ®´k < 1, then set " = 1 ¡ ®´k, which is a positive number. Then we get E[S(G)] · E[S(A £ B)] + n"¹ as claimed. Theorem 4.1 shows that there exists partial °exibility structure that can still attain the most of the bene¯t of full °exibility structure even with the shrinking in the capacity. Next, we will introduce the methodology for the graph expander index construction in the shrinking capacity case. 26 For a bipartite graph G = (A S B; F), the incidence matrix T is de¯ned in the following way: each column of T, Tl, characterizes an edge l 2 F, where edge l connects node i 2 A to j 2 B, by letting Tli = ¡1, Tlj = 1 and Tlk = 0, 8 k 6= i; j. The Laplacian matrix L = TT0 is a positive semide¯nite matrix. The connectivity of the graph G can be measured by the second smallest eigenvalue ¸2(L) of L, also known as the algebraic connectivity of G. For the shrinking capacity case, we consider it is a weighted graph and de¯ne the incidence matrix as the following way: Each column of T, say Tl, characterizes an edge l 2 F, where edge l connects node i 2 A to j 2 B, by letting Tli = kij , Tlj = ¡kij and Tlk = 0, 8 k 6= i; j (Merris (1994), Wallis (2000)). The relationship between ¸2(L) and the connectivity property of G is wellknown in graph theory ¯eld (Fiedler (1973), Ghosh and Boyd (2006)). Especially, Chou et al. (2007) proposed that ¸2(L) can be used as an index to rank process °exibility structures. In general, a graph with more links is more °exible, and connected graphs are generally more °exible than disconnected graphs. In the subsequent numerical study, we consider ¸2(G) of the weighted graph as the indicator of structure G. 4.5 Numerical Analysis In this section, we report the results of the computational study that we performed based on the shrinking SF matrix and graph expander. Our experiment consists two parts: one is about the chaining structure, and the other is about the general struc ture. To evaluate the e®ectiveness of various indices, we use E[S(G)], the expected shortage of structure G, as the indicator of how °exible structure G is. 4.5.1 Chaining Structure In this section, our numerical study tests a 44 manufacturing structure as shown in Figure 4.2. The arcs emanating from the source node s have capacities (q1; q2; q3; q4), 27 and the arcs, which end in the sink node t have capacities (d1; d2; d3; d4). The °ow in arcs between the plant i node and demand node j is xij . The shrinking factor between supply node i and demand node j is kij . In the simulations of this section, each demand is uniform distribution in the interval [0; 8); the capacity of each plant is 5. We use XpressIVE version 1.17.12 to implement the optimization problem, and create the random demand by function random. First, we test the SF indices in the chaining structure. Following our construction method, the shrinking SF matrix is M = (Mij)4£4: M = 2 66666664 1 + k12k23k34k41 k12 + k41k23k34 k12k23 + k41k34 k12k23k34 + k41 k12 + k23k34k41 1 + k23k34k41k12 k23 + k12k41k34 k23k34 + k12k41 k23k12 + k34k41 k23 + k34k41k12 1 + k23k12k41k34 k34 + k23k12k41 k41 + k33k23k12 k34k23 + k41k12 k34 + k41k12k23 1 + k41k12k23k34 3 77777775 : We have eight di®erent shrinking structures, and the mean value and dominant real eigenvalue of each structure is shown in Table 4.1. In Table 4.1, as for the mean values: structure 1 equals to structure 5, structure 2 equals to structure 6, structure 3 equals to structure 7, structure 4 equals to structure 8. Our numerical study consists of 100 cases generated by varying the demands. For each scenario, we calculate the minimal shortage facing the sampling demand. Hence we can get a average shortage for each structure after running 100 scenarios. The results are shown in Figure 4.3. In this graph, the horizontal axis represents the av erage shortage, and the vertical axis represents the mean value or biggest eigenvalue of SF matrix. The numbers beside nodes are structure numbers. We can see that: as the average shortage becomes smaller, the mean value becomes bigger. The same occurs for the biggest eigenvalue. The detail simulation results are attached in Ap pendix A. Simulation results provide evidence that SF index is useful in predicting the performance rank of manufacturing °exibility in shrinking capacity case. 28 3 6 2 1 8 4 5 7 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 80 90 100 110 120 130 140 150 160 170 180 190 Average Shortage Mean Value and Biggest Eigenvalue Mean Value Biggest Eigenvalue Figure 4.3: SF Matrix Index (the number beside each node is the structure it is associated with) 29 Structure 1 2 3 4 5 6 7 8 k12 0.5 0.5 0.3 0.3 0.4 0.65 0.4 0.47 k23 0.5 0.6 0.3 0.7 0.4 0.65 0.4 0.47 k34 0.5 0.7 0.3 0.3 0.6 0.65 0.2 0.47 k41 0.5 0.8 0.3 0.7 0.6 0.65 0.2 0.47 Mean Value 0.703 0.960 0.461 0.664 0.703 0.960 0.461 0.664 Biggest Eigenvalue 2.813 3.843 1.842 2.653 2.818 3.841 1.859 2.654 Table 4.1: Shrinking Capacity Case Next, we test the performance of expander index in the chaining structure. Based on our construction method, the incidence matrix of manufacturing °exibility struc ture shown in Figure 4.2 is the following T = 2 6666666666666666666664 ¡1 ¡k12 0 0 0 0 0 0 0 0 ¡1 ¡k23 0 0 0 0 0 0 0 0 ¡1 ¡k34 0 0 0 0 0 0 0 0 ¡1 ¡k41 1 0 0 0 0 0 0 k41 0 k12 1 0 0 0 0 0 0 0 0 k23 1 0 0 0 0 0 0 0 0 k34 1 0 3 7777777777777777777775 : We compute the second smallest eigenvalue of Laplacian matrix of weighted graph, which is L = TT0. The results are shown in Table 4.2. We plot the results shown in Table 4.2 in Figure 4.4. In this graph, the horizontal axis represents the average shortage, and the vertical axis represents the second smallest eigenvalue of Laplacian matrix. The numbers beside nodes are structure numbers. We can see that the main trend is: as the shortage becomes bigger, the second smallest eigenvalue becomes 30 smaller. Simulation results provide evidence that expander index is useful in pre dicting the performance rank of manufacturing °exibility in shrinking capacity case. Structures 1 2 3 4 5 6 7 8 k12 0.5 0.5 0.3 0.3 0.4 0.65 0.4 0.47 k23 0.5 0.6 0.3 0.5 0.4 0.65 0.4 0.47 k34 0.5 0.7 0.3 0.3 0.6 0.65 0.2 0.47 k41 0.5 0.8 0.3 0.5 0.6 0.65 0.2 0.47 ¸2(G) 0.219 0.279 0.086 0.086 0.181 0.337 0.05 0.197 Table 4.2: Shrinking Capacity Case 6 2 1 8 5 4 7 3 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 80 100 120 140 160 180 200 Average Shortage Second Smallest Eigenvalue Figure 4.4: Graph Expander Index(the number beside each node is the structure it is associated with) However, there are small oscillations of expander index curve, such as Structure 5, 8 and Structure 7, 3. This phenomenon probably is caused by the nature of expander index, which is a bound for the connectivity property of graph, not the exact value of graph connectivity. We can see similar result for the nonchaining structure. 31 4.5.2 General Structures In this section, we will analyze the nonchaining structure, and use our indices to the shrinking capacity case. We use a set of numerical examples from Iravani et al. (2005) to test the performance of expander index and the SF index. Consid ering the set of structures facing uniform demand in the interval [0; 8), ¯xed ca pacities q = (5; 5; 5; 5; 5; 5; 5; 5), and the same shrinking factor kij = 0:5; 8 i; j 2 f1; 2; 3; 4; 5; 6; 7; 8g as shown in Figure 4.5. We use XpressIVE version 1.17.12 to implement the optimization problem. Structures 1 2 3 4 5 6 7 8 9 ¸2(G) 0.06 0.05 0.07 0.25 0.09 0.08 0.59 0.25 0.52 Mean Value 0.37 0.37 0.59 0.76 0.74 0.78 1.11 1.12 1.42 Biggest Eigenvalue 2.9883 3.29 5.56 6.11 6.33 6.33 8.86 9.29 11.5 E(S(G)) 187.096 571.145 323.468 112.827 110.464 107.289 87.229 86.468 79.674 Table 4.3: SF Structures The performance of various indices are as shown in Table 4.3. We plot the results shown in Table 4.3 in Figure 4.6. The numbers beside nodes are structure numbers. From the Figure 4.6, we can see that biggest eigenvalue of SF matrix ranks the structures almost in line with the order obtained from the sampling estimation: as the shortage increase, the index decreases. But the biggest eigenvalue has a signi¯cant decrease at Structure 1 (Figure 4.5) as shown in Figure 4.6. Iravani et al. (2005) mentioned that the biggest eigenvalues can be considered as an indication of the magnitude of elements of a matrix. As any element of the SF matrix increases (i.e., more °exibility), the biggest eigenvalue of the matrix increases. Because Structure 1 is a chaining structure which has less arcs compared to other structures with similar performance. So dominant eigenvalue has a 32 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 11 12 13 14 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 A B C 4 D 5 6 7 8 E F G H 1 2 3 4 5 6 7 8 A B C D E F G H 1 2 3 4 5 6 7 8 A B C D E F G H 1 2 3 4 5 6 7 8 A B C D E F G H 15 16 17 18 19 Figure 4.5: SF Structures 33 big decrease at Structure 1. Another potential reason for this phenomenon is that in structures 2 and 3, there are very few arcs for specialized production (Structure 2 has 3 arcs, and Structure 3 has 6 arcs), and this makes E[S(G)] of these two structures very high when e±ciency loss exits in cross production. While, for other seven structures, each product has dedicated plant. Therefore, it is not fair to compare structures 2 and 3 to other structures directly. On the other hand, the mean value index ranks the structures in a similar order. This implies SF matrix does not perform good to compare chaining and nonchaining structure. 5 2 3 1 6 4 7 8 9 0 2 4 6 8 10 12 50 150 250 350 450 550 Indices Expander Biggest Eigenvalue of SF Matrix Mean Value of SF matrix Figure 4.6: Indices for SF Structures (the number beside each node is the structure it is associated with) We can see that expander index ranks the structures almost in line with the order obtained from the sampling estimation: as the shortage increases, the expander index decreases. Especially, expander index perform well to compare chain and nonchain structure well. However, there are small oscillations in the expander index curve, such as Structure 7, 8 and 9. As mentioned before, this phenomenon probably is caused by the nature of expander index, which is a bound for the connectivity property of 34 graph, not the exact value of graph connectivity. However, we noticed that the performance di®erence among some di®erent struc tures is quite small, it is possible that the slight di®erence in ordering actually arises from the small number of sampling. The results, however, suggest that the concept of graph expander and SF matrix can be used as the index to rank process °exibility structures in the shrinking capacity case. 35 CHAPTER 5 Additional Cost Case 5.1 Introduction In this chapter, we study the manufacturing °exibility index in the additional cost case. We model the additional cost in linear programming, and develop a general formula to express the pro¯t of the additional cost case. We build up the modi¯ed SF(Structure Flexibility) matrix and Laplacian matrix in the additional cost case, and examine the SF indices and expander indices in di®erent manufacturing structures. We ¯rst test the chaining structure. Then we test the performance of SF indices and expander indices in the general structure (nonchaining structure). 5.2 Model in Additional Cost Case In this section, we ¯rst model the additional cost case in linear programming, then give a general formula to express the optimal solutions of the additional cost case. For simplicity, we use the same notations as shown in Chapter 4, and also consider the nm manufacturing °exibility structure in this section. The objective is to maximize the total pro¯t when the suppliers face the demands. Due to additional production processes or additional training for workers, an extra cost may be incurred if one type of product is produced in a plant that is not speci¯ed. We use cij to denote the additional cost for each unit of product j produced at plant i, hence cij = 0, if i = j, and cij > 0, if i 6= j. In addition, pj denotes the price of product j. We assume that cij < pj , 8 i 2 f1; 2; ¢ ¢ ¢ ; ng, 8 j 2 f1; 2; ¢ ¢ ¢ ;mg. The 36 maximal pro¯t of n¡m structures in additional cost case can be acquired by solving the following linear program: max Xm j=1 pj Xn i=1 xij ¡ Xn i=1 Xm j=1 cijxij (5.1) s:t: X (i;j)2F xij · qi 8 i = 1; 2; ¢ ¢ ¢ n; X (i;j)2F xij · dj 8 j = 1; 2; ¢ ¢ ¢ m: We get a general formula (5.2) for the optimal solution of the above problem in the following theorem. Theorem 5.1 The maximal pro¯t of °exibility nm structure with additional cost is: min ¹j ( X j dj¹j + X i qi max j fpj ¡ cij ¡ ¹jg ) ; ¹j ¸ 0; i = f1; ¢ ¢ ¢ ; ng; j = f1; ¢ ¢ ¢ ;mg (5.2) Proof. The problem (5.1) is same to the following: max Xn i=1 Xm j=1 (pj ¡ cij)xij (5.3) s:t: X (i;j)2F xij · qi 8 i = 1; 2; ¢ ¢ ¢ n; X (i;j)2F xij · dj 8 j = 1; 2; ¢ ¢ ¢ m: The dual of the linear program has the following form: min : d1¹1 + ¢ ¢ ¢ + dm¹m + q1v1 + ¢ ¢ ¢ + qnvn (5.4) s:t: ¹j + ºi ¸ pj ¡ cij 8(i; j) 2 F ¹j ; ºi ¸ 0 8 j = 1; 2; ¢ ¢ ¢ m; i = 1; 2; ¢ ¢ ¢ ; n: We observe that the optimal solutions should satisfy the following condition: in a optimal solution to (5:4), we can have ºi's as follows: ºi = max j fpj ¡ cij ¡ ¹jg (5.5) 37 provided that cj ¸ 0. That is, for a given speci¯cation of f¹1; ¢ ¢ ¢ ; ¹mg, we set ºi as small as possible. The case when cj < 0 is not meaningful, since it implies negative capacity. Since the optimal objective value to (5.4) equals the optimal objective value for (5.1), then we can get the solution of problem (5.1) has the form as (5.2). As for this study, we use the above theorem to analyze the structure index in the chaining structure. 5.3 SF Matrix of Additional Cost Case In this section, we set up SF matrix in the additional cost case, and introduce an algorithm for the construction of SF matrix in this special case. For simplicity, we focus on the nn additional cost case to show how to build the SF matrix. In this section, we assume that the capacity of each supply node is 1. Recall that Iravani et al. (2005) created the SF matrix in the following way: (1) for nondiagonal element: \the total number of nonoverlapping paths a system can use to respond to a particular change in demand," which can be obtained by solving the maximal °ow problem. (2) for diagonal element: the number of arcs connected to the corresponding supply node. We set the element of the SF matrix as the maximal pro¯t from each supply node to each demand node. Our method extends the work of Iravani et al. (2005) in the following way: (1) we set the nondiagonal element as the total pro¯t for one unit of product from supply node i to demand node j; (2)we set the diagonal element to be the total pro¯t for one unit of product from supply node i to demand node i. For example, as shown in Figure 5.1, the diagonal element M11 = 1 £ [p1 + (p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41)] = 2p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41, and the nondiagonal element M12 = 1 £ [p2 + (p2 ¡ c12 ¡ c41 ¡ c34 ¡ c23)] = 2p2 ¡ c12 ¡ c41 ¡ c34 ¡ c23. To get the elements of SF matrix, Iravani et al. (2005) used a maximal °ow 38 1 2 3 4 1 2 3 4 Plant Demand c11=0 c12 c23 c22=0 C33 =0 c34 c44=0 c41 s t q1 q2 q3 q4 P1/d1 P2/d2 P3/d3 P4/d4 Figure 5.1: 44 Manufacturing Flexibility Structure in Additional Cost Case. formulation to ¯nd the maximum number of units of source e®ort that can be shipped from a demand start node, i, to a demand sink node, j, in a particular structure. Unfortunately, their methodology cannot be used directly to the additional cost case, because of the addition of additional cost associated with each arc in the path. For example, if there exists a route R1 = 1¡2¡2¡3 from the source node 1 to demand node 3, as shown in Figure 5.1. The maximal pro¯t of this route can be solved as p3 ¡ c12 ¡ c23, not p3 ¡ max(c12; c23). With the increasing of °exibility in the manufacturing structure, it is not easy to solve the maximal pro¯t between supply node and demand node. In the chaining structure, there are only two paths from each supply node to demand node. But for nonchaining structure, it is not easy to get the maximal pro¯t between two nodes. This motivates for our algorithm in the next section. 39 5.3.1 Algorithm for SF Matrix Construction in Additional Cost Case The above maximal °ow problem can be transferred to the shortest path problem. We want to get the route r 2 R from source node s to demand node t, so that (pt ¡ P (i;j)2r cij) of the route be the maximal value in all routes R from s to t. That is, we want to get the route r, so that P (i;j)2r cij of the route be the minimal value in all routes R. Let cij represent the distance from node i to node j. The maximal pro¯t from node s to t is transformed to solve the distance from s to t. For example, the maximal °ow of route R1, as we mentioned in the last section, can be acquired by p3 ¡ d13, where d13 = c12 + c23 + c22 = c12 + c23. For our methodology, we use the maximal pro¯t, from a supply node, s, to a demand node, t, to present the element mst of SF matrix. The algorithm, which gets the element mst of SF matrix, is as follows: Step 1: To input incidence matrix T of the structure, s and t; initialize i = 1. Step 2: To calculate the shortest path ri and the distance di from s to t, which equals the summation of additional cost of arcs that this path passes. Step 3: Delete the arcs that ri passes, and check if the node s is connected to t. If they are disconnected, go to Step 4; if there are still routes from node s to t, then update the incidence matrix T, set i = i + 1, and go to Step 2. Step 4: Calculate P i(pt ¡di), which is mst, where pt denotes the price of product t. 5.4 Graph Expander in Additional Cost Case As mentioned before, SF matrix indices lack the mathematical support. At the same time, graph expander theory can help us get another structure index, which has more mathematical supports than SF matrix. This motivates for the graph expander index in this section. In this section, we extend the results of Chou et al. (2007) to the additional cost case. In addition, we propose a method to construct expander index in the additional 40 cost case. Similar with the shrinking capacity case, for the additional capacity case, we consider that the °exibility structure is a weighted graph, and de¯ne the additional cost incidence matrix, similar to the weighted incidence matrix, in the following way: each column of T, say Tl, characterizes an edge l 2 F, where edge l connects node i 2 A to j 2 B, by letting Tli = cij=pj ¡ 1, Tlj = (1 ¡ cij=pj) and Tlk = 0, 8 k 6= i; j. In this de¯nition, we use pj¡cij pj = (1 ¡ cij=pj), the ratio between the net pro¯t of shipping one unit of supply i to product j and the product price j, to represent the weight of the arc from supply node i to the demand node j. We de¯ne L = TT0, a positive semide¯nite matrix, motivated by Laplacian ma trix. In the subsequent numerical analysis, we consider ¸2(L), the second smallest eigenvalue of L, as the indicator. 5.5 Numerical Analysis In this section, we report the results of the computational study that we performed based on the additional cost SF matrix. Our experiment is consisted of two parts: one is about the chaining structure, and the other is about the general structure. To evaluate the e®ectiveness of various indices, we estimate the expected pro¯t of structure G, as the indicator of how °exible structure G is. 5.5.1 Chaining Structure In this section, we use, as an example, a 44 manufacturing structure shown in Figure 5.1 to test the structure indices. The arcs emanating from the source node s have capacities (q1; q2; q3; q4), and the arcs, which end in the sink node t have capacities (d1; d2; d3; d4). The °ows and additional costs in the arcs between plant node i and demand node j are xij and cij . The price of product j is pj . In the simulations of this section, each demand is uniform distribution on the 41 interval [0; 8); the capacity of each plant is 5. We use XpressIVE version 1.17.12 to implement the optimization problem and function random to generate the demand. First, we test the SF indices in the chaining structure. Following our construction method, the additional cost SF matrix isM = (Mij)4£4 = 2B¡(c12+c23+c34+c41)A = 2 6664 2p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41 2p2 ¡ c12 ¡ c41 ¡ c34 ¡ c23 2p3 ¡ c21 ¡ c32 ¡ c41 ¡ c34 2p4 ¡ c12 ¡ c23 ¡ c34 ¡ c41 2p1 ¡ c12 ¡ c23 ¡ c34 ¡ c41 2p2 ¡ c23 ¡ c34 ¡ c41 ¡ c12 2p3 ¡ c23 ¡ c12 ¡ c41 ¡ c34 2p4 ¡ c23 ¡ c34 ¡ c12 ¡ c41 2p1 ¡ c23 ¡ c12 ¡ c34 ¡ c41 2p2 ¡ c23 ¡ c34 ¡ c41 ¡ c12 2p3 ¡ c23 ¡ c12 ¡ c41 ¡ c34 2p4 ¡ c34 ¡ c23 ¡ c12 ¡ c41 2p1 ¡ c41 ¡ c33 ¡ c23 ¡ c12 2p2 ¡ c34 ¡ c23 ¡ c41 ¡ c12 2p3 ¡ c34 ¡ c41 ¡ c12 ¡ c23 2p4 ¡ c41 ¡ c12 ¡ c23 ¡ c34 3 7775 where B = 2 66666664 p1 p2 p3 p4 p1 p2 p3 p4 p1 p2 p3 p4 p1 p2 p3 p4 3 77777775 ; and A is the matrix with all elements equal to 1. If two di®erent 44 manufacturing °exibility structures have the same c12 + c23 + c34 + c41, and the prices of all products of each structure are identical, then SF matrix of each structure is same. The SF matrix of structure shown in Figure 5.1 is M = (2p ¡ c12 ¡ c23 ¡ c34 ¡ c41)A, given p1 = p2 = p3 = p4 = p. We can get the insights from Theorem 5.1. The maximal pro¯t of additional cost case has the form X j dj¹j + X i qi max j fpj ¡ cij ¡ ¹jg: For simplicity, we set qi = q and pj = p for i; j 2 f1; 2; ¢ ¢ ¢ ; ng, and consider the following: X i qi max j fpj ¡ cij ¡ ¹jg = q X i max j fp ¡ cij ¡ ¹jg = q X i (p ¡ ¹j¤ ¡ cij¤) = qnp ¡ X i (¹j¤ ¡ cij¤) = qnp ¡ n¹j¤ + X i cij¤ ; where p ¡ ¹j¤ ¡ cij¤ = maxjfp ¡ cij ¡ ¹jg. Besides ¹j , P i cij¤ is a major factor to the value of maximal pro¯t ³P j dj¹j + P i qi maxj fpj ¡ cij ¡ ¹jg ´ , because the 42 two di®erent structures has the same qnp, n¹j¤ and P j dj¹j . That means, in the numerical study, If two di®erent 44 manufacturing °exibility structures have the same c12+c23+c34+c41, and the prices of all products of each structure are identical, then the maximal pro¯t of each structure should be same. Structures 1 2 3 4 5 6 7 8 c12 0.1 0.1 0.1 0.3 0.1 0.1 0.1 0.3 c23 0.1 0.2 0.1 0.5 0.1 0.2 0.1 0.5 c34 0.1 0.3 0.3 0.3 0.1 0.3 0.3 0.3 c41 0.1 0.4 0.2 0.5 0.1 0.4 0.2 0.5 p1 1 1 1 1 1.1 1.1 1.1 1.1 p2 1 1 1 1 1.1 1.1 1.1 1.1 p3 1 1 1 1 1.1 1.1 1.1 1.1 p4 1 1 1 1 1.1 1.1 1.1 1.1 Mean Value 1.6 1 1.3 0.4 1.8 1.2 1.5 0.6 Biggest Eigenvalue 6.4 4 4.2 1.6 7.2 4.8 6 2.4 Table 5.1: Additional Cost Case In this numerical study, we have eight di®erent additional cost structures, and the mean value and dominant real eigenvalue of each structure is shown in Table 5.1. We set up the model and ran 100 scenarios to analyze the maximal pro¯t of each scenario. Hence we can get a average shortage for each structure after running 100 scenarios. The results are shown in Figure 5.2. In this graph, the horizontal axis represents pro¯t, and the vertical axis represents mean value of SF matrix. We can see that: the mean value of SF matrix becomes greater, as the pro¯t becomes larger, given the prices are same. The detailed simulation results are attached in Appendix B. 43 0 1 2 3 4 5 6 7 8 1450 1500 1550 1600 1650 1700 1750 Prof it Mean Value Price = 1.1 Price = 1 Figure 5.2: SF Matrix Indices for Additional Cost Case From Figure 5.2, we can see that price can greatly a®ect the index. For simplicity, we set all the prices at the same value (price = 1) and use the structures shown in Table 5.2. We ran another 100 scenarios and show the results in Figure 5.3. The numbers beside nodes are structure numbers. In this graph, we can see the mean values increases as the pro¯t increases. If the mean values of di®erent structures are the same (0:4), pro¯ts are similar. The detailed simulation results are attached in Appendix C. The above two simulation results provide evidences that SF index is useful in predicting the performance rank of manufacturing °exibility in the additional cost case. Next, we test the performance of expander index in the chaining structure. The 44 Structures 1 2 3 4 5 6 7 8 c12 0.1 0.1 0.1 0.3 0.4 0.1 0.3 0.4 c23 0.1 0.2 0.1 0.5 0.1 0.7 0.1 0.5 c34 0.1 0.3 0.3 0.3 0.5 0.6 0.3 0.6 c41 0.1 0.4 0.2 0.5 0.1 0.2 0.7 0.7 Mean Value 1.6 1 1.3 0.4 0.9 0.4 0.6 0.2 Biggest Eigenvalue 6.4 4 4.2 1.6 3.6 1.6 2.4 0.8 ¸2(G) 0.5231 0.3606 0.4393 0.2192 0.2549 0.1463 0.1982 0.1283 Table 5.2: Additional Cost Case 6 1 3 2 7 4 8 5 0.5 0 0.5 1 1.5 2 1320 1340 1360 1380 1400 1420 1440 Average Prof it Mean Value Figure 5.3: SF Matrix Indices for Additional Cost Case (the number beside each node is the structure it is associated with) 45 modi¯ed additional cost incidence matrix is the following: T = 2 6666666666666666666664 ¡1 c12 p2 ¡ 1 0 0 0 0 0 0 0 0 ¡1 c23 p3 ¡ 1 0 0 0 0 0 0 0 0 ¡1 c34 p4 ¡ 1 0 0 0 0 0 0 0 0 ¡1 c41 p1 ¡ 1 1 0 0 0 0 0 0 1 ¡ c41 p1 0 1 ¡ c12 p2 1 0 0 0 0 0 0 0 0 1 ¡ c23 p3 1 0 0 0 0 0 0 0 0 1 ¡ c34 p4 1 0 3 7777777777777777777775 : We compute the second smallest eigenvalue of L = TT0. The results are shown in Table 5.2. We plot the results shown in Table 5.2 in Figure 5.4. In this graph, the horizontal axis represents the pro¯t and the vertical axis represents the second smallest eigenvalue of L. The numbers beside nodes are structure numbers. We can see that the main trend is: as the pro¯t becomes higher, the second smallest eigenvalue of L becomes higher. Simulation results provide evidence that expander index is useful in predicting the performance rank of structure °exibility in the additional cost case. 1 3 2 5 6 7 4 8 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 1320 1340 1360 1380 1400 1420 1440 Profit Expander Index Figure 5.4: Graph Expander Index (the number beside each node is the structure it is associated with) However, there are small oscillations of expander index line, such as Structure 4, 46 6 and Structure 7. As mentioned before, this phenomenon probably is caused by the nature of expander index, which is a bound for the connectivity property of graph, not the exact value of graph connectivity. We can see similar result for the nonchaining structure. 5.5.2 General Structure In this section, we will analyze the general structure and use our indices to the additional cost case. We use a set of numerical examples from Iravani et al. (2005), shown in Figure 4.5, to test the performance of the expander index and the SF index. We analyze the set of structures facing random uniform distribution demand in the interval [0; 8), ¯xed capacity q = (5; 5; 5; 5; 5; 5; 5; 5), the additional cost cij = 0:1, 8 i; j 2 f1; 2; ¢ ¢ ¢ ; 8g and pj = 1, 8 j = f1; 2 ¢ ¢ ¢ ; 8g. We use XpressIVE version 1.17.12 to implement the optimization problem and random function to generate the demand. To evaluate the e®ectiveness of various indices, we estimate the expected pro¯t of the structure G, by sampling 100 scenarios, and use this estimate as the indicator of how °exible structure G is. The performance of various indices are as shown in Table 5.3. Structures 1 2 3 4 5 6 7 8 9 Mean Value 1.2 1.334 1.755 2.283 2.045 2.205 3.152 2.981 3.786 Biggest Eigenvalue 64.32 53.20 62.04 61.69 56.02 70.04 56.95 68.45 62.606 ¸2(G) 0.1362 0.1631 0.1892 0.5258 0.2607 0.2236 1.2336 0.7845 1.5025 Pro¯t 3063.05 2961.81 3034.65 3098.33 3098.10 3100.09 3107.24 3107.57 3109.544 Table 5.3: SF Structures We plot the results shown in Table 5.3 in Figure 5.5 and 5.6. The numbers beside nodes are structure numbers. From these two ¯gures, we can see that SF index 47 2 3 1 5 4 6 8 7 9 8 13 18 23 28 33 2960 2980 3000 3020 3040 3060 3080 3100 3120 Profit Biggest Eigenvalue 2 3 1 6 5 4 8 7 9 1 1.5 2 2.5 3 3.5 4 2960 2980 3000 3020 3040 3060 3080 3100 Profit Mean Value of SF Matrix Figure 5.5: SF Indices, Up: Biggest Eigenvalue Index; Down: Mean Value Index (the number beside each node is the structure it is associated with). 2 3 1 9 7 8 4 6 5 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 2960 2980 3000 3020 3040 3060 3080 3100 Profit Expander Index Figure 5.6: Expander Indices for SF Structures (the number beside each node is the structure it is associated with) 48 and expander index rank the structures almost in line with the order obtained from the sampling estimation: as the pro¯t increases, the SF index and expander index increase. Simulation results provide evidence that SF index and expander index are useful in predicting the performance rank of manufacturing °exibility in the additional cost case. However, the biggest eigenvalue has a signi¯cant decrease at Structure 1 (Figure 4.5) as shown in Figure 5.5. Iravani et al. (2005) mentioned that the biggest eigenval ues can be considered as an indication of the magnitude of elements of a matrix. As any element of the SF matrix increases (i.e., more °exibility), the biggest eigenvalue of the matrix increases. Because Structure 1 is a chaining structure which has less arcs compared to other structures with similar performance. So dominant eigenvalue has a big decrease at Structure 1. Another potential reason for this phenomenon is that in structures 2 and 3, there are very few arcs for specialized production (Struc ture 2 has 3 arcs, and Structure 3 has 6 arcs), and this makes expected pro¯t of these two structures very low when e±ciency loss exits in cross production. While, for other seven structures, each product has dedicated plant. Therefore, it is not fair to compare structures 2 and 3 to other structures directly. On the other hand, the mean value index ranks the structures in a similar order. This implies SF matrix does not perform good to compare chaining and nonchaining structure. From Figure 5.6, we can see that expander index has small oscillations, such as Structure 7, 8 and 9, in the expander index line. This probably is caused by the nature of expander index, which is a bound for the connectivity property of graph, not the exact value of graph connectivity. However, we notice that the performance di®erence among some di®erent struc tures is quite small, it is possible that the slight di®erence in ordering actually arises from the small number of sampling. The results, however, suggest that the concept of SF matrix and Laplacian matrix can be used as the index to rank process °exibility 49 structures in the additional cost case. 50 CHAPTER 6 Conclusion Our main contribution of this study is that we model e±ciency loss occurred in manufacturing °exibility. We focus on the shrinking capacity and additional cost cases, the two main sources for e±ciency loss. We develop new indices, for the shrinking capacity and additional cost cases, which are simple and traceable numbers, and can rank the structure performance. First, we include the shrinking capacity and the additional cost into the current classical maximal °ow models, and build up the shrinking capacity case and additional cost case in linear programming. We characterize the optimal solutions, and present e±cient methods to solve the above two problems. Second, we provide an approach to extend SF matrix to the shrinking capacity and additional cost case. Based on this method, we can develop a simple performance index for the both cases. Indeed, this approach can also be applied in general nm system. Extensive numerical studies show that our method can get useful index for the structure performance. Third, we analyze the shrinking capacity and additional cost cases using graph expander theory, which is a direct extension of Chou et al. (2007). We evaluate the manufacturing °exibility structure in the shrinking capacity and additional cost cases as the weighted graph. Extensive numerical studies show that our index is simple and useful for the structure performance. The structure indices capture important information about a structure, and how well it can respond to demand variability. Our experiments suggest that SF indices 51 and expander indices are purely deterministic metrics, and quite robust, because they work no matter the demand realization. They are powerful in predicting system performance ranking at demand variation. In reality, the concept of SF index and graph expander index can be used to help managers to design good manufacturing °exibility structure, and does not require intensive simulation. Finally, we discuss some future research directions. (1) Combination of shrinking capacity and additional cost. This work raises an important future direction, the combination of shrinking capacity and ad ditional cost. So far, we consider individually the cases of shrinking capacity and additional cost. In reality, they often occur in the manufacturing °exibility at the same time. Another important issue is to develop useful index for the manufacturing °exibility structure in this combination case. (2) E±ciency loss in correlated demand situation. In this thesis, we assume that the demand of di®erent plant is independent. In reality, the demand of di®er ent plant is often positive correlated or negative correlated. If it happens, the chain structure maybe not bene¯cial as in the independent demand case. In addition, the manufacturers may adjust the capacity allocation between each plant in order to ¯t the correlated demand. Hence, the challenge is to study the in°uence of correlated demand to the manufacturing °exibility in the e±ciency loss manufacturing envi ronment. Another important issue is to build new index for the correlated demand case. 52 BIBLIOGRAPHY [1] Aksin, O. Z., F. Karaesmen. 2007. Characterizing the performance of process °exibility structures. Operations Research Letters 35(4) 477484. [2] Alon, N. 1986. Eigenvalues and expanders. Combinatorica 6(2) 8396. [3] Alon, N., V.D. Milman. 1985. ¸1, isopermitric inequalities for graphs, and su perconcentrators. Journal of Combinatorial Theory Series A 38(1) 7388. [4] Bassalygo, L. A., M. S. Pinsker. 1973. Complexity of an optimum nonblocking switching network without reconnections. Problem Information Transmission 9 8487. [5] Chou, M., C. Teo, H. Zheng. 2007. Process °exibility revisited: graph expander and foodfromtheheart.Working paper, National University of Singapore, Sin gapore. [6] De Meyer, A., J. Nakane, J. G. Miller K. Ferdows. 1989. Flexibility: the next competitive battle. Strategic Management Journal 10(2) 135144. [7] De Toni, A., S. Tonchia. 1998. Manufacturing °exibility: a literature review. International Journal of Production Research 36(6) 15871617. [8] Fiedler, M. 1973. Algebraic connectivity of graphs. Czechoslovak Mathematics Jornal 23 298305. [9] Gerwin, D. 1993. Manufacturing °exibility: a strategic perspective. Manage ment Science 39(4) 395410. 53 [10] Graves, S. C., B. T. Tomlin. 2003. Process °exibility in supply chains. Manage ment Science 49(7) 907919. [11] Gurumurthi, S., S. Benjaafar. 2004. Modeling and analysis of °exible queueing systems. Naval Research Logistics 51(5) 755782. [12] Hopp, W. J., E. Tekin, M. P. Van Oyen. 2004. Bene¯ts of skill chaining in production lines with crosstrained workers. Management Science 50(1) 8398. [13] Iravani, S. M., M. P. Van Oyen, K. T. Sims. 2005. Structural °exibility: a new perspective on the design of manufacturing and service operations. Management Science 51(2) 151166. [14] Iravani, S.M., R. B. Kolfal, M. P. Van Oyen. 2007. Call center labor cross training: It's a small world after all. Management Science 53(7) 11021112. [15] Jordan, W.C., R. P. Inman, D. E. Blumenfeld. 2004. Chained crosstraining of workers for robust performance. IIE Transactions 36(10) 953967. [16] Jordan, W. C., S. C. Graves. 1995. Principles on the bene¯ts of manufacturing process fexibility. Management Science 41(4) 577594. [17] Lien, R., S. M. Iravani, K. Smilowitz, M. Tzur. 2005. E±cient and robust design for transshipment networks. Working paper, Northwestern University, Evanston, IL. [18] Merris R. Laplacian matrics of graphs: a survey. 1994. Linear Algebra and its Applications 197,198 143176. [19] Reingold, O., S. Vadhan, A. Wigderson. 2002. Entropy waves, the zigzag graph product, and new constantdegree expanders and extractors. Ann. of Math 155 157187. 54 [20] Sarnak, P. 2004. What is an expander? Notices of the AMS 51(7) 62763. [21] Sethi, A. K., S. P. Sethi. 1990. Flexibility manufacturing: a survey. Internat. J. Flexible Manufacturing Systems 2 289328. [22] Sheikhzadeh, M., S. Benjaafar, D. Gupta. 1998. Machine sharing in manufac turing systems: °exibility versus chaining. International Journal of Flexible Manufacturing Systems 10(4) 351378. [23] Shi, D., R. L. Daniels. 2003. A survey of manufacturing °exibility: implications for ebusiness. IBM Systems Journal 42(3) 414427. [24] Tanner, M. 1984. Explicit construction of concentrators from generalized N gons. SIAM Journal on Algebraic Discrete Methods 5(3) 287293. [25] Wallis W.D. 2000. A beginners guide to graph theory, BirkhÄauser, Boston, MA. [26] Xiao, D.Y. 2003. The evolution of expander graphs. BA Thesis, Harvard Uni versity, http://www.cs.princeton.edu/dxiao. 55 APPENDIX A Simulation Results in Shrinking Capacity Case Appendix A data goes here Demand Strucuture 1 2 3 4 1 2 3 4 5 6 7 8 1 7.632 1.098 7.35 6.243 4.273 3.883 5.054 3.76 4.664 3.764 4.664 4.38 2 3.436 2.092 6.792 4.407 0 0 0.763 0 0.321 0 0.359 0.005 3 2.644 2.364 3.881 2.46 0 0 0 0 0 0 0 0 4 2.555 4.044 6.142 3.683 0 0 0.599 0 0.241 0 0.325 0.004 5 1.755 7.476 1.441 7.318 1.392 0.784 2.753 2.753 1.342 0.398 2.771 1.577 6 6.976 7.398 4.044 0.125 2.136 1.386 2.874 1.941 1.978 1.588 3.355 2.215 7 2.275 3.082 0.422 6.884 0 0 0.384 0.384 0 0 0.865 0 8 1.894 7.249 2.555 3.291 0 0 1.097 0.804 0.249 0 0.826 0.14 9 1.457 3.069 1.405 3.304 0 0 0 0 0 0 0 0 10 0.353 5.791 3.422 7.616 1.444 0.867 2.088 2.016 1.402 0.673 2.207 1.555 11 7.476 0.125 7.345 7.925 5.355 4.995 6.283 5.081 5.796 4.881 5.796 5.441 12 3.881 0.025 6.734 7.35 1.967 1.464 2.584 1.82 2.189 1.383 2.296 2.052 13 1.457 5.254 6.243 1.398 0.12 0 0.903 0.371 0.545 0 0.66 0.245 14 7.249 7.692 6.792 7.318 9.051 9.051 9.051 9.051 9.051 9.051 9.051 9.051 15 6.407 7.634 4.038 1.89 2.439 1.823 3.021 2.342 2.302 1.984 3.366 2.502 16 3.916 4.622 1.356 2.114 0 0 0 0 0 0 0 0 17 2.46 6.142 1.784 1.755 0 0 0.001 0 0 0 0 0 18 6.243 7.319 7.692 3.645 5.577 5.17 5.848 5.306 5.434 5.379 5.978 5.613 19 0.039 7.476 1.441 7.634 0.853 0.14 2.554 2.554 0.971 0.029 2.4 1.081 20 3.683 1.89 4.501 7.35 1.158 0.417 1.884 1.464 1.167 0.373 1.951 1.279 21 0.081 0.742 0.353 1.529 0 0 0 0 0 0 0 0 22 2.307 1.391 1.405 2.842 0 0 0 0 0 0 0 0 23 3.082 2.275 5.973 4.792 0 0 0 0 0 0 0 0 24 7.249 0.125 3.304 6.884 2.158 1.168 3.185 2.633 2.054 1.443 3.39 2.245 25 7.925 4.27 3.069 1.706 0.704 0 1.743 0.107 0.117 0 2.161 0.859 26 7.856 1.098 7.634 7.632 6.17 5.78 6.951 5.459 6.561 5.6 6.561 6.276 27 3.683 2.092 7.476 6.449 2.141 1.785 2.934 1.612 2.551 1.496 2.551 2.255 28 3.436 2.114 1.875 7.692 0.212 0 1.453 1.192 0 0 1.769 0.404 29 1.89 1.876 2.17 7.398 0 0 1.184 0.898 0 0 1.465 0.034 30 6.378 4.044 2.46 6.792 1.661 1.068 2.322 2.207 1.401 1.217 2.574 1.755 31 5.791 4.706 3.082 1.405 0 0 0 0 0 0 0 0 32 3.304 2.307 0.081 2.842 0 0 0 0 0 0 0 0 33 7.853 0.422 5.973 7.99 5.185 4.602 5.723 5.174 5.324 4.561 5.668 5.28 34 4.253 1.894 0.742 7.616 0.116 0 1.116 1.116 0 0 1.596 0.252 35 4.792 2.275 6.458 1.392 0 0 0.524 0 0 0 0.217 0 36 7.616 5.532 0.522 4.043 1.55 0.203 2.458 1.537 0.928 0.66 2.767 1.694 37 1.529 7.99 4.706 2.65 0.631 0.49 1.73 1.49 0.99 0 1.405 0.793 38 2.769 1.58 3.722 0.353 0 0 0 0 0 0 0 0 56 Demand Strucuture 39 6.458 1.894 7.853 7.985 5.743 5.432 6.364 5.122 6.054 5.289 6.054 5.827 40 0.303 7.465 4.038 3.082 0 0 0.965 0.965 0.465 0 0.465 0.101 41 1.894 2.275 4.038 6.976 0.425 0 1.358 0.919 0.433 0 1.456 0.583 42 2.082 6.884 0.742 0.522 0 0 0.558 0.384 0 0 0.309 0 43 1.777 2.65 5.532 7.925 2.201 1.634 2.786 2.388 2.366 1.418 2.736 2.31 44 2.17 0.353 2.307 0.081 0 0 0 0 0 0 0 0 45 1.405 5.791 0.125 6.921 0 0 0.433 0.421 0 0 0.902 0 46 1.529 3.943 1.706 6.048 0 0 0 0 0 0 0.177 0 47 0.353 6.877 0.081 6.569 0 0 0.576 0.576 0 0 0.584 0 48 2.533 2.739 5.212 7.616 1.848 1.296 2.409 2.049 1.957 1.143 2.394 1.95 49 1.405 3.082 4.043 7.99 1.582 0.759 2.433 2.074 1.598 0.601 2.521 1.729 50 2.307 2.769 6.458 0.742 0 0 0.431 0 0 0 0 0 51 1.777 3.082 2.739 4.253 0 0 0 0 0 0 0 0 52 1.706 3.722 4.043 0.019 0 0 0 0 0 0 0 0 53 6.048 7.465 0.081 7.244 3.405 2.553 4.281 4.281 3.069 2.909 4.754 3.474 54 1.529 3.343 6.458 3.304 0 0 0.603 0 0.076 0 0.184 0 55 4.584 7.99 5.791 1.58 2.718 2.205 3.349 2.938 2.787 2.084 3.336 2.82 56 3.683 4.501 1.398 2.555 0 0 0 0 0 0 0 0 57 1.89 6.378 3.881 6.243 0.639 0.385 1.352 1.352 0.699 0.256 1.148 0.693 58 6.792 5.681 7.692 1.755 3.543 2.971 4.192 3.229 3.304 3.177 4.504 3.631 59 7.345 2.092 1.875 3.291 0.345 0 1.472 0.099 0 0 1.818 0.531 60 5.254 7.318 6.976 1.457 3.535 3.003 4.051 3.626 3.537 2.978 4.106 3.621 61 2.204 4.177 6.963 5.623 1.476 1.254 2.088 1.423 1.81 0.887 1.81 1.572 62 6.673 3.059 7.475 4.988 3.171 2.973 3.562 2.78 3.364 2.886 3.369 3.224 63 1.452 3.503 5.177 7.887 2.157 1.636 2.709 2.402 2.288 1.419 2.685 2.261 64 5.987 2.556 6.428 6.917 3.11 2.877 3.599 2.819 3.355 2.807 3.355 3.177 65 2.715 5.145 4.032 3.748 0 0 0 0 0 0 0 0 66 3.069 3.291 4.792 7.345 1.572 1.076 2.076 1.802 1.618 0.976 2.1 1.66 67 7.398 1.405 5.532 2.082 0.623 0 1.474 0 0.3 0 1.766 0.758 68 1.392 2.65 6.407 3.422 0 0 0.335 0 0 0 0 0 69 0.522 2.275 7.249 1.876 0 0 0.981 0 0.359 0 0.359 0 70 1.391 0.742 1.58 4.706 0 0 0 0 0 0 0 0 71 2.918 2.08 0.848 4.342 0 0 0 0 0 0 0 0 72 7.759 3.082 3.221 1.896 0.522 0 1.616 0 0 0 2.02 0.691 73 6.112 6.048 0.251 1.332 0.354 0 0.932 0.332 0.282 0 1.215 0.456 74 2.809 3.702 0.053 1.006 0 0 0 0 0 0 0 0 75 7.867 6.33 2.533 5.809 3.985 3.463 4.266 4.266 3.783 3.69 4.504 4.028 76 3.291 5.791 4.038 0.522 0 0 0 0 0 0 0 0 77 2.842 0.081 7.99 1.706 0.49 0 1.49 0 0.99 0 0.99 0.626 78 1.777 3.304 0.019 2.769 0 0 0 0 0 0 0 0 79 2.739 1.529 7.787 4.253 0.393 0 1.523 0 0.965 0 1.013 0.562 80 1.057 7.616 6.976 1.392 2.091 2.091 3.091 3.091 2.591 1.578 2.72 2.227 81 1.006 1.296 1.896 4.465 0 0 0 0 0 0 0 0 82 2.809 7.867 5.105 0.848 0.839 0.473 1.942 1.473 1.091 0 1.758 1.009 83 5.335 4.584 6.429 1.57 0.876 0.456 1.242 0.704 0.984 0.375 1.204 0.944 84 6.33 6.53 0.053 3.044 1.088 0.195 1.828 1.207 0.864 0.302 2.256 1.199 85 5.454 2.007 4.826 6.112 0.731 0.24 1.244 0.885 0.736 0.292 1.286 0.815 86 6.877 2.739 5.105 7.985 4.349 3.986 4.69 4.419 4.378 3.986 4.699 4.406 87 0.019 4.584 0.848 3.221 0 0 0 0 0 0 0 0 88 6.133 7.787 2.918 0.303 2.104 1.354 2.677 2.077 2.03 1.432 2.901 2.205 89 5.809 3.943 6.048 7.867 4.196 4.09 4.407 3.985 4.302 4.042 4.302 4.225 90 3.702 7.465 4.043 2.533 1.079 0.56 1.827 1.497 1.208 0.337 1.728 1.198 57 Demand Strucuture 91 5.105 3.082 7.465 0.019 0.909 0.15 1.764 0.412 1.232 0 1.552 1.055 92 2.08 5.809 4.253 0.774 0 0 0 0 0 0 0 0 93 0.053 6.429 2.739 6.133 0 0 0.449 0.443 0 0 0.627 0 94 2.769 1.762 3.343 6.048 0 0 0.199 0 0 0 0.373 0 95 3.702 2.533 7.867 7.99 4.299 3.988 5 3.858 4.663 3.721 4.663 4.401 96 3.142 2.918 4.342 4.584 0 0 0 0 0 0 0 0 97 5.809 7.244 0.303 1.896 1.399 0.649 2.081 1.539 1.357 0.68 2.237 1.509 98 7.867 7.465 6.133 5.212 6.676 6.676 6.676 6.676 6.676 6.676 6.676 6.676 99 3.221 0.251 0.486 2.48 0 0 0 0 0 0 0 0 100 1.332 5.335 1.57 3.702 0 0 0 0 0 0 0 0 Total 130.766 103.501 182.445 141.585 135.149 100.421 180.61 137.141 58 APPENDIX B Numerical Results in Additional Cost Case with Di®erent Price Appendix B data goes here Demand Strucuture 1 4.571 3.614 7.308 6.648 19.776 19.594 19.776 18.964 21.776 21.594 21.776 20.964 2 3.111 0.619 5.024 1.471 10.222 10.22 10.222 10.212 11.244 11.242 11.244 11.235 3 1.713 1.695 1.569 3.463 8.439 8.439 8.439 8.439 9.283 9.283 9.283 9.283 4 2.193 0.628 7.936 2.299 12.763 12.469 12.763 11.588 14.069 13.775 14.069 12.894 5 2.988 0.795 1.357 1.823 6.964 6.964 6.964 6.964 7.66 7.66 7.66 7.66 6 0.209 0.913 7.106 7.7 15.105 14.085 14.565 12.571 16.698 15.677 16.158 14.092 7 7.115 1.961 6.107 4.114 18.729 17.615 18.272 17.071 20.659 19.545 20.202 18.878 8 1.42 1.921 4.137 6.71 13.933 13.506 13.591 13.252 15.351 14.925 15.009 14.67 9 2.91 6.163 0.509 7.636 16.839 16.311 16.311 16.079 18.56 18.033 18.033 17.8 10 0.427 1.345 7.888 5.234 14.558 14.199 14.511 13.262 16.048 15.688 16.001 14.752 11 5.057 0.578 7.888 6.633 19.404 18.655 19.098 17.329 21.404 20.655 21.098 19.329 12 0.687 1.798 0.427 7.834 10.462 9.895 9.895 9.895 11.536 10.969 10.969 10.969 13 3.168 0.209 7.878 5.251 16.167 15.804 16.117 14.866 17.818 17.455 17.767 16.516 14 2.529 2.696 4.469 1.921 11.615 11.615 11.615 11.615 12.777 12.777 12.777 12.777 15 6.672 6.785 0.206 3.565 16.502 15.06 15.752 14.536 18.225 16.783 17.475 16.08 16 3.516 1.921 2.696 1.345 9.477 9.477 9.477 9.477 10.425 10.425 10.425 10.425 17 1.961 7.878 5.379 2.414 17.246 17.143 17.224 16.421 19.009 18.906 18.987 18.163 18 0.209 6.71 7.888 3.168 17.226 16.937 17.226 15.151 19.024 18.735 19.024 16.949 19 7.106 5.057 6.163 0.206 17.961 16.847 17.628 16.27 19.814 18.7 19.481 18.007 20 6.672 6.037 7.653 4.944 19.994 19.977 19.989 19.972 21.994 21.977 21.989 21.972 21 7.878 4.723 3.168 0.05 15.531 14.668 15.243 14.38 17.113 16.25 16.825 15.962 22 5.663 7.831 2.933 3.565 19.154 17.694 18.393 16.984 21.153 19.693 20.392 18.778 23 6.037 7.888 7.917 7.45 20 20 20 20 22 22 22 22 24 0.427 3.422 5.251 6.633 15.35 14.835 15.024 14.24 16.924 16.409 16.597 15.782 25 0.509 1.789 4.684 2.333 9.316 9.316 9.316 9.316 10.248 10.248 10.248 10.248 26 0.509 6.633 6.163 2.529 15.439 15.322 15.439 14.414 17.022 16.906 17.022 15.998 27 0.427 4.626 7.106 3.48 15.254 15.043 15.254 14.065 16.818 16.607 16.818 15.629 28 2.696 6.037 6.672 1.378 16.305 16.016 16.264 15.054 17.983 17.694 17.943 16.691 29 7.888 1.42 3.898 0.209 13.127 12.261 12.838 11.972 14.469 13.602 14.18 13.313 30 1.798 3.168 4.723 0.05 9.739 9.739 9.739 9.739 10.713 10.713 10.713 10.713 31 7.653 2.696 0.05 1.789 11.923 11.127 11.658 10.862 13.142 12.346 12.877 12.081 32 3.422 6.672 1.297 4.684 15.899 15.871 15.889 15.527 17.506 17.478 17.497 17.134 33 4.626 7.917 0.913 7.959 19.328 18.172 18.398 17.872 21.328 20.172 20.398 19.759 34 5.757 6.71 4.363 1.798 18.21 17.47 17.963 16.881 20.073 19.333 19.826 18.744 35 2.333 3.565 1.378 5.001 12.277 12.277 12.277 12.277 13.505 13.505 13.505 13.505 36 7.636 1.345 0.495 3.898 12.957 11.859 12.387 11.596 14.295 13.197 13.724 12.933 37 4.626 7.834 1.508 3.565 16.901 15.958 16.45 15.248 18.654 17.711 18.203 16.898 38 1.798 0.05 7.959 2.933 12.444 12.148 12.444 11.261 13.718 13.422 13.718 12.535 39 1.378 1.789 4.363 7.878 14.895 14.096 14.32 13.424 16.436 15.637 15.861 14.965 59 Demand Strucuture 40 7.917 1.584 2.333 6.037 17.056 15.261 15.973 14.97 18.843 17.048 17.76 16.628 41 4.363 3.103 2.933 2.333 12.732 12.732 12.732 12.732 14.006 14.006 14.006 14.006 42 3.75 3.422 7.831 6.785 19.592 19.31 19.592 18.211 21.592 21.31 21.592 20.211 43 5.251 4.684 1.508 6.571 17.807 17.367 17.417 17.342 19.608 19.168 19.218 19.143 44 0.05 2.292 2.714 7.339 12.156 11.683 11.688 11.667 13.396 12.923 12.928 12.907 45 6.672 4.6 4.04 1.789 16.933 16.432 16.766 16.264 18.643 18.142 18.476 17.975 46 5.757 2.933 2.292 7.351 17.907 17.018 17.21 16.943 19.74 18.852 19.043 18.736 47 1.508 2.714 3.75 4.802 12.774 12.774 12.774 12.774 14.051 14.051 14.051 14.051 48 5.001 4.363 6.571 3.422 19.013 18.575 18.919 18.104 20.948 20.511 20.855 19.946 49 1.584 7.298 6.6 3.768 18.651 18.347 18.603 17.184 20.576 20.272 20.528 19.061 50 1.58 7.633 7.959 3.898 19.249 18.729 19.139 17.479 21.249 20.729 21.139 19.369 51 2.933 3.707 2.678 7.922 16.889 16.244 16.304 16.064 18.613 17.968 18.028 17.788 52 5.663 5.757 6.571 4.363 19.936 19.745 19.873 19.681 21.936 21.745 21.873 21.681 53 2.292 2.61 4.091 3.75 12.743 12.743 12.743 12.743 14.017 14.017 14.017 14.017 54 7.351 2.674 1.782 6.063 17.274 15.866 16.356 15.631 19.061 17.653 18.143 17.399 55 7.917 5.853 3.358 4.222 19.594 18.54 19.023 18.298 21.594 20.54 21.023 20.298 56 5.518 1.219 0.269 4.267 11.222 11.067 11.17 11.015 12.35 12.194 12.298 12.142 57 0.845 0.908 1.886 4.198 7.838 7.838 7.838 7.838 8.621 8.621 8.621 8.621 58 4.923 4.794 3.708 2.582 16.007 16.007 16.007 16.007 17.608 17.608 17.608 17.608 59 2.41 6.603 1.569 7.593 17.755 17.236 17.236 16.916 19.572 19.054 19.054 18.733 60 4.377 1.622 1.025 3.299 10.323 10.323 10.323 10.323 11.355 11.355 11.355 11.355 61 2.714 4.04 5.853 1.584 14.106 14.021 14.106 13.765 15.526 15.44 15.526 15.184 62 6.284 4.802 7.351 5.001 19.98 19.96 19.98 19.901 21.98 21.96 21.98 21.901 63 3.75 3.707 7.922 7.339 19.621 19.367 19.621 18.354 21.621 21.367 21.621 20.354 64 7.795 3.236 1.93 4.624 17.063 15.741 16.3 15.462 18.822 17.499 18.058 17.22 65 2.678 3.768 4.128 3.358 13.932 13.932 13.932 13.932 15.325 15.325 15.325 15.325 66 6.284 3.707 7.298 7.351 19.871 19.741 19.871 19.354 21.871 21.741 21.871 21.354 67 1.557 7.633 3.75 6.6 19.047 18.693 18.728 18.026 21.002 20.647 20.682 19.945 68 2.714 4.091 2.846 7.894 17.181 16.529 16.603 16.307 18.936 18.283 18.357 18.061 69 2.292 5.853 2.61 1.711 12.381 12.381 12.381 12.211 13.628 13.628 13.628 13.457 70 1.301 6.291 3.236 1.58 12.279 12.279 12.279 12.02 13.519 13.519 13.519 13.261 71 5.001 5.663 1.789 2.293 14.614 14.415 14.547 14.216 16.088 15.889 16.022 15.69 72 7.45 7.653 0.495 2.714 17.183 15.14 16.14 14.385 19.004 16.961 17.961 15.951 73 4.802 7.831 3.565 7.922 19.837 19.55 19.55 19.51 21.837 21.55 21.55 21.51 74 7.298 0.228 3.707 2.674 13.677 12.988 13.448 12.758 15.068 14.379 14.838 14.149 75 6.284 7.959 1.58 2.292 17.241 15.661 16.51 14.799 19.053 17.473 18.321 16.457 76 4.091 7.298 4.222 1.557 16.799 16.383 16.66 15.784 18.516 18.1 18.377 17.501 77 5.334 0.228 3.236 6.045 14.671 14.295 14.362 14.262 16.156 15.78 15.847 15.746 78 1.93 6.291 2.61 3.768 14.47 14.47 14.47 14.211 15.929 15.929 15.929 15.671 79 2.674 2.212 7.633 2.678 14.934 14.671 14.934 13.881 16.454 16.19 16.454 15.4 80 5.844 6.063 5.075 4.6 19.96 19.84 19.92 19.8 21.96 21.84 21.92 21.8 81 2.61 1.58 0.228 2.674 7.092 7.092 7.092 7.092 7.801 7.801 7.801 7.801 82 7.894 7.831 3.358 2.714 19.34 17.833 18.619 17.337 21.34 19.833 20.619 19.233 83 3.768 2.678 5.334 7.45 18.661 17.892 18.17 17.01 20.584 19.815 20.093 18.887 84 2.333 1.93 4.04 7.351 15.28 14.671 14.81 14.253 16.846 16.236 16.375 15.819 85 4.128 6.045 6.571 5.001 19.913 19.913 19.913 19.738 21.913 21.913 21.913 21.738 86 1.584 3.768 4.624 4.04 14.016 14.016 14.016 14.016 15.417 15.417 15.417 15.417 87 4.6 3.236 7.298 2.292 17.129 16.859 17.115 16.09 18.871 18.602 18.858 17.819 88 7.894 2.597 1.58 4.128 15.707 14.434 15.013 14.145 17.326 16.054 16.633 15.765 89 6.045 2.714 4.991 6.063 19.288 18.343 18.762 17.922 21.269 20.325 20.743 19.799 90 1.682 1.711 5.844 3.707 12.86 12.776 12.86 12.522 14.155 14.07 14.155 13.817 91 2.293 4.6 4.222 3.707 14.823 14.823 14.823 14.823 16.305 16.305 16.305 16.305 60 Demand Strucuture 92 2.61 0.228 5.853 3.768 12.374 12.289 12.374 12.033 13.62 13.535 13.62 13.279 93 7.922 4.363 2.714 1.782 16.489 15.612 16.197 15.32 18.167 17.291 17.875 16.998 94 6.284 7.45 7.917 2.846 19.698 19.052 19.482 18.662 21.698 21.052 21.482 20.662 95 4.04 6.291 0.21 7.795 17.861 17.136 17.202 16.878 19.694 18.97 19.036 18.679 96 2.212 1.072 2.639 6.184 11.989 11.752 11.752 11.752 13.2 12.963 12.963 12.963 97 5.563 4.991 1.682 3.009 15.189 15.02 15.132 14.963 16.713 16.544 16.657 16.488 98 5.242 5.075 0.273 7.275 17.567 16.953 17.017 16.914 19.353 18.74 18.803 18.693 99 3.236 5.854 4.044 1.425 14.472 14.472 14.472 14.302 15.928 15.928 15.928 15.757 100 4.182 3.568 4.984 1.493 14.227 14.227 14.227 14.227 15.65 15.65 15.65 15.65 Total 1553.704 1507.743 1529.807 1470.2 1711.998 1666.038 1688.102 1626.264 61 APPENDIX C Numerical Results in Additional Cost Case with Same Price Appendix C data goes here Demand Strucuture 1 4.339 6.219 7.523 1.137 18.284 17.107 17.975 16.05 17.161 16.462 15.939 15.872 2 0.874 5.793 0.839 2.246 9.673 9.673 9.673 9.514 9.435 9.673 9.514 9.435 3 3.87 5.331 7.443 0.867 16.824 16.087 16.66 15.128 15.992 15.194 15.448 15.015 4 1.151 4.327 1.084 5.127 11.677 11.651 11.651 11.651 11.626 11.613 11.651 11.613 5 2.104 1.046 0.651 7.633 11.17 10.644 10.644 10.644 10.117 9.854 10.644 9.854 6 0.575 6.533 7.443 7.523 19.223 18.844 19.133 17.136 17.716 17.443 18.248 16.739 7 3.128 1.59 2.432 0.874 8.024 8.024 8.024 8.024 8.024 8.024 8.024 8.024 8 1.084 4.06 7.65 3.75 16.108 15.843 16.108 14.706 15.595 14.518 15.766 14.535 9 3.875 4.437 2.246 5.793 16.271 16.112 16.112 16.112 15.954 15.874 16.112 15.874 10 3.576 0.878 5.127 5.331 14.832 14.72 14.766 14.583 14.7 14.492 14.766 14.517 11 3.875 3.714 5.331 0.089 12.975 12.942 12.975 12.843 12.975 12.777 12.975 12.843 12 2.432 6.65 4.459 3.576 16.952 16.952 16.952 16.622 16.457 16.952 16.622 16.457 13 1.084 6.743 2.246 0.878 10.777 10.777 10.777 10.428 10.254 10.777 10.428 10.254 14 0.874 1.063 1.046 5.127 8.097 8.072 8.072 8.072 8.047 8.034 8.072 8.034 15 7.443 1.137 7.098 0.867 16.09 15.147 15.846 14.274 16.09 14.587 14.624 13.785 16 1.016 6.966 5.9 7.254 19.288 18.863 19.064 17.572 17.646 17.965 18.268 17.286 17 4.437 0.541 6.712 3.033 14.551 14.38 14.551 13.867 14.551 13.524 14.551 13.867 18 1.561 1.582 0.231 0.318 3.692 3.692 3.692 3.692 3.692 3.692 3.692 3.692 19 0.549 1.59 2.629 1.063 5.831 5.831 5.831 5.831 5.831 5.831 5.831 5.831 20 7.093 2.597 0.789 1.226 11.496 10.868 11.287 10.659 11.496 11.287 10.24 10.24 21 0.549 6.494 5.496 3.362 15.653 15.603 15.653 15.057 15.056 15.355 15.255 14.858 22 1.582 1.071 0.429 5 8.082 8.082 8.082 8.082 8.082 8.082 8.082 8.082 23 1.561 6.559 0.405 7.528 15.644 15.139 15.139 14.827 14.165 14.38 14.827 13.913 24 7.254 4.153 1.746 5.523 18.173 16.942 17.392 16.716 17.062 16.559 16.265 16.108 25 6.309 0.231 1.59 6.929 14.604 13.564 13.826 13.434 13.31 12.855 13.172 12.593 26 6.918 4.327 7.098 0.149 17.805 16.593 17.471 15.772 17.378 16.212 15.657 15.388 27 6.309 3.362 2.597 0.131 12.268 11.875 12.137 11.744 12.268 12.137 11.483 11.483 28 1.063 0.405 4.667 5.127 11.249 11.224 11.224 11.224 11.198 11.186 11.224 11.186 29 1.063 4.41 1.561 5.962 12.899 12.707 12.707 12.707 12.515 12.418 12.707 12.418 30 1.046 1.016 0.429 6.966 9.26 8.867 8.867 8.867 8.474 8.277 8.867 8.277 31 6.219 7.18 1.063 6.918 19.324 17.931 18.335 17.65 17.51 17.154 17.406 16.83 32 3.714 5.793 0.575 1.046 11.049 11.049 11.049 10.89 10.811 11.049 10.89 10.811 33 7.098 5.127 0.878 1.151 14.018 13.351 13.796 13.103 13.98 13.796 12.658 12.658 34 5.9 4.437 2.323 1.084 13.654 13.384 13.564 13.294 13.654 13.564 13.114 13.114 35 7.254 3.576 7.87 2.104 19.44 18.364 19.15 17.519 19.247 17.91 17.638 17.068 36 3.991 0.92 0.789 4.05 9.75 9.75 9.75 9.75 9.75 9.75 9.75 9.75 37 0.429 6.32 1.582 6.559 14.602 14.29 14.29 14.026 13.582 13.822 14.026 13.426 38 7.044 1.746 7.514 5.703 19.597 19.112 19.445 18.143 19.3 17.5 19.43 18.002 39 1.226 7.528 0.651 5.523 14.623 14.518 14.518 14.012 13.655 14.361 14.012 13.603 62 Demand Strucuture 40 5.223 1.016 2.744 5.147 14.071 13.93 13.974 13.907 13.922 13.863 13.863 13.818 41 0.549 7.093 3.938 5.703 17.004 16.863 16.863 16.444 16.094 16.652 16.444 16.024 42 5.496 0.541 5 6.309 16.935 16.245 16.524 15.803 16.213 15.541 16.326 15.541 43 5.962 0.405 0.429 7.528 13.878 12.892 13.084 12.796 12.482 12.037 12.603 11.845 44 3.033 1.53 6.712 4.153 15.256 15.085 15.256 14.572 15.256 14.229 15.256 14.572 45 1.561 6.677 7.044 1.59 16.268 15.979 16.24 14.678 15.151 15.013 15.382 14.334 46 0.651 1.582 1.063 1.53 4.825 4.825 4.825 4.825 4.825 4.825 4.825 4.825 47 1.016 0.318 4.41 5.962 11.572 11.342 11.379 11.231 11.187 10.979 11.379 10.979 48 5.9 6.494 4.437 0.92 17.362 16.644 17.123 16.106 16.914 17.123 15.627 15.627 49 3.991 0.405 0.429 2.629 7.454 7.454 7.454 7.454 7.454 7.454 7.454 7.454 50 3.362 0.541 6.712 7.87 17.727 16.695 17.153 15.308 16.543 14.417 17.129 14.759 51 7.528 1.582 6.32 1.016 16.061 15.17 15.808 14.521 16.061 15.016 14.544 14.016 52 7.044 6.966 1.226 5.472 19.167 17.421 18.082 16.965 17.28 16.949 16.556 16.415 53 0.429 6.929 0.651 4.05 11.865 11.865 11.865 11.479 11.286 11.865 11.479 11.286 54 1.071 5.223 0.92 1.758 8.95 8.95 8.95 8.905 8.883 8.95 8.905 8.883 55 5.523 7.093 7.431 4.41 19.934 19.757 19.875 19.685 19.914 19.875 19.567 19.567 56 1.561 4.41 7.254 1.063 13.896 13.671 13.896 12.662 13.397 12.544 13.563 12.495 57 1.063 1.016 0.318 3.991 6.387 6.387 6.387 6.387 6.387 6.387 6.387 6.387 58 5.962 4.437 1.226 0.549 12.078 11.789 11.982 11.693 12.078 11.982 11.501 11.501 59 1.53 6.966 5.127 3.033 16.434 16.421 16.434 15.964 15.806 16.358 16.015 15.755 60 5.496 5.9 0.92 1.746 13.832 13.413 13.692 13.093 13.562 13.692 12.814 12.814 61 7.633 7.523 1.151 1.084 16.39 14.673 15.673 13.808 15.246 15.348 13.025 13.025 62 3.75 0.878 6.533 2.104 13.112 12.958 13.112 12.499 13.112 12.192 13.112 12.499 63 6.918 7.443 0.839 2.789 17.094 15.356 16.228 14.646 15.501 15.583 14.204 14.204 64 6.743 5.127 2.416 5.793 19.558 18.503 18.862 18.32 18.51 18.086 17.971 17.733 65 6.219 3.576 3.87 1.063 14.606 14.24 14.484 14.118 14.606 14.484 13.874 13.874 66 5.086 2.094 0.831 5.872 13.779 13.561 13.579 13.553 13.396 13.291 13.536 13.274 67 3.702 1.308 6.822 2.272 13.922 13.74 13.922 13.193 13.922 12.829 13.922 13.193 68 4.767 6.826 1.201 4.888 17.193 16.418 16.737 16.042 16.052 16.293 16.019 15.996 69 3.12 1.445 1.647 4.71 10.923 10.923 10.923 10.923 10.923 10.923 10.923 10.923 70 1.065 7.482 4.025 0.084 12.408 12.408 12.408 11.912 11.663 12.408 11.912 11.663 71 6.91 4.06 1.063 7.254 18.657 17.228 17.633 17.037 16.991 16.361 16.701 16.025 72 2.432 2.597 4.437 7.098 16.201 15.628 15.781 15.167 15.362 14.691 15.781 14.691 73 6.65 1.084 6.309 6.533 19.24 18.005 18.611 17.045 18.197 16.477 18.182 16.738 74 1.746 0.131 0.405 5.496 7.727 7.628 7.628 7.628 7.529 7.479 7.628 7.479 75 6.918 0.541 5.962 4.327 17.211 16.166 16.77 15.686 16.713 15.695 15.936 15.551 76 2.744 2.564 3.022 0.276 8.605 8.605 8.605 8.605 8.605 8.605 8.605 8.605 77 6.025 6.929 7.044 6.677 20 20 20 20 20 20 20 20 78 1.758 1.929 3.793 5.223 12.681 12.636 12.636 12.636 12.591 12.569 12.636 12.569 79 7.514 5.523 5.09 5.154 20 20 20 20 20 20 20 20 80 6.922 1.976 6.343 4.05 18.769 17.767 18.383 17.172 18.381 17.188 17.519 16.982 81 2.744 6.7 4.05 5.223 18.524 18.48 18.48 18.14 17.925 18.413 18.14 17.903 82 2.933 2.564 5.314 7.514 17.751 16.965 17.248 16.078 16.628 15.591 17.17 15.653 83 6.32 6.929 1.758 6.611 19.482 18.344 18.67 18.15 18.091 17.697 17.886 17.402 84 4.732 7.431 6.677 6.988 19.973 19.973 19.973 19.92 19.893 19.973 19.92 19.893 85 1.258 3.304 0.276 3.591 8.429 8.429 8.429 8.429 8.429 8.429 8.429 8.429 86 7.528 2.629 0.651 0.279 10.834 10.075 10.581 9.823 10.834 10.581 9.317 9.317 87 1.929 1.386 4.056 5.09 12.452 12.434 12.434 12.434 12.416 12.407 12.434 12.407 88 1.758 3.591 7.514 3.304 15.805 15.554 15.805 14.578 15.473 14.297 15.584 14.468 89 2.933 7.431 2.166 2.744 14.994 14.885 14.958 14.362 14.265 14.958 14.29 14.083 90 0.125 6.611 5.092 5.314 16.869 16.766 16.806 16.272 16.138 16.594 16.403 16.101 91 1.976 1.073 4.389 1.258 8.696 8.696 8.696 8.696 8.696 8.696 8.696 8.696 63 Demand Strucuture 92 7.956 2.301 4.408 0.771 15.141 14.255 14.846 13.959 15.141 14.846 13.368 13.368 93 4.382 3.123 2.638 6.456 16.454 16.163 16.163 16.163 15.871 15.726 16.163 15.726 94 4.732 6.343 6.989 3.022 19.487 18.804 19.289 18.156 18.813 18.748 17.941 17.915 95 0.687 1.645 1.382 5.548 9.207 9.097 9.097 9.097 8.987 8.933 9.097 8.933 96 4.859 1.859 0.771 3.123 10.612 10.612 10.612 10.612 10.612 10.612 10.612 10.612 97 1.442 0.34 3.608 4.382 9.773 9.773 9.773 9.773 9.773 9.773 9.773 9.773 98 1.382 7.922 4.76 6.989 19.475 19.218 19.287 18.355 18.015 18.867 18.564 17.991 99 5.154 4.408 4.816 5.889 19.863 19.649 19.708 19.471 19.553 19.298 19.708 19.298 100 2.638 1.142 6.396 3.556 13.591 13.452 13.591 13.033 13.591 12.754 13.591 13.033 Total 1429.973 1389.439 1409.455 1354.194 1381.495 1358.386 1364.069 1328.257 64 VITA Meng Li Candidate for the Degree of Master of Science Thesis: STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBIL ITY DESIGN Major Field: Industrial Engineering and Management Biographical: Personal Data: Born in Hengshui, Hebei, China on March 11, 1981. Education: Yanshan University, China B.E. in Material Engineering July, 2002 Tianjin University, China M.S. in Applied Math March, 2005 Oklahoma State University, USA M.S. in IEM December, 2008 Experience: Oklahoma State University Research Assistant 2007=09 ¡ 2008=05 SoftTech Development Inc. Software Engineer 2006=02 ¡ 2006=07 Beijing Nantian Software Co.,Ltd Software Engineer 2005=03 ¡ 2005=09 Name: Meng Li Date of Degree: December, 2008 Institution: Oklahoma State University Location: Stillwater, Oklahoma Title of Study: STUDY OF FLEXIBILITY INDICES IN MANUFACTURING FLEXIBILITY DESIGN Pages in Study: 64 Candidate for the Degree of Master of Science Major Field: Industrial Engineering and Management This thesis examines structure index for process °exibility design with e±ciency loss in cross production. We conducted numerical experiments to study the performance of the SF (Structure Flexibility) Matrix Index and the Graph Expander Index with two types of e±ciency loss: shrinking capacity or additional cost in cross production. Our experiments suggest that SF index and expander index are purely robust and powerful in predicting system performance ranking at demand variation. This suggests that the SF index and graph expander index can help managers to design good manufacturing °exibility structure, without requiring intensive simulation. ADVISOR'S APPROVAL: 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


