Iterative Algorithm for the Generalized Segmental Continuous Cutting Problem with Optimization Time Constraint

The paper proposes a new algorithm for solving one class of the tool path problems for CNC sheet cutting machines (the generalized segmental continuous cutting problem, GSCCP) with an additional parameter limited the calculation time for finding an optimal solution. As input data in the GSCCP, 2D layout of nested parts and a finite set of subtasks for optimizing the cutting path are used. Each subtask contains a set of so-called basic cutting segments, which determine the trajectories of tool movement between the points for material piercing and the points for switching tool off. Each subtask can be solved independently within the specified calculation time. The best solution found for the all subtasks is a solution to the GSCCP problem. The proposed iterative algorithm involves quantizing the total computation time. Moreover, within each time quant, all subtasks are also solved sequentially by calculation the upper and lower bounds. Initial upper bounds can, for example, be obtained using any fast heuristic based on effective combinatorial optimization methods. Next, for each of them, the procedure for searching for the lower boundary is launched. The next iteration of the solution process is performed taking into account the adjusted bounds. The solution procedures are interrupted when the specified time quant is reached, or upon obtaining a guaranteed exact solution. The effectiveness of the algorithm is illustrated by practical examples. It is also shown that for generate a set of finite set of subtasks for GSCCP, it is advisable to use neural networks.