In this thesis, we focus arc welding robot-scheduling problem considering heat-caused distortion with the objective of minimizing total cycle time. Since this problem is known as a special case of (with additional constraints) traveling salesman problem, it is difficult to solve within a polynomial time. Therefore, we develop a heuristic algorithm for finding the schedule-information in which total cycle time is minimized within a polynomial time. The heuristic is a two-phase method which combines tour construction phase and tour improvement phase. To evaluate its performance, we compare the proposed heuristic with the existing heuristics after modification that is necessary in the problem. Computational results based on randomly generated problems show that the proposed heuristic dominates all those existing heuristics.
본 논문은 열변형을 고려한 아크 용접 로봇의 스케줄링에 대한 연구이다. 용접선을 용접하고 나면 용접선 주위에는 열구간이 생긴다. 이 열구간이 충분히 식기전에 열구간에 걸쳐있는 다른 용접선을 용접하면 열변형이 생길 가능성이 있다. 이를 방지하기 위해 열구간이 충분히 식을 시간이 필요하다. 이러한 문제를 고려한 아크 용접 로봇의 작업시간 최소화가 본 논문의 목적이다. 이와같은 문제는 외판원 순회 문제라 할 수 있고 외판원 순회 문제는 풀기 어려운 문제기 때문에 휴리스틱을 제안한다.
제안된 휴리스틱은 일반적인 외판원 순회 문제의 휴리스틱처럼 2단계 휴리스틱이다. 1단계는 전체 작업 순서 형성 단계이고 2단계는 향상 단계이다. 제안된 휴리스틱의 성능을 평가하기 위해 작은 문제에 대해선 최적해와 비교를 하였고 큰 문제에 대해선 기존 외판원 순회 문제 휴리스틱들과 비교하였다. 그런데 본 문제와 외판원 순회문제가 동일한 문제가 아니므로 기존 외판원 순회 문제의 휴리스틱들을 문제에 맞게 수정하였다. 최적해와 비교하고 이들 휴리스틱과 비교했을 때 제안된 휴리스틱이 좋은 결과를 나타냈다.