1、 In todays manufacturing environment, several industries are adapting flexible manufacturing systems （FMS） to meet the ever-changing competitive market requirements. CNC machines are widely used in FMS due to their high flexibility in processing a wide range of operations of various parts and compat
2、ibility to be operated under a computer controlled system. The overall efficiency of the system increases when CNC machines are utilized to their maximum extent. So to improve the utilization, there is a need to allocate the positions of cutting tools optimally on the tool magazines. The cutting too
3、ls on CNC machines can be changed or positioned automatically when the cutting tools are called within the part program. To do this turrets are used in CNC lathe machines and automatic tool changers （ATC） in CNC milling machines. The present model can be used either for the ATC magazines or turrets
4、on CNC machines. The indexing time is defined as the time elapsed in which a turret magazine/ATC moves between the two neighbouring tool stations or pockets. Bi-directional indexing of the tool magazine is always preferred over uni-directional indexing to reduce the non-machining time of the machine
5、. In this the magazine rotates in both directions to select automatically the nearer path between the current station and target station. The present work considers bi-directional movement of the magazine. In bidirectional indexing, the difference between the index numbers of current station and tar
6、get station is calculated in such a way that its value is smaller than or equal to half of the magazine capacity. Dereli et al. 1 formulated the present problem as a “traveling salesman problem” （TSP）, which is NP complete. They applied genetic algorithms （GA） to solve the problem. Dorigo et al. 2,
7、3 introduced the ant colony algorithm （ACA） for solving the NP-complete problems. ACA can find the superior solution to other methods such as genetic algorithms, simulated annealing and evolutionary programming for large-sized NP-complete problems with minimum computational time. So, ACA has been ex
8、tended to solve the present problem.2 MethodologyDetermination of the optimal sequence of manufacturing operations is a prerequisite for the present problem. This sequence is usually determined based on minimum total set-up cost. The authors 4 suggested an application of ACA to find the optimal sequ
9、ence of operations. Once the sequence of operations is determined, the following approach can be used to get the optimal arrangement of the tools on the magazine.Step 1 Initially a set of cutting tools required to execute the fixed （optimal） sequence of the manufacturing operations is assigned. Each
10、 operation is assigned a single cutting tool. Each tool is characterized by a certain number. For example, let the sequence of manufacturing operationsM1-M4-M3-M2-M6-M8-M9-M5-M7-M10 be assigned to the set of cutting tools T8-T1-T6-T4-T3-T7-T8-T2-T6-T5. The set of tools can be decoded as 8-1-6-4-3-7-
11、8-2-6-5. Here the manufacturing operation M1 requires cutting tool 8, M4 requires 1 and so on. In total there are eight different tools and thus eight factorial ways of tool sequences possible on the tool magazine. Step 2 ACA is applied as the optimization tool to find the best tool sequence that co
12、rresponds to the minimum total indexing time. For every sequence that is generated by the algorithm the same sequence of index positions （numbers） is assigned. For example, let the sequence of tools 4-6-7-8-2-5-3-1 be generated and hence assigned to the indexing positions 1-2-3-4-5-6-7-8 in the sequ
13、ential order, i.e. tool 4 is assigned to the 1st position, tool 6 to the 2nd position and so on.Step 3 The differences between the index numbers of subsequent cutting tools are calculated and then totaled to determine the total number of unit rotations for each sequence of cutting tools. Absolute di
14、fferences are to be taken while calculating the number of unit rotations required from current tool to target tool. This following section describes an example in detail. The first two operations M1 and M4 in the pre-assumed fixed sequence of operations require the cutting tools 8 and 1, respectivel
15、y. The tool sequence generated by the algorithm is 4-6-7-8-2-5-3-1. In this sequence tools 8 and 1 are placed in the 4th and 8th indexing positions of the turret/ ATC. Hence the total number of unit rotations required to reach from current tool 8 to target tool 1 is | 4-8 |= 4. Similarly the total n
16、umber of unit rotations required for the entire sequence is | 4-8 |+| 8-2 |+| 2-1 |+| 1-7 |+| 7-3 |+| 3-4 |+|4-5 |+| 5-2 |+| 2-6 |=30. Step 4 Minimization of total indexing time is taken as the objective function. The value of the objective function is calculated by multiplying the total number of u
17、nit rotations with the catalogue value of turret/ATC index time. If an index time of 4 s is assumed then the total index time required for the tool sequence becomes 120 s.Step 5 As the number of iterations increases ACA converges to the optimal solution.3 Allocation policy The following are the thre
18、e cases where the total number of available positions can be related with the total number of cutting tools employed. Case 1 The number of index positions is equal to the number of cutting tools Case 2 The number of index positions is greater than the number of cutting tools （a） without duplication
19、of tools, （b） with duplication tools Case 3 The number of index positions is smaller than the number of cutting tools If the problem falls into case 1, duplication of cutting tools in the tooling set is not required as the second set-up always increases the non-machining time of the machine. Table 1
20、 List of features and their abbreviationsIn case 2, the effect of duplication of cutting tools should be tested carefully. Most of the times the duplication of tooling is too expensive. Case 3 leads to finding the cutting tools to be used in the second set-up. However, other subphases are possible i
21、n cases 2（b） and 3. The duplicated tools may be used in such a way that no unloaded index is left on ATC or some indexing positions are left unloaded.Table 2 Operations assigned to the features4 Ant colony algorithmThe ant colony algorithm （ACA） is a population-based optimization approach that has b
22、een applied successfully to solve different combinatorial problems like traveling salesman problems 2, 3, quadratic assignment problems 5, 6, and job shop scheduling problems 7. This algorithm is inspired by the foraging behaviour of real life ant colonies in which individual ants deposit a substanc
23、e called pheromone on the path while moving from one point to another. The paths with higher pheromone would be more likely to be selected by the other ants resulting in further amplification of current pheromone trails. Because of this nature, after some time ants will select the shortest path. The
24、 algorithm as applicable to the present problem is described in the following section.It is assumed that there is k number of ants and each ant corresponds to a particular node. The number of ants is taken as equal to the number of nodes required to execute the fixed set of manufacturing operations.
25、 The task of eachant is to generate a feasible solution by adding a new cutting tool at a time to the current one, till all operations are completed. An ant k situated in state r moves to state s using the following state transition rule:Table 3 Cutting tools assigned to optimal sequence of operatio
26、ns Where （r, s） is called a pheromone level. （r, s）s are changed at run time and are intended to indicate how useful it is to make move s when in state r. （r, s） is a heuristic function, which evaluates the utilityof move s when at r. In the present work, it is the inverse of the number of unit rota
27、tions required to move from r to s.Parameter weighs the relative importance of the heuristic function. q is a value chosen randomly with uniform probability in 0,1, and q0 e0 q0 1T is a parameter. The smaller the q0, the higher the probability to make a random choice. In short q0 determines the rela
28、tive importance of exploitation versus exploration in Eq. 1.Jk（r） represents the number of states still to be visited by the k ant when at r.S is a random variable selected according to the distributiongiven by Eq. 2, which gives the probability with which an ant in operation r chooses s to move to.
29、 This state transition rule will favour transitions towards nodes connected by short edges with high amount of trail.4.1 Local updating rule While building a solution, ants change their trails by applying the following local updating rule:Where 0 represents the initial pheromone value.4.2 Global upd
30、ating rule Global trail updating provides a higher amount of trail to shorter solutions. In a sense this is similar to a reinforcement learning scheme in which better solutions get a higher reinforcement.Once all ants have completed their solutions, edges （r, s） belonging to the shortest solution made
