Multi-objective optimisation of tool indexing problem: a mathematical model and a modified genetic algorithm

Figures & data

Table 1. Summary of research performed to address tool-indexing problems.

								Number of objectives
study	Tool Duplicate	Empty Index	Tool Wear	Mathematical Model	Solution Approach	TIP	ToSP	SOO	MOO
Dereli et al. (1998)					GA	o		o
Dereli and Filiz (2000)					GA	o		o
Baykasoğlu and Dereli (2004)	o				SA	o		o
Gopala and Rao (2006)		o			AC	o		o
Baykasoğlu and Ozsoydan (2016)	o				SA,VNS	o		o
Baykasoğlu and Ozsoydan (2017)	o	o			SA	o	o	o
Baykasoğlu and Ozsoydan (2018)	o	o			SA	o	o	o
Atta, Sinha Mahapatra, and Mukhopadhyay (2019)		o		o	HS	o		o
Amouzgar, Ng, and Ljustina (2020)	o	o	o		GA	o		o
Palubeckis (2020)		o			SA,VNS	o		o
This study	o	o	o	o	GA	o			o

Note: Genetic algorithm (GA), simulated annealing (SA), ant colony (AC), harmony search (HS), tool-indexing problem (TIP), tool-switching problem (ToSP), single-objective optimisation (SOO), multi-objective optimisation (MOO), variable neighbourhood search (VNS).

Figure 1. Tool indexing on an 8-index turret magazine (Dereli and Filiz 2000).

Figure 2. (a) Turret magazine with 45 index positions used in OP30; (b) schematic of OP30 turret.

Table 2. OP30 operations with required tools and tool life (i.e. the number of crankshafts each tool can machine before complete wear out).

Operation number	O1	O2	O3	O4	O5	O6	O7	O8	O9	O10
Tool number	T1	T2	T6	T5	T7	T5	T6	T7	T4	T3
Tool life	145	131	326	326	326	326	326	326	131	326

Figure 3. Factory-settings-based tool allocation on 45-index turret.

Table 3. Number of duplicates for each tool and magazine-index positions allocated to each tool based on the current factory settings.

Tool No.	No. of Duplicates	Index positions
T1	9	1,3,5,8,12,16,20,24,28
T2	10	2,4,6,10,14,18,22,26,30,32
T3	4	7,19,21,33
T4	10	9,11,13,15,17,23,25,27,29,31
T5	4	34,36,40,42
T6	4	35,37,41,43
T7	4	38,39,44,45

Table 4. TIP sets and their definitions.

Sets	Definition
$t:1,\dots ,NT$	Tool index
$s,s^{\mathrm{\prime }}:1,\dots ,NS$	Slot index
$o:1,\dots ,NO$	Operation index
$p:1,\dots ,NP$	Part index

Table 5. TIP parameters and their definitions.

Parameters	Definition
NT:	Number of tools
NS:	Number of slots
NO:	Number of operations
NP:	Number of parts
$l_t$:	Tool life of tool t
$du{p}_t$:	Duplication of tool t
$f{o}_{ot}$:	$\left\{\begin{array}{l}1:\text{if operation o uses tool t}\\ 0;\text{otherwise}\end{array}\right.$
$y_{st}^c$:	$\left\{\begin{array}{l}1:\text{if tool t is placed on slot s in current magazing status}\\ 0;\text{otherwise}\end{array}\right.$
$d(s,s^{\mathrm{\prime }})$:	minimum number of rotations between slot s and $s^{\mathrm{\prime }};min\left\{\right|s^{\mathrm{\prime }}-s|,|s+NS-s^{\mathrm{\prime }}\left|\right\}$

Table 6. TIP decision variables and their definitions.

Decision variables	Definition
$y_{st}$:	$\left\{\begin{array}{l}1:\text{if tool t is placed on slot s}\\ 0;\text{otherwise}\end{array}\right.$
$z_{pos}$:	$\left\{\begin{array}{l}1:\text{if operation o uses slot s for machining part p}\\ 0;\text{otherwise}\end{array}\right.$

Table 7. Operations with required tools and tool life (i.e. the number of parts each tool can machine before complete wear out).

Operation Number	O1	O2	O3	O4	O5
Tool number	T2	T3	T4	T1	T2
Tool life	4	6	12	6	4

Table 8. Number of duplicates for each tool and magazine-index positions allocated to each tool based on the settings illustrated in Figure 1.

Tool no.	No. of duplicates	Index positions
T1	2	1,2
T2	3	4,5,8
T3	2	3,6
T4	1	7

Figure 4. Solutions in the objective space for the 8-index turret magazine solved by the mathematical model.

Figure 5. Flowchart of the SPEA2 algorithm.

Figure 6. Solution representation of 8-index turret magazine depicted in Figure 1.

Figure 7. Solution representation of current tool-allocation strategy pertaining to the 45-index turret used in factories.

Figure 8. Calculating value of second objective function (NoC) for a random solution.

Figure 9. Illustration of environmental selection operator when the archive is too small (first scenario) for 45-index tool magazine with $\overline{N}=50$, and $\left|{\overline{P}}_{t+1}\right|<50$: (a) $\left|{\overline{P}}_{t+1}\right|=16$; i.e. the 16 non-dominated solutions shown in this figure are first copied to ${\overline{P}}_{t+1}$; (b) missing NoC solutions and 22 solutions indicated by stars are added to ${\overline{P}}_{t+1}$, thereby increasing archive size to $\left|{\overline{P}}_{t+1}\right|=16+22=38$; (c) remaining $50-38=12$ solutions are chosen from the best-dominated solutions in the multi-set ${\overline{P}}_t+{\overline{P}}_{t+1}$ and added to the archive (indicated by diamonds); hence $\left|{\overline{P}}_{t+1}\right|=50$.

Figure 10. Customised crossover-repair operator used in the simple 8-index turret-magazine case described in Figure 1. (a) Best indexing route of the two parents is swapped. whilst maintaining other indexes constant. (b) Repair process for second offspring.

Figure 11. Mutation operation wherein index positions of the first instance of two random tools not participating in the crossover process are swapped to creating fitter offspring.

Figure 12. Two-hundred random initial solutions generated by executing an m-SPEA2 run.

Figure 13. Hypervolume for minimisation of MOOP considered in this study with Nadir point as reference Amouzgar et al. (2019).

Figure 14. Non-dominated solutions in the objective space forming the Pareto front.

Figure 15. Tool allocation and improvement of non-machining time for 4 non-dominated solutions marked in Figure 14. Tool positions that remain unchanged compared to the current factory setting are marked by dark backgrounds. (a) solution a; (b) solution b; (c) solution c; (d) solution d.

Table 9. Results for four different non-dominated solutions marked in Figure 14.

Solution	NoC	Total no. of rotations	Rotation per part	Non-machining time per part (s)
a	0	58,398	$\sim 45$	$\sim 9$
b	36	18,421	$\sim 14$	$\sim 2.8$
c	6	38,085	$\sim 29$	$\sim 5.8$
d	12	27,909	$\sim 21$	$\sim 4.2$

Figure 16. Number of unit rotations required to execute OP30 throughout the lifespan of 45-index turret magazine under two extreme solutions (marked by a and b in Figure 14).

Figure 17. Non-dominated solutions in decision space illustrated as heat-map plot with each row representing a solution (optimum tool allocation). Small boxes represent magazine indexes, and tools placed at given index locations are marked by the tool number in the box. Triangles indicate similar tool-allocation sequences shared by several solutions.

Table A1. Levels of m-SPEA2 parameters used in Taguchi design.

Parameter levels	N	${\rho }_{\mu }$
1	50	0.1
2	100	0.2
3	150	0.3

Figure A1. Plots obtained via Taguchi analysis for (a) Means; (b) SN ratio.

Dereli, T., A. Baykasoğlu, N. Gindy, and I. Filiz. 1998. “Determination of Optimal Turret Index Positions by Genetic Algorithms.” In Proceedings of 2nd International Symposium on Intelligent Manufacturing Systems, Vol. 2, 743–750.

 Google Scholar

Dereli, T., and I. H. Filiz. 2000. “Allocating Optimal Index Positions on Tool Magazines Using Genetic Algorithms.” Robotics and Autonomous Systems 33 (2): 155–167. doi: 10.1016/S0921-8890(00)00086-5

 Web of Science ®Google Scholar

Baykasoğlu, A., and T. Dereli. 2004. “Heuristic Optimization System for the Determination of Index Positions on CNC Magazines with the Consideration of Cutting Tool Duplications.” International Journal of Production Research 42 (7): 1281–1303. doi: 10.1080/00207540310001622557

 Web of Science ®Google Scholar

Gopala, A., and K. K. M. Rao. 2006. “Optimal Allocation of Index Positions on Tool Magazines Using An Ant Colony Algorithm.” The International Journal of Advanced Manufacturing Technology 30: 717–721. doi: 10.1007/s00170-005-0099-5

 Web of Science ®Google Scholar

Baykasoğlu, A., and F. B. Ozsoydan. 2016. “An Improved Approach for Determination of Index Positions on CNC Magazines with Cutting Tool Duplications by Integrating Shortest Path Algorithm.” International Journal of Production Research 54 (3): 742–760. doi: 10.1080/00207543.2015.1055351

 Web of Science ®Google Scholar

Baykasoğlu, A., and F. B. Ozsoydan. 2017. “Minimizing Tool Switching and Indexing Times with Tool Duplications in Automatic Machines.” The International Journal of Advanced Manufacturing Technology 89 (5-8): 1775–1789. doi: 10.1007/s00170-016-9194-z

 Web of Science ®Google Scholar

Baykasoğlu, A., and F. B. Ozsoydan. 2018. “Minimisation of Non-machining Times in Operating Automatic Tool Changers of Machine Tools Under Dynamic Operating Conditions.” International Journal of Production Research 56 (4): 1548–1564. doi: 10.1080/00207543.2017.1357861

 Web of Science ®Google Scholar

Atta, S., P. R. Sinha Mahapatra, and A. Mukhopadhyay. 2019. “Solving Tool Indexing Problem Using Harmony Search Algorithm with Harmony Refinement.” Soft Computing 23 (16): 7407–7423. doi: 10.1007/s00500-018-3385-5

 Web of Science ®Google Scholar

Amouzgar, K., A. H. Ng, and G. Ljustina. 2020. “Optimizing Index Positions on Cnc Tool Magazines Considering Cutting Tool Life and Duplicates.” Procedia CIRP 93: 1508–1513. doi: 10.1016/j.procir.2020.03.044

 Google Scholar

Palubeckis, G. 2020. “An Approach Integrating Simulated Annealing and Variable Neighborhood Search for the Bidirectional Loop Layout Problem.” Mathematics 9 (1): 5. doi: 10.3390/math9010005

 Web of Science ®Google Scholar

Amouzgar, K., S. Bandaru, T. Andersson, and A. H. C. Ng. 2019. “Metamodel-based Multi-objective Optimization of a Turning Process by Using Finite Element Simulation.” Engineering Optimization 52 (7): 1–18.

 Web of Science ®Google Scholar