In this paper, we consider the cutting sequencing problem arising in a steel cutting process within a shipbuilding company. Given a set of lines to be cut, precedence constraints are imposed on them and some cutting lines have constraints on their cutting directions because of the heat generated during the cutting operation. Under these constraints, we consider the problem of deciding the cutting directions and sequence, minimizing the total moving time of the cutting robot.
This problem can be modeled as the precedence constrained traveling salesman problem (PCATSP), which has been well-studied among the precedence related problems. We present an integer programming (IP) model for our problem. Though the model has integer variables and exponentially many constraints, it can be solved efficiently by branch-and-cut (B&C) algorithm. B&C algorithm works by solving linear programming (LP) relaxations using cutting planes in the branch-and-bound tree. To solve LP relaxations, we use some valid inequalities known to be most efficient from the literature to get feasibility and improve integrality.
We test our algorithm on randomly generated test problems. The computational results show that our problem can be solved to optimality in a very reasonable time by branch-and-cut algorithm.
본 논문은 조선소의 강재절단공정에서 생기는 절단경로를 결정하는 문제를 다룬다. 강재 위에 절단선들의 위치가 정해져 있을 때, 절단시 발생되는 열로 인해 절단선들간에 우선순위가 생기고, 어떤 절단선들으 특정한 절단방향을 갖게 된다. 이러한 제약아래, 절단로봇의 총 이동시간을 최소로 하면서 절단선들의 절단방향과 절단순서를 결정하는 것이 우리가 다루는 문제이다.
위 문제는 우선순위가 있는 외판원문제로 모델링 될 수 있다. 우리는 우선순위가 있는 절단경로문제의 모형을 기반으로 우리의 절단경로문제에 대한 정수계획 모형을 제시한다. 변수들은 정수값을 가지고 제약식은 지수적으로 많이 존재하지만, 분지절단법을 사용해서 효율적으로 해를 구할 수 있다. 랜덤하게 만든 테스트 문제에 대한 실험결과, 최적해를 빠른 시간 내에 구할 수 있었다.
