APPLICATION OF METAHEURISTIC ALGORITHMS TO MINIMIZE IDLE RUNNING LENGTH OF CUTTING TOOL
The paper deals with minimizing of idle running length of cutting tool which appears in CAD/CAM systems while generating control program of the CNC machine. We present problem model for standard cutting technology, i.e. one contour is cut by one continuous line without cutting tool shutdown and every contour contains the only incut point. Connection between presented problem and general traveler salesman problem with precedence conditions (GTSP+SOP) is shown. This problem is NP-hard one. In the view of complexity of the problem to be solved, to develop algorithm of cutting tool idle run length optimization three metaheuristics were choosen: Simulated Annealing (SA), Threshold Accepting (TA) and Great Deluge Algorithm (GD). Common scheme of solving given problem is suggested which contains of ten stages. To determine the most effective metaheuristic and check operability of algorithm we conduct computational experiment test cutting layout, which contains fifty three contours including inner ones. Timework of algorithm with different metaheuristics was synchronized and divided into two intervals: 3-5 seconds (quick route search), 10-15 (long route search). Experiments results show that algorithm based on GD constructed a shortest route on running length for both time intervals in a smaller time. It was pointed out what some steps of algorithm do not depend on SA, TA or GD usage, therefore algorithm can be easily adapted for other considered methods.