Filiz Isik

An Entropy-Based Approach for Measuring Complexity in Supply Chains

Keywords: SUPPLY CHAIN DYNAMICS, SUPPLY CHAIN Complexity, Supply Chain, Entropy, Measurement. 1

Today's supply chains are more complex than ever due to globalization and its effects especially on the logistics activities. Therefore, understanding and managing complexity in supply chains are very popular topics nowadays. Measures for complexity in supply chains contribute to their manageability and controllability. This paper describes an approach to the measurement of complexity in supply chains based on the Shannon's information entropy. The new proposed approach gives a formal approach that is able to measure and analyze the supply chain complexity. The main contribution of this study is to extend two formulas (structural and operational complexity) building on the Shannon's entropy measure to evaluate the complexity of a supply chain. The aim is to measure complexity associated with information and material flows in the chain. A numerical example is presented to demonstrate the approach.

Introduction

Competitiveness is essential for every company in the business world. Every company wants to reduce their costs to compete better. Globalization, customers' expectations, reduced costs, shorter allowed lead-times, shorter product life cycles, etc. are parameters that determine business success.

To compete successfully, companies are using mergers, acquisitions, and joint ventures to achieve market penetration, product launches to combat the rise in commoditization, and outsourcing to keep costs low, while improving service levels to meet the growing expectations of customers. As a result, supply chains are growing increasingly complex [START_REF] Vickers | Deriving Benefit from Supply Chain Complexity[END_REF]. Successful businesses are now those able to master this evolution. So, after exploiting all internal resources, companies have started to focus more closely on their supply chain, seeking an overall cost reduction and an overall increase of effectiveness and efficiency. Therefore, improving competitiveness of a company now involves suppliers and distributors thus making the overall system more complex. As a matter of fact, many managers are realizing that the control of this overall complexity is a strategic issue for the company, and for the whole supply chain [START_REF] Perona | Complexity management and supply chain performance assessment: a field study and a conceptual framework[END_REF].

However complexity in supply chains is defined, a high or low complexity comprises no value itself. Low or high complexity in supply chains might include both advantages and disadvantages. On one hand, complexity can sometimes be necessary and value adding. For 2 example, it could help a company to gain market share. On the other hand, low complexity does not necessarily need to be positive but might be expensive for the company.

Complexity may enable flexibility. High complexity includes advantages when the customer pays for it that means when the market is demanding a lot of variety. For example, mass customization involves deliberately expanding the complexity of the product range to offer customers greater variety. The key is to be able to do this without raising prices. This is the balance of a successful mass customization strategy. A manufacturer can have a lot of complexity in stock. If suppliers are variable and unpredictable or customers keep changing their minds at the last minute, then, the manufacturer can accommodate it by keeping stock. It is how a manufacturer often deals with it and is therefore a symptom of high complexity but, of course the manufacturer is then paying for the storage. High complexity includes disadvantages when a facility is not operating well and generating a lot of information which a manufacturer must pay for that high complexity merely involves additional cost [START_REF] Frizelle | Seminar Notes On "Measuring Complex Systems[END_REF]. Therefore, complexity is very difficult to manage. In order to manage complexity better, it is first recommended to be measured so that it can be understood how big it is both in absolute and relative terms. The present paper focuses on defining and measuring supply chain complexity. A measure based on the entropy method will be derived and discussed. It has been first introduced in manufacturing by [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF]. This paper discusses their approach and expands it according to some drawbacks presented in the discussion.

Complexity measures as discussed in this paper, based on entropy, have many useful advantages and can be simply applied in the industrial world. They are also relevant in supply chains to examine the performance of a supply chain's interfaces between the manufacturer, the supplier and the customer. Supply chains can be analyzed by this method from many perspectives. It can be used in order to compare the flows (material and information), different products on different product lines, supply chain partners, etc. The entropy measure presented here can also be used for analyzing internal, external and total complexity of a supply chain business partner.

Literature Review

Complexity as a concept is widely discussed in several scientific areas such as physics, biology, chemistry, mathematics, computer science and economics. This paper focuses on supply chain complexity (SCC). From the theoretical perspective, some researchers studied complexity in manufacturing. [START_REF] Wilding | The supply chain complexity triangle: Uncertainty generation in the supply chain[END_REF] described the interaction between deterministic chaos, parallel interactions and demand amplification as a "supply chain complexity triangle" in order to understand the generation of uncertainty within supply chains. [START_REF] Calinescu | Classes of complexity in manufacturing[END_REF] classified complexity in manufacturing into three categories: decision-making complexity, structural complexity and behavioural complexity to analyze the manufacturing complexity. [START_REF] Milgate | Supply chain complexity and delivery performance: an international exploratory study[END_REF] described the dimensions of supply chain complexity as uncertainty, technological intricacy and organizational system to manage it. To manage complexity in manufacturing, understanding and measuring complexity is becoming increasingly important. This paper focuses on the measurement of the supply chain complexity associated with uncertainty and variety. One of the approaches to evaluate uncertainty is the information-theoretic entropy-based measure, which was first introduced by Shannon in 1948. Although the concept of entropy is known as a measure of thermodynamic, it has been used also as statistical measure in manufacturing. From the statistical perspective, some authors applied the entropy-based measure to manufacturing. [START_REF] Yao | Material and information flows in flexible manufacturing systems[END_REF] studied the entropy as a measure of flexibility. [START_REF] Deshmukh | Characteristics of Part Mix Complexity Measure for Manufacturing systems[END_REF] [START_REF] Ronen | An information entropy approach to the small-lot concept[END_REF] developed an approach which includes a formula for determining the location of a lot based on entropy measurement. [START_REF] Johnston | From Efficiency to Flexibility: Entropic Measures of Market Complexity and Production Flexibility[END_REF] studied the production flexibility and the market complexity based on entropy measure.

The academic work of entropy-based measures in supply chains has been first elaborated by the Institute for Manufacturing (IFM) at Oxford and Cambridge Universities. The aim of the IFM research was to define and to quantify the complexity in supply chains [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF][START_REF] Calinescu | Applying and assessing two methods for measuring complexity in manufacturing[END_REF][START_REF] Sivadasan | An information-theoretic methodology for measuring the operational complexity of supplier-customer systems[END_REF][START_REF] Sivadasan | Advances on measuring the operational complexity of supplier-customer systems[END_REF]. [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF] defined an entropy-based measure to quantify complexity in supply chains based on Shannon's information entropy. They classified complexity into structural (static) and operational (dynamic). Structural complexity deals with variety (schedule) and operational complexity deals with uncertainty (deviation from the schedule). In their work, supply chain is considered as a random variable with different states and corresponding probabilities for each state.

The new proposed approach gives a formal approach that is able to measure and to analyze the supply chain complexity. The main contribution of this study is to develop two new measures for structural and operational complexity building on [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF] approach by using Shannon's information entropy [START_REF] Shannon | The Mathematical Theory of Communication[END_REF]. In [START_REF] Shannon | The Mathematical Theory of Communication[END_REF]Frizelle`s and[START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF] work, complexity is only a function of probabilities of different states. This paper argues that complexity is not only a function of probabilities of different states, but also each state can have different complexity level of its own that needs to be considered. As a contribution of the new approach, an expected value is defined for each state, and the deviation from that expected value is measured. In order to demonstrate the new approach, a numerical example is presented and the complexity measures (structural and operational) of a supply chain system are calculated using these new proposed formulas.

Complexity and its Dimensions

Understanding and measuring complexity become increasingly important in manufacturing, especially in supply chains. It is difficult to define what complexity really means. There are many definitions of complexity in literature. Some of them are -Complexity is being marked by an involvement of many parts, aspects, details, notions, and necessitating earnest study or examination to understand or cope with (Webster's Third International Dictionary, [START_REF] Gove | Complexity, Webster's third new international dictionary of the English language unabridged[END_REF]).

-Complexity arises from not only the size of the system but also from the interrelationships of the system components and the emergent behaviour that cannot be predicted from the individual system components [START_REF] Arteta | A measure of agility as the complexity of the enterprise system[END_REF].

Regarding these definitions and referring to the goal of this study, complexity here is seen as the quantitative differences between two states (predicted and real) which include uncertainty and/or variety and associated with internal and external causes in a (supply chain) system.

Obviously, uncertainty and variety are not the only dimensions (factors) which have influence on complexity. There are also other dimensions of complexity. According to Reiss Size (Number) includes e.g. number of products, processes, partners, customers, goals, locations, etc. The higher the number of the systems` component, the higher the complexity. This way of measuring complexity is relatively easy to capture because it is not surprising to know that, if the number is reduced, complexity will also be reduced. Therefore, if the number of the parameter under consideration is changed, complexity of the system also changes.

Diversity covers the homogeneity or heterogeneity of the system. The more heterogeneous (or less homogeneous) the system is, the higher (the lower) the complexity is.

Variety (variability) is associated with the variations of internal and external states (environment), requirements, and sources in the course of time. If the types of the system elements change rapidly or unexpectedly, the complexity of the system increases. This component of complexity integrates the dynamic aspects of complexity.

Uncertainty comprises the difficulties to make a clear picture of the system. Indefiniteness, risks, ambiguities, ambivalences are some examples of a systems` deficit and cause uncertainty. If uncertainty increases, complexity will increase as well.

Measuring complexity is not only a value for itself but is a tool to evaluate a company's status with respect to complexity and must be in line with the company goals as well as must substantiate these goals. In this paper, I will focus on the uncertainty and variety aspects of SCC. Size (number) and diversity will not be addressed explicitly here.

Supply Chain Complexity

A complex system is a system with numerous components and interconnections, interactions, or interdependencies that are difficult to describe, understand, predict, manage, design, and/or change [START_REF] Magee | An attempt at complex system classification[END_REF]de Weck 2002: Engineering Systems Division, MIT 2002). Complex systems are typically organizations made of many heterogeneous parts interacting locally in the absence of a centralized pacemaker and control [START_REF] Fontana | Complexity: an essay[END_REF]. Several factors contribute to system complexity: (i) the number of components in the system, (ii) the number of relationships among these components (i.e., the degree of coupling), and (iii) the types of relationships between the components [START_REF] Gonzalez | The use of microworlds to study dynamic decision making[END_REF]). As a system a supply chain is also complex and the business environment is uncertain. The supply chain is a complex network of facilities and organizations with different, conflicting objectives. This implies that finding the best supply chain strategy for a particular firm poses significant challenges (Simchi-Levi and Kaminsky 2000).

The variety and uncertainty of a supply chain might be extremely high and cause complexity. It can be associated with organizational, operational or technical causes of a supply chain. The more uncertainty or variety in a system, the more complex the supply network. A typical supply chain can often be complex, due to the following [START_REF] Blackhurst | Network-based approach to modeling uncertainty in a supply chain[END_REF]):

• Large mesh of interlinked participants (information and material flows) including suppliers, manufacturers and distributors across multiple organizations. • Each of these participants may be a member of a large number of other supply chains. • Dynamic and uncertain nature of the supply chain.

• Each participant may have differing objectives.

Based on the theory-oriented literature (such as [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF][START_REF] Calinescu | Classes of complexity in manufacturing[END_REF][START_REF] Sivadasan | An information-theoretic methodology for measuring the operational complexity of supplier-customer systems[END_REF]Blackhurst 2004 etc.) SCC can be defined as all operational uncertainties and/or structural varieties associated with internal or external causes by the information and/or material flows along the supply chain that are known, unknown, expected, unexpected, predicted or unpredicted.

A supply chain is a system with multiple business partners who work somehow independently of each other. Each supply chain participant has its own complexity level which can have impact on the other participants. A small complexity level of one participant in the chain can have a large impact on the whole supply chain system. For example, in a simple supply chain system which includes a single supplier, manufacturer and costumer (see figure 1) when demand forecast (schedule production) of the manufacturer has some deviation from the actual order (sales orders) from its customer, it can result in massive changes of manufacturer demand (purchasing orders) to its supplier. Variation of orders can increase up the supply chain from customer to supplier. This effect is also known as the "bullwhip effect" in the supply chain literature.

Within a supply chain, material and information flows represent the main complexity drivers because of uncertainty and/or variety in this study. The reasons causing complexity can originate from inside or from outside of a supply chain system. Therefore, complexity in a supply chain can be classified generally into three main categories, namely as internal SCC, external SCC and total SCC. Each business partner can have its own internal, external and total complexity level in a chain.

Internal Supply Chain Complexity is associated with material and information flows within a business partner of a supply chain. Internal SCC depends on the structure of the single business partner. Examples for increased SCC are: process deficits, material shortness, machine breakdowns, bad management techniques, large product variety, etc.

External Supply Chain Complexity is associated with material and information flows exported by other business partners to a partner. The causes might be related to globalization, technological innovation, customer demand variety, etc.

Total Supply Chain Complexity is associated with material and information flows within a business partner as well as amongst its other business partners. It includes both internal and external complexity. A coarse diagram of the complexity flows in a supply chain between manufacturer and its business partners (supplier and customer) are shown in figure 1. In this diagram internal SCC is associated with flows within the manufacturer; external SCC is associated with flows from a supplier and/or from a customer to the manufacturer and vice versa and total complexity covers all internal and external complexity.

5.

Entropy as a Measure of Complexity A supply chain is a complex system and before companies cope with it, they should first define "how complex this system is". But this is a general context. If we want to define the complexity of a system or compare two systems (A and B), to be able to say that system A is more complex than system B, we need some sort of quantitative indicator. Therefore, the Shannon's entropy is used to measure complexity quantitatively in this paper because it is simple and most widely used in uncertainty measure of a system in the relevant literature. Unfortunately, there are not many complexity measures which can be applied in manufacturing systems. Kolmogorov`s entropy [START_REF] Kolmogorov | Three approaches to the quantitative definition of information[END_REF] or Reny`s entropy can be used as a measure of uncertainty as well and they will be studied in the future work.

Although the entropy is known as a physical concept in the thermodynamic system and was first introduced by Rudolf Julius Emmanuel Clausius (1822-1888), later on scientists studied it from statistical aspect (such as Ludwig Eduard Boltzmann , James Clerk Maxwell (1831-1879), Claude Elwood Shannon, (1916[START_REF] Milgate | Supply chain complexity and delivery performance: an international exploratory study[END_REF]). Of the different entropy measures, Shannon's entropy [START_REF] Shannon | The Mathematical Theory of Communication[END_REF] is the most popular and common one and has established its usefulness in almost every area of science and technology, economics etc. [START_REF] Mandal | On the utility of different entropy measures in image thresholding[END_REF].

It is well known that "Shannon entropy measures the average uncertainty (in bits) associated with the prediction of outcomes in a random experiment" [START_REF] Klir | Fuzzy Sets and Fuzzy Logic: Theory and Applications[END_REF]. The basic idea behind the measure is that occurrence of events that have high probability provides less information (uncertainty) than occurrence of events that have low probability. The average uncertainty associated with an outcome is represented by discrete random variable X. The Shannon's information entropy [START_REF] Shannon | The Mathematical Theory of Communication[END_REF]) of a discrete random variable X, with n outcomes ( n x x ,..., 1) is:

∑ = - = n i i i x p x p X H 1 2 ) ( log ) ( ) ( (1)
where p(x i ) is the probability of outcomes of a system being in state i , (

n i ,..., 1 = ), 0 ) ( ≥ i x p , ∑ = = n i i x p 1 1 ) ( and 0 ) 0 ( log 2 = .
Shannon used logarithm to the base 2 in the entropy formula to give entropy the dimension of a binary digit (bit) which represents an answer, such as "0" or "1," "yes" or "no," or "on" or "off". In certain cases, it is possible to give a numerical measure to the amount of information (in the Shannon sense) in a state, which can tell us little about what the system is doing. The definition of a system state is often only an abbreviation of the essential information needed to characterize the system, as indicated in the dictionary definitions [START_REF] Reeker | A New Classification of Information: A Step on the Road to Interpretability[END_REF]. In complexity measurement, a state is defined as a description of the target (order), the resources, a recipe, and constraints [START_REF] Meijer | Reducing Complexity through Organizational Structuring in Manufacturing and Engineering[END_REF]. A system can have one or many states at a point of observation.

The entropic complexity measure (Shannon's information entropy) is only a function of probabilities of different states. But each state can have different entropy/complexity level of its own that needs to be considered. It means each state can have its own expected outcome value in a system. The expected value needs to be defined with respect to the problems that are being addressed. The complexity in this paper is defined as variation between expected and actual flows. The existence of variation between planned and actual flows shows that there is a complexity. If the variation between flows is zero there is not any complexity occurring. It is often expected that there is not any variation between the flows. In other words there is not any deviation from the schedule. Therefore, the expected outcome value for this study is zero. However, the expected value can also be some tolerated variation between expected and actual flows in a supply chain system according to the company and its structure. The corresponding deviation from that expected value shows the complexity of that particular state. Therefore, the equation ( 2) is proposed as a measure of entropy/complexity that includes the deviation value ( i d ) from the expected value.

The main contribution of the paper is modification of equation (1) as follows:

[ ] ∑ = - = n i i i i I d p p H 1 2 log ( 2
)
where i d is the deviation of outcomes ( n x x ,..., 1 ) from the expected outcome value for the state. The value of i d can be negative, zero or positive. Permitting negative values for i d makes equation ( 2) almost useless as a measure of entropy because a large negative value can change it drastically (robustness issue). Due to that reason absolute value of i d will be considered as the deviation of an outcome from its expected outcome in the formulas.

Measuring Supply Chain Complexity based on Entropy Method

The entropy based complexity measure for supply chains was first introduced by Frizelle and Woodcock (1995) and has been successfully used in industry [START_REF] Sivadasan | An information-theoretic methodology for measuring the operational complexity of supplier-customer systems[END_REF]. Their work includes a mathematical model that provides a measure for structural (static) complexity by equation (3) and operational (dynamic) complexity by equation (4). Furthermore they have defined operational complexity as complexity index in their study and applied their approach also to some companies (EPSRC, Unilever, BAE Systems and AEA Technology), (see http://www-mmd.eng.cam.ac.uk/complexity).

Structural (static) complexity, arising from the impact the product structure has on the resources that will produce it and represents the expected amount of information required to define the state of the system for a given period, is based on the information in the schedule [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF][START_REF] Calinescu | Applying and assessing two methods for measuring complexity in manufacturing[END_REF]. Structural complexity can be written [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF]: Operational (dynamic) complexity determines the operational behavior from direct observation of the process, in particular on how queues behave (in terms of queue length, variability and compositions) and represents the amount of information required to define the state of the system, based on monitoring the system for a given period. Operational complexity is related to the monitoring of planned and unplanned events [START_REF] Calinescu | Complexity in Manufacturing: An Information Theoretic Approach[END_REF]. Operational complexity can be defined as [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF]:

∑∑ = = - = M i N j ij ij s I p p H 1 1 2 ) ( log (
∑∑ = = - - = M i N j ij ij o I p p P H 1 1 2 ) ( log ) 1 ( (4)
where ) 0 ( I

H

: Operational complexity (Complexity Index) P : Probability of the system being "in control (scheduled)" state ) 1 ( P -: Probability of the system being "out of control (unscheduled)" state

Complexity can be associated with information or material flows within a supply chain. The information complexity measurements are recorded by sampling the variability in the primary information flows associated with forecast accuracy and schedule adherence. The material flow complexity is measured by sampling variations associated with schedule reliability of delivery and dispatch and variability of stock [START_REF] Frizelle | Measuring complexity as an aid to developing operational strategy[END_REF][START_REF] Sivadasan | Information Complexity as a Determining Factor in the Evolution of the Supply Chain[END_REF]. For the complexity measurement scheduled (in control) and unscheduled (out of control) are defined as possible states of a supply chain in this study. Regarding this definition each supply chain flow (information/material) has its own in control and out of control states which have to be considered. Table 1 shows some possible complexity measure variations in quantities associated with supply chain flows. They will not be addressed in this paper. Measuring complexity of manufacturing systems or supply chains based on the entropy measure presented by formulas (1), ( 3) and ( 4) is not without problems: This approach basically separates a system into two situations, i.e. a) the system is under control and b) the system is not under control. The (different) 'not under control' situations or states are here structurally seen to be indifferent with respect to their 'degree' of being not under control since in the entropy formula, these states are only weighted by their probability of occurrence. I.e. the same probability values contribute the same to the entropy/complexity formulas (1), ( 3) and ( 4) although the states underlying these probabilities might very well differ with respect to complexity. Think, e.g., of planning production in a manufacturing system: In some systems, the production plan meets easily the demand prognosis, in other slight differences occur whereas in further systems there might be large differences between the production plan and the demand prognosis. The last two systems, however, might have the same complexity measured by (4) although the (manufacturing) complexity is obviously different. Consequently, larger deviations from the 'under control' state should be weighted larger in complexity measures than smaller deviations.

Complexity by

Therefore, I propose a modified approach to a complexity measure by giving two new formulas for structural (equation 5) and operational complexity (equation 6) covered ij d that is the value of deviation from the expected value for resource i being in state j , ( 0

≥ ij d
). In order to explain the approaches, a numerical example will be presented.

The modified structural complexity can be defined:

[ ] ∑∑ = = - = M i N j ij ij ij s II p d p H 1 1 2 ) ( log (5)
The modified operational complexity can be defined:

[ ] ∑∑ = = - - = M i N j ij ij ij o II p d p P H 1 1 2 ) ( log ) 1 ( (6)

Numerical Example

The differences between predicted (forecasted) and real situations are "out of control" states in the chain and defined as complexity in this example. Complexity arises from the material and information flows exchanged between supply chain partners. Forecast and actual orders between a customer and its supplier are created, e. g. every month as a simple example 2). The supplier-costumer system is illustrated in figure 2. In order to illustrate the variations between forecast and actual order (from table 2) better, the two curves are plotted in figure 3. The quantitative differences between planned and actual value of monthly order are used as the outcome data X (discrete random variable) with 25 outcomes ( 25 1 ,..., x x

). In this case the discrete random variable is classified into two states, "in control" and "out of control". The in control states include planned or scheduled states and the out of control states include unplanned or unscheduled states. The system is said to be "in control", if the quantitative differences between expected and actual flows equal zero, and if not, the system is said to be "out of control". Therefore, the expected outcome value for this example is zero. The state definitions are illustrated in table 3.

Table 3: The State Definition

The next step is to compute the differences between expected and actual order quantities. Expected values are subtracted from actual values to define the differences (see also [START_REF] Sivadasan | An information-theoretic methodology for measuring the operational complexity of supplier-customer systems[END_REF]. All positive or negative differences between these two values are defined to be "out of control". A probability histogram of the data is created to analyse the complexity by indices. The differences are categorized within the chosen ranges. The ranges can be generally defined depending on the problem structure that is being addressed. In this example "+6 ≤ x ≤ +10", "+1 ≤ x ≤ +5", "-5 ≤ x ≤ -1" and "-10 ≤ x ≤ -6" are chosen as ranges (see table 4). After that, frequencies for each ranges and the probability of these frequencies are determined. Structural complexity is calculated by using equation (3). In order to define the structural complexity, all complexity values are added up (see structural complexity column in table 4). The probabilities that represent the "in control" state ) (P are used to define operational complexity (complexity index) by equation (4). The system is "in control" if the complexity is zero. System states which are "in control" reduce the complexity of the whole system. Therefore, equation ( 3) is modified by multiplying the factor ) 1 ( P with the sum of the weighted probability values of the "out of control" states which yields equation (4). If the results of table 2 are analyzed according to state effects, it can be observed that there is a weakness. I. e. two different ranges (for example the ranges "+6 ≤ x ≤ +13" and "-5 ≤ x ≤ -1") could have the same complexity value (0.46) because of the same probability value, but cannot have the same distance to the expected value (table 4). Obviously from a practical point of view, the larger the distance to the expected value the greater the complexity of the system will be. Therefore two additional formulas (equations ( 5) and ( 6)) are proposed including distance to expected value for structural and operational complexity measures. In this way, the more realistic result seems to be obtained as compared with the classical entropy measurement: While keeping basically the "under control" and "out of control" approaches of entropy, the different distances of states being "not under control" to the "under control" situation are explicitly included into the measures. Thus measures ( 5) and ( 6) allow also to measure relative improvements of a system, even if the portion of (truly) under control situations does not change but the "amount" of being out of control has reduced nevertheless. I. e. mathematically, the formulas have an additional parameter to cover the deviation value from the expected value. The mid-range of the each histogram cells are used as outcome ij d (deviation from the expected value for the state) for equations ( 5) and ( 6). In order to demonstrate the new proposed approach, the complexity measures of the customer-supply system, both structural and operational, are calculated using equations ( 5) and ( 6) and it is shown in table 5. The results in table 5 show that there are structural complexity of values 1.87 and 11.37 and complexity indices of 1.57 and 9.55 between expected and actual orders. I. e. there is a difference between classical and new structural complexity values because the distances from the expected value are not taken into consideration by the classical complexity measure. This argument can be explained by an example: The frequency value of the range "-5 ≤ x ≤ -1" is exchanged with the value of "-13 ≤ x ≤ -6" and complexity values are calculated again. Table 6 shows the results.

According to the classical measure the complexity value (1.87) remains unchanged although the frequency values are exchanged. But according to the new measure the complexity value changes because of the " ij d " effect. Therefore the new approach is proposed to obtain more meaningful results as compared with the classical approach. The classical complexity measure is able to indicate the controllability of the system, i. e. whether the system is "under control "or not. But it seems to be even more important to know how big the complexity, i. e. the 'amount of non-controllability', is. Therefore I propose the above measure to overcome the pure binary approach of 'under control' and 'out of control' by explicitly including a component into the complexity measure which maps a state's 'degree of being out of control'. Also from a cost perspective of complexity, the modified approach proposed here might be advantageous: If a state's distance from being under control has an influence on the complexity costs (e. g. higher penalty costs if a manufacturer is not able to deliver ordered products in time) then this should be regarded in the complexity evaluation of a system. Supposing no difference with respect to two states' frequency, the state with the further distance to the under control situation should be ceteris paribus considered first for complexity reduction approaches.

Conclusions and Future Work

Supply chains and supply chain management are important topics in the globalized world during the recent years. Therefore, analysis, measurement and reduction techniques of the increasing complexity of supply chains play an important economic role. In this paper the uncertainty of supply chain were measured based on the entropy method from a viewpoint of classical (Shannon's entropy measure) and new proposed approaches. The goal of this study is to give a formal approach which is able to measure the influence of the entropy measure on SCC environment. The results of the study seem to be interesting and meaningful. Shannon's entropy measure is used because it is simple and most widely used in uncertainty measurement. Of course, it is not the only measure for uncertainty or complexity respectively. Some other measurement methods could be studied in the future as well (such as Lyapunov exponent or fuzzy set theory).

The study presents a binary approach for classical measurement of complexity in supply chains. The classical entropy measure of SCC focuses whether the system is "under control" or "out of control". If the differences between actual and expected flow equal zero then the system is said to be "under control" and if not the system is "out of control". This study proposes a somehow different approach with respect to this aspect. It concentrates on predictability of a system and compares two models which are "more under control" than others. The system which has higher complexity (indicated by complexity index) should ceteris paribus be considered first with respect to complexity reduction as compared to the system with low complexity index. The more divergence to an expected value the greater the complexity. Therefore two additional formulas were developed that have an additional parameter to cover the range effect. While reducing complexity, the situations that are very far from situations of "under control" should be considered first and, if possible, reduced as compared with situations that are nearly "under control". The proposed new measure is in line with this view on complexity.

The classical entropy-based complexity measures, which are presented here, have been successfully applied and refined in industry by [START_REF] Sivadasan | An information-theoretic methodology for measuring the operational complexity of supplier-customer systems[END_REF]. However, regarding new proposed measures complexity will be also applied in industry in order to highlight its use in practice. Further research should be directed to more empirical work on the new proposed complexity measure in more detail.

Complexity can be associated with demand distortion up to supply chain from supplier to manufacturer. This effect is known as bullwhip effect in the literature. The new proposed entropy-based complexity measure can be used as a bullwhip measure as well. The future work will be concentrated on entropic complexity measure as a bullwhip metric.

F

  , four significant dimensions can be identified that drive complexity: namely size (number), diversity, variety and uncertainty.

Figure 1 :

 1 Figure 1: Complexity Flows in a Supply Chain

  to use the complexity measure (see table

Figure 2 :

 2 Figure 2: Supplier-Costumer System

Figure 3 :

 3 Figure 3: Graphic of Forecast and Actual Order (Example)

Figure

  Figure 1: Complexity Flows in a Supply Chain

  [START_REF] Deshmukh | Complexity in manufacturing systems, Part 1: Analysis of static complexity[END_REF]

	provided a static measure of complexity based on entropy method.
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	3

Table 1 :

 1 Some Possible Complexity Measure Variations by Supply Chain Flows (adopted from[START_REF] Sivadasan | Information Complexity as a Determining Factor in the Evolution of the Supply Chain[END_REF]

	Supply Chain Flows (Information / Material)	Measure Variations
		Requested Delivery -Confirmed Delivery
		Confirmed Delivery -Forecast Delivery
	Information	Confirmed Delivery -Provisional Delivery
		Scheduled Delivery -Forecast Delivery

Table 2 :

 2 Sample Data Collection for Expected and Actual Flows

Table 4 :

 4 Calculation of Structural and Operational Complexity

Table 5 :

 5 Calculation of Structural and Operational Complexity according to classical and new complexity measures

Table 6 :

 6 Calculation of Structural and Operational Complexity according to Frequency -Exchange

Table 1 :

 1 Some Possible Complexity Measure Variations by Supply Chain Flows (adopted from[START_REF] Sivadasan | Information Complexity as a Determining Factor in the Evolution of the Supply Chain[END_REF]

	Time

Table 2 :

 2 Sample Data Collection for Expected and Actual Flows

	State	Quantitative Differences		Definition
			(Forecast -Actual Order)
	"in control"		=0			No variation between the expected
	/ scheduled					and actual flows
	"out of control" /	>0 or <0		Positive or negative variations,
	non scheduled				which must be taken under control
	Table 3: The State Definition
				Forecast-Actual Order
	State Range	F o r Range	Frequency	Probability	H	Complexity/Entropy = = i j 1 1 M N ∑∑ -= ij s I p p 2 ) ( log	ij
	In Control		P 0	4		0,16	0
			e +6 ≤ x ≤ +13	5		0,20	0,46
	Out of Control	+1 ≤ x ≤ +5 -5 ≤ x ≤ -1	e r 7 5		0,28 0,20	0,51 0,46
	-13 ≤ x ≤ -6 Structural Complexity Operational Complexity (Complexity Index) 4 R e	0,16	0,42 1,87 1,57
					v i e
							w
							O n l
								y

Table 4 :

 4 Calculation of Structural and Operational Complexity

	Forecast -Actual Order
	Complexity/Entropy

Table 5 :

 5 Calculation of Structural and Operational Complexity according to classical and new complexity measures

						Forecast -Actual Order
	State Range											Complexity/Entropy
		Frequency Probability	H	I	(	s	)	=	-	∑∑ = = M i N j 1 1	p	ij	log	2	p	ij	H	II	(	s	)	=	-	M = i 1 ∑ ∑ N j 1 =	[ log	2	p	ij	] d	ij	p	ij
										(Classical)												(New)
	0 (in control)	4	0,16								0														0
	+6 ≤ x ≤ +13	5	0,20								0,46														4,41
	+1 ≤ x ≤ +5	7	0,28								0,51														1,54
	-5 ≤ x ≤ -1	4	0,16								0,42														1,27
	-13 ≤ x ≤ -6	5	0,20								0,46														4,41
	Structural Complexity F r Operational Complexity o (Complexity Index)									1,87 1,57														11,64 9,77
		P
		e
			e r
			R
						e
									v i e
											w
														O n l
																			y

Table 6 :

 6 Calculation of Structural and Operational Complexity according to Frequency -Exchange

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.ukInternational Journal of Production Research


Chih-Hsing Chu
email: chchu@ie.nthu.edu.tw

Cheng-Ta Lee

Kai-Wen Tien

Ching-Jung Ting

Yuan Ze

Efficient Tool Path Planning for 5-Axis Flank Milling of Ruled Surfaces using Ant Colony System Algorithms

Keywords: Flank Milling, 5-axis Milling 5-axis machining, flank milling, ant colony, ruled surface, machining error

5-axis CNC flank milling has recently received much attention in industry. The flank milling operation is efficient in shaping ruled geometry, but introduces a challenging task in machining error control. Previous work proposed a dynamic-programming based scheme for generating optimal tool path by minimizing the machining error. However, to compute the tool path takes a considerable amount of time. This paper presents a new scheme using meta-heuristics, Ant Colony System (ACS), for tool path planning in 5-axis flank milling, with a focus on improving the computation efficiency. The path planning problem is first formulated as mapping two boundary curves of a ruled surface. An ACS-based optimization algorithm is then applied to search for the mapping that minimizes the machining error. The solution is nearly as good as using dynamic programming but takes only half of the computational time. The results from machining experiment and 3D measurement validate the effectiveness of the proposed scheme.

In recent years, 5-axis CNC machining has been widely used in manufacturing industries like automobile, aerospace, energy, and molding components. This advanced machining technology is classified into two ways of operation: end milling and flank milling. The flank milling operation is more efficient in terms of machining efficiency. The machining shape that it can deal with is usually limited to ruled geometries. The tool path planning in 5-axis flank milling is considered a challenging task. Frequent occurrence of tool interferences and control of the machining error are two major difficulties. Effective solution to these problems has not yet been fully developed.

[Insert Figure 1 about here] As illustrated in Figure 1, a straight ball-end milling cutter sweeping along the boundary curves of a ruled surface induces tool interferences when the contact region is not locally developable [START_REF] Chu | Automatic Tool Path Generation for 5-axis Flank Milling based on Developable Surface Approximation[END_REF]. The majority of previous studies attempted to reduce the amount of such interferences with empirical methods applied to individual tool locations. [START_REF] Liu | Five-Axis NC Cylindrical Milling of Sculptured Surfaces[END_REF] displaced the cutter contact points with a small distance along the surface normal at the midpoint of a ruling. The line connected with the displaced points then determines the new cutter axis. The author claimed that setting the tool axis in this way produces a smaller machining error. [START_REF] Lee | Interference-Free Tool-Path Planning for Flank Milling of Twisted Ruled Surfaces[END_REF] developed a method for adjusting the cutter axis and the offset distance to the design surface such that the sum of the distances from sample points of the cutter axis to the surface is minimized. [START_REF] Bohez | A Geometric Modeling and Five-Axis Machining Algorithm for Centrifugal Impellers[END_REF] developed an optimization scheme that offsets the end points of the surface rulings to determine the tool orientations. The offset direction was chosen as the average of the surface normals at these points. Some recent studies fully utilized the two extra degrees of freedom in 5-axis machining.

They employed local optimization methods to adjust the tool axis until producing a smaller machining error [START_REF] Menzel | Triple Tangent Flank Milling of Ruled Surfaces[END_REF], or to re-position the cutter with look-up tables considering the surface twist [START_REF] Tsay | Accurate 5-Axis Machining of Twisted Ruled Surfaces[END_REF]. [START_REF] Monies | Five-axis NC Milling of Ruled Surfaces: Optimal Geometry of a Conical Tool[END_REF] positioned the cutter tangent to the ruled surface at three points, i.e. two points on two directrices and one point on a ruling. A tool axis is solved from a set of nonlinear transcendental equations. The interference errors on the two ends of the ruling are equal and thus minimized with the axis. [START_REF] Ding | On a Novel Approach to Planning Cylindrical Cutter Location for Flank Milling of Ruled Surfaces[END_REF] proposed a simple adaptive mesh algorithm to adjust cylindrical cutter location for flank milling of ruled surfaces in two steps. The first step is to determine a sequence of initial cutter locations by offsetting the grid sampled points based on semi-definite programming (SDP). The second step is to re-position the tool axis by adjusting the offset value of each However, these methods could not control the error amount of the machining surface as a whole.

The recent research [START_REF] Chu | Tool Path Planning for 5-Axis Flank Milling of Ruled Surfaces Considering CNC Linear Interpolation[END_REF] found that in 5-axis flank milling of ruled surface the local optima discretely scattered on the surface do not transform into a global optimum in consideration of CNC interpolation, i.e. they do not guarantee a smaller error amount in view of the entire surface. This finding motivates and justifies the research work on the tool path planning of 5-axis flank milling using a global optimization/adjustment approach. [START_REF] Wu | Optimized tool path generation based on[END_REF] converted the planning task into a curve matching problem and applied dynamic programming to generate optimal tool path by minimizing the total machining error. Their method offers an effective error control mechanism. However, it took a significant amount of time to compute the tool path. Not much flexibility exists in the tradeoff between the required computation time and the machining quality, thus restricting its practical use. This paper proposes a novel scheme for the tool path planning of 5-axis flank milling of ruled surfaces using a meta-heuristic algorithm, Ant Colony System (ACS). This work is the first attempt of applying meta-heuristics based optimization to 5-axis flank milling. The path planning task is transformed into the optimal mapping problem between two boundary curves. These curves are discretely sampled and any connection between the two set of sample points determines a tool location. A complete tool path consists of the sequence of the connections along which the cutter sweeps across the entire surface. An ACS-based optimization scheme is applied to search for the mapping that is globally optimal in reducing the machining error. A local search mechanism is also included to adaptively improve the path in local regions. A set of error simulations generated by a stock height method compares the performance of ACS, ACS with local optimization, and dynamic programming. The results indicate that both the ACS schemes provide solutions nearly as good as the dynamic programming approach. It however only requires half of the computational time. Finally, we conduct a set of machining experiments and measure the machined surfaces with a 3D coordinates measuring machine (CMM) to verify the effectiveness of the proposed method. This work provides a computationally efficient method for systematically reducing the machining error in 5-axis flank milling of ruled surfaces.

Optimization of 5-Axis Flank Milling

Preliminaries of Ant Colony System (ACS)

The idea of ant-based algorithms originated from the observation of ants' behaviors in nature [START_REF] Dorigo | Ant System: Optimization by a Colony of Cooperating Agents[END_REF] and gradually became a well-established research trend. Ants travel back and forth between two end points for delivering food.

When the ants encounter an obstacle during the trip, they find the paths to move around the obstacle and continue the trip. At first, the ants wander and randomly choose a path to circumvent the obstacle. After a certain period of time, the number of the ants passing the shorter path increases, as it takes less time to travel. The pheromone lay down by these ants taking on the shorter path tends to accumulate and less likely to evaporate. The ants that follow will thus have a higher probability to choose this better path.

The artificial ants in most ant-based algorithms have three common characteristics.

First of all, the ants have to remember the paths that they pass by for updating pheromone trails. Secondly, in addition to pheromone trails, they are able to use some heuristics to choose the path. Thirdly, the ants move at discrete time intervals in most applications rather than continuously. There are different variants in the ant-based algorithms [START_REF] Dorigo | Ant System: Optimization by a Colony of Cooperating Agents[END_REF]. Most of them consist of the following procedures:

(1) Solution construction: determine the probability for choosing all different paths.

(2) Pheromone update: the change of the pheromone trails on the traveled and unselected paths.

(3) Application of heuristic value (or visibility): use of other heuristic conditions for determining the probability in solution construction.

(4) Local optimization: adaptive tweaking of the optimal result locally in order to find better solution. The previous study [START_REF] Dorigo | Ant Colony Optimization[END_REF] reported that it is quicker to find optimal solutions by ACS compared to the original ant method. We thus develop an algorithm based on Ant Colony System (ACS) to find the optimal tool path from all possible mappings. The parameters involved in the algorithm are denoted as: The computational models of our ACS algorithm are defined as:

Solution construction:

(1)

where k i N indicates all next positions the k-th ant can choose at node i.

Pheromone update:

(2)

Parameters in the ACS Algorithm

The proposed optimization scheme contains three basis parameters, as shown in Table 1. A ruled surface is generally formed by linearly interpolating two boundary curves. The two boundary curves are discretely sampled in our scheme. Any connection between the two set of sample points determines a tool location, becoming

[ ] [ ] [ ] [ ] k i N j , k i N l ij ) t ( ij ij ) t ( ij k ij a ∈ ∀ ∈ β η α τ β η α τ = ∑ ∑ ∈ >      ∈ = = ≤      k i N l (t) il a (t) ij a (t) k ij p 0 q q when k i N j | (t) k ij a argmax j if 1 otherwise 0 k ij p 0 q q when U(0,1) q solution best the is j) (i, connection if (t) gb 1/f otherwise 0 (t) ∆τ (t) ∆τ ρ (t) τ ρ) (1 1) (t τ ij ij ij ij      = ⋅ + ⋅ - = + F o r P e e r R e v i e w O n l y
the "ideal" contact line of the cutter. In reality, the cutter protrudes or protracts the machined surface around the line due to the surface twist (see Figure 1). A complete tool path consists of the collection of the connections that can cover the entire surface.

The discrete points are sampled with equal parametric intervals. The parameters NDP 1 and NDP 2 control the sampling density of the two boundary curves, respectively.

[Insert Table 1 about here] Perhaps the simplest way to plan tool path in 5-axis flank milling is to let the cutter move along the surface rulings, i.e. to make use of all the sampling points and their connections in our case. The tool path thus generated is certainly not optimal in terms of minimizing the machining error. Positioning the cutter along the surface ruling may induce a larger amount of tool interference. Besides, it is not necessary that the cutter passes all the points. The machining error may be reduced by skipping some points. To utilize this potential advantage, we provide the parameter PS in our algorithm. It specifies the maximal number of the points skipped when connecting the sampling points. Every discrete point has a line connected to it when PS is set to zero.

At most 2 discrete points on the boundary curve are not being connected for PS = 2.

The third parameter CS in Table 1 places a constraint on the displacement of the to the point with the same index on the opposite curve; otherwise the tool will follow the surface rulings. However, it is also not practical to allow a point to be connected to another point much further to the current indexed position. There are two implications associated with this constraint. The cutting edge of a tool has certain length. The tool contact line during machining certainly cannot be longer than it.

Besides, the CS value confines the connections in a range, thus reducing the solution space of the possible paths. From a practical point of view, it is not possible that two connected points indexed very apart on each curve produces a smaller machining error.

ACS Algorithm for Tool Path Generation

The path planning task will be formulated in a way that can be solved by ACS algorithms. The two boundary curves are discretely sampled. The sampled points are then indexed and transformed to a discrete finite 2D coordinate system. The beginning and end positions are indexed as (0, 0) and (NDP 1 , NDP 2 ) respectively. The tool path can then be generated by connecting the nodes traveled through by the ants.

[Insert Figure 2 Given no explicit constraints, the whole solution space consists of, theoretically, any possible connection between the two set of discrete points. There are NDP 1 xNDP 2 possible points. The complexity increases with the sampling density.

Searching exhaustively in the whole solution space is not computationally feasible.

The proposed algorithm provides two parameters, PS and CS, for controlling the space size to be searched. As shown in Figure 2, a larger PS value allows more options to be considered for the next tool movement. The proposed ACS algorithm contains the following procedures (see Figure 3):

Step 1: Compute a look-up table to record the machining errors A look-up table is constructed to store the machining error values of all nodes based on the stock height method proposed by the previous work [START_REF] Wu | Optimized tool path generation based on[END_REF]. This is to avoid re-computing the machining error values during the optimization process. Note that the computation load required for the error estimation is greater than that for the optimization process in the current problem. The values of pheromone are initialized to 1 except for the unproceedable nodes, which are initialized to 0.

Step 2: Construct the path for ant k in the t-th iteration The iteration process begins. An ant is placed at the starting position. The probability for each proceedable node is then computed. The heuristic η ij (t) for Step 3: Compare X k and X ib Store the path constructed above in X k (the best solution of the ant k) and

compute f k . If f ib > f k , update X ib and f ib with X k and f k . If f ib <= f k , retain X ib and f ib for next iteration.
Step 4: Compare X k and X gb After all of the search by the ants in generation t is completed, compare f ib and

f gb . If f gb > f ib , update X gb and f gb with X ib and f ib . If f gb <= f ib , no update is carried out.
Step 5: Check the stop criterion If X gb remains un-changed for N generations, the search is ended, otherwise proceeds to next iteration.

[Insert Figure 3 about here] [Insert Figure 4 about here]

Local optimization

Generally speaking, meta-heuristic optimization is more computationally efficient than dynamic programming, as only part of the solution space will be 13 evaluated during the optimization process. The solution thus obtained is certainly a sub-optimal result. In addition, the optimum can have variances of some degree due to the probabilistic nature of the meta-heuristic algorithm. A local search mechanism is often included in ACS to improve the performance of the optimization process. We incorporate a similar mechanism to the original algorithm, which consists of the following steps:

(1) Randomly select a tool contact line from the optimal result X gb obtained by the original algorithm. Identify an altering area that contains M consecutive tool positions starting from the selected position for further improvement (See Figure 4(b)).

(2) Perform the original ACS-based search to attain an optimal path in the altering area, as shown in Figure 4(c).

(3) Update the corresponding path with the new one if the latter is better (see Figure 4(d)).

Machining Error Estimation

To optimize the tool path in 5-axis flank milling depends on effective estimation of the machining error. The major task in the error estimation is to compute the shape of the machined stock. It can be generated by subtracting the volume swept by the cutter along a tool path from the initial stock. However, to obtain the exact shape involves complex computations like envelop surface construction [START_REF] Lartigue | Tool Path Deformation in 5-Axis Flank Milling Using Envelope Surface[END_REF] and Boolean Operations. To save the computation load, this research adopts an approximate method developed by our previous study [START_REF] Wu | Optimized tool path generation based on[END_REF]. The schematic of the method is shown in Figure 5. The idea is to transform the stock shape from volumetric representation into lines sampled from the surface. Two line segments of a length equal to the cutter radius are created from each point, one along a user-given direction and the other along its reversed direction. Each group of lines represents the excess and gouge regions, respectively. A tool movement is approximated by n This section simulates the machining error of test surfaces under various conditions to validate the ACS algorithm. The machining error is estimated using the stock height method developed in our previous work [START_REF] Wu | Optimized tool path generation based on[END_REF]. The method transforms the stock geometry from volumetric representation into discrete heights at the sampling points of the machining surface. Two line segments are produced from each point, one along a user-given direction and the other along its reversed direction.

Intermediate tool motion is constructed by linear interpolation of the tool center point and the tool axis between consecutive cutter locations. The cutter intersects those line segments during the motion, thus updating the height of the intersected lines. The stock shape is approximated in this manner. Note that all the length units are mm in this section if not specified.

[Insert Figure 6 about here] [Insert Table 2 about here] Figure 6 shows a test ruled surface constructed with two cubic Bezier curves. The coordinates of the surface control points are also shown. Table 2 lists the parameters setting during the simulation. The performance of an ACS algorithm is closely related to four parameters: M ant , α, β, and ρ (see the definitions described in section 2.2).

There is no common agreement on how these parameters should be set. They are (1) M ant : as shown in Figure 7(a), the error converges as the number of ants increases. This is because the research space is expanded with more paths produced. As a result, it takes a longer time to compute the optimal solution. The plot shows that the convergence rate remains nearly unchanged when M ant > 500.

(2) α: we can see that α smaller than 4 produces a smaller error in Figure 7(b).

(3) β: Figure 7(c) shows that a smaller β value produces a smaller error.

(4) ρ: as shown in Figure 7(d), with a larger ρ value, the error curve converges more quickly but to a larger value. The error curve converges more slowly but to a smaller value with a smaller value. 3 about here] The above trials help us properly select the parameter values in the ACS algorithm. Table 3 shows a better setting in terms of both the convergence rate and the optimal value. This setting should produce a satisfactory result, although it is not the best combination of the parameters. Unless specified, these parameters remain unchanged in the subsequent optimizations.

Effectiveness of Local Search

The next step is to demonstrate the effectiveness of the local optimization mechanism discussed in Section 2. The simulation result is computed with the same test surface shown in Figure 6 and the parameters setting (Tables 2 and3) as the original algorithm. Figure 8 shows the error distributions with and without applying the local optimization in the tool path generation. Each optimization is conducted for 20 random trials. The error amount produced by each search varies due to the stochastic nature of ACS. The graphs indicate that the error distribution in both cases is close to a normal distribution. The local search mechanism is validated with the above discussion.

[Insert Figure 8 about here]

[Insert Table 4 about here]

Comparison with Dynamic Programming

The last test is to compare the result with that produced by dynamic programming. All the test conditions remain the same, including the machining surface (Figure 6) and the parameters setting (Table 2). The dynamic programming algorithm used for the comparison can be referred to the previous work [START_REF] Wu | Optimized tool path generation based on[END_REF]. The objective function in all cases is to minimize the total machining error. As shown in Table 5, both the ACS algorithms (with or without local search) produces an error value higher than that of the previous method. However, it takes less than half of [Insert Table 5 about here] Note that we choose β=1 in the tests above, although β=2 gives a slightly better result (see Figure 7). Since the ASC algorithm is a computational process that employs a degree of randomness as part of its logic, a single run result like in this case does not guarantee that β=1 outperforms β=2 or vise versa. Table 6 shows the comparison of both settings in 20 trial runs without local search. The average error with β=1 is slightly greater than that of β=2, but the former produces a smaller value of the maximum value. Its standard deviation is also smaller. 6 about here]

Machining Experiment

We conduct a 5-axis machining experiment to validate the effectiveness of our method on reducing the machining error. A test ruled surface is cut twice with different tool paths. In the experimental condition, the surface is to be cut with the tool path generated by the ACS algorithm proposed by this work. In the control condition, the same surface is to be cut with un-optimized tool path, in which the cutter follows the surface rulings. Figure 9 shows the rule surface used in the experiment (different from the one in Figure 6) and the coordinates of the control vertices of the boundary curves (both cubic Bezier curve). The parameter settings in the ACS algorithm remain the same as Table 2.

[Insert Figure 9 about here] Each contact line generates a cutter location in the following manner. As shown in Figure 1, the cutter center point is determined by offsetting the point on the B curve (the lower one) along the surface normal with a distance of the cutter radius.

Offsetting the point on the other curve (the A curve in this case) produces another point in 3D space. The cutter axis is along the direction determined by the two offset points. A tool path is fully specified, i.e. the CL (Cutter Location) file is manifested, once every cutter location of the path has been generated in the above manner. The CL file is then converted into machine-specific NC codes by a post processor (PP). Figure 10 shows the cutter contact lines generated by the ACS algorithms with and without the local search. The better path will be used in the subsequent machining experiment.

[Insert Figure 10 about here] The experiment is conducted on a 5-axis CNC machining center DECKEL-MAHO DMG 60T with an ITNC 530 controller. The computed tool paths are first generated in the CL format from a C++ program integrated with the modeling kernel ACIS. They are then converted into NC codes input to the controller by a post processor program. The tool used in the experiment is a 2-mm (radius) straight ball-end milling cutter. It is designed for deep machining with a large aspect ratio. The total length of the cutter is 30 mm and the cutting edge is of 20 mm. The stock material is Epoxy, which produces light cutting loads. Cutting fluids is thus not needed. The experiment consists of the following steps:

Stock preparation: design the stock shape so as to ease the fixturing task and Rough cut: the rough cuts are conducted with the same tool. The radial depth of cut is 2 mm in each tool path, offset from the surface geometry. The feed rate is 280 mm/min and the spindle speed is 14000 rpm. The depth of cut preserved for the finish cut is 0.5 mm.

Finish cut: a fresh tool is used for this machining operation. The feed rate is increased to 3000 mm/min. The spindle rate is 14000 rpm. The finished part is shown in Figure 11.

[Insert Figure 11 about here] The machined part is then measured with a Zeiss TM UMC 850 3D measuring machine (CMM). The stock geometry contains three mutually orthogonal planes, x-y, y-z, and x-z. They have been precisely machined at the stage of stock preparation. The intersection of the three planes determines the measurement reference point (see point is calculated as the distance between the actual position probed by the machine and the ideal value in CAD. To sum up the errors at all the points gives the machining error of the surface.

Table 7 shows the measurement result. The machining error in the experimental condition is approximately 51% of the error amount of the control condition. This validates the effectiveness of the ACS algorithm on improving the machining quality.

As shown in Figure 10, the machining error can be reduced by following non-ruling lines or properly skipping sampled points in certain surface regions. Figure 12 shows the distributions of the measured errors on the two finished surfaces along the u and v directions. Not only is the total machining error reduced, but the maximal tool interference at single tool location is also decreased from 0.174 mm to 0.136 mm, approximately 22%. They are both overcut in this case.

[Insert Table 7 about here] Note that the measured errors do not numerically match the simulated errors in both conditions. This is mainly because that the way the CMM measures the error does not exactly correspond to the error estimation in the optimization process. The probing density of the CMM, restricted by the machine resolution, is lower than that of the optimization. The sampling locations are also different on the surface. We can

Conclusion

5-axis flank machining offers a productive way for material removal of complex geometry. However, to control the machining error in the flank milling operation is difficult. Tool interference inevitably occurs in the tool contact regions that are locally non-developable. Most past studies adjusted individual cutter locations with heuristics or analytic methods for reducing the tool interferences. These "greedy" approaches may not produce minimal machining error due to CNC interpolation when considering the error of the entire machining surface. Tool path generation of 5-axis flank milling must thus take a holistic approach that minimizes the error globally rather than locally. This work is the first attempt that proposes a solution for this based on the ant colony algorithm. The path planning task is transformed into the optimal mapping problem between the boundary curves of a ruled surface. Any connection between the curves determines a cutter location and the machining error that the tool induces at the location. We then propose an optimization scheme based on Ant Colony System (ACS) to compute the optimal combination of such connections that minimizes the machining error on the surface. A local search mechanism is included to improve the result by applying the ACS scheme to some surface region randomly generated. The minimal error produced by the optimal tool path is only 3.5% higher than that produced by dynamic programming but takes only half of the computational time. A test ruled surface was cut twice with different tool paths to verify the effectiveness of the ACS scheme. 3D measurement result shows that the amount of the machining error is only 51% of that generated by the tool moving alone the surface rulings. The maximal tool interference at individual cutter location is also decreased by 22%. This work provides an effective and systematic method of reducing the machining error in 5-axis flank milling of ruled surfaces. Future work is to expand the solution space in the optimization by allowing the tool contact lines not to lie on the machining surface.

It is also of a good potential to incorporate parallel processing techniques with meta-heuristics for further improvement of computational efficiency.

  the designed surface according to the predicted cutting errors.

  both curves. A point on a boundary curve may not be connected

  about here]

  is equal to the inverse of the corresponding error between nodes i and j.

  intermediate tool positions generated by linear interpolation of the tool center point and the tool axis at each cutter location. The cutter intersects the line segments at each position, thus updating the lengths of the intersected lines. The material left in the excess region after machining indicates undercut while the material removed in the gouge region suggests overcut.

  based on trial and error. Statistics-based approaches offer a rigorous but time-consuming way for determining these parameters. For example, conducting the simulations with DOE (Design of Experiments) techniques provides a systematic approach to setting the parameters. The process requires a large amount of computation, though. Since this work is not focused on optimizing the ACS algorithm, we adopt a simpler method instead. The value of each parameter is varied while the other parameters remain constant. The results are shown in the following graphs. The vertical axis in the graphs indicates the machining error, which is estimated as the summation of all the stock heights after machining. The parameters are chosen as:

  . It is clear that adding local optimization help reduces the error mean and standard deviations. The optimization with the local search outperforms the original algorithm for all the trials in this case. Besides, the corresponding best and worst solutions are smaller. It is also worth noted that adding the local search does not significantly increase the computational time (see the comparison in the later section).

  . Applying the local search improve the tool path. The corresponding error is merely 1.3% greater than that produced by the dynamic programming method. More importantly, performing local search in the ACS algorithm does not introduce a significant increase on the computational time. The result shows that the ACS-based tool path planning is quite effective on tradeoff between the machining quality and the computation time spent on the tool path generation. Note that in the test the estimation of the objective function, i.e. the machining error, needs a much longer time than the search process in the optimization.

Figure 11 )

 11 Figure 11). It coincides the origin of the surface models in CAD. Each machined

  sampling conditions identical by decreasing the sampling density in the ACS algorithms, but doing so may deteriorate the optimum attained. The more sampling points in the error estimation, the closer to the actual machining error. From a practical point of view, it is not necessary to use the exact machining error as the objective in the optimization. An approximate error serves the purpose well as long as the machining error can be effectively reduced through the optimization process.[Insert Figure12about here]

Figure 1 :Figure 2 :Figure 5 :Figure 4 :Figure 7 Figure 8 :Figure 10 Figure 12 :

 1254781012 Figure 1: Machining error produced by 5-axis flank milling due to non-developability

ij (t):the heuristic other than pheromone trails for choosing paths • ρ:the evaporation rate of pheromone

	• •	X gb (t):global optimal solution f gb (t):the value of global optimal solution F o r
	•	P X ib (t):optimal solution in one iteration e
	•	f ib (t):the value of optimal solution in one iteration e r
	•	f k (t):the path traveled by ant k in the t-th iteration R
	•	τ ij (t):the amount of pheromone between nodes i and j in the t-th iteration, with e
		the initial value τ 0 at the beginning	v i e
				w
	•	P ij	k (t): the probability of ant k choosing node j when it is at node i in the t-th O n l
		iteration	y
	•	M ant : the number of total ants
	•	α: the weighting value for choosing pheromone trails
	•	β: the weighting value for choosing other heuristics
				8

• η

  Table 4 compares the means and the standard

Table 3 :

 3 Parameters setting in the ACS algorithms

	M ant α	β	ρ
	500 1.0 1.0 0.125

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.

uk International Journal of Production Research

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	44

Table 4 :

 4 Statistics of the machining errors with and without local search

		With local optimization Without local optimization
	Mean	9.554703	9.881245
	Std.	0.010711836	0.05976158
	Max.	9.56586	10.01235
	Min.	9.53432	9.87546

Table 6 :

 6 Performance comparison between the parameter settings β=1 and β=2

		β = 1	β = 2
	Mean	9.881245	9.826810
	Std.	0.05976158	0.0686151
	Max.	10.01235	10.74235
	Min.	9.87546	9.81335

Table 7 :

 7 Error measuring results

	Page 47 of 47
		Simulated error	Measured error
	Experimental condition	22.3946	10.8664
	Control condition	64.3416	21.3383

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.

uk International Journal of Production Research

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.ukInternational Journal of Production Research