Material at manual working spaces is often organized in inflexible gravity roller conveyers. With every change of product variant the totes have to be rearranged manually. The goal of the dFlow project is the automation of this task. This system is based on the N x N puzzle but allows for more than one blank and multiple batch movements of blanks. The current algorithm is too slow for larger systems. The objective of this thesis is to reduce calculation time by employing heuristic search.
Different heuristic searches, which have been successful for the N x N puzzle, are examined in regards to their suitability for the dFlow system. The most promising search is implemented. The implementation is analysed and the heuristics are extended to match the differences of the dFlow system to the N x N puzzle. The optimized heuristics and search algorithms are then evaluated.
The developed searches are similar in regards to their average calculation time. Those times depend on the initial configuration of the system. The developed approaches return nearly optimal solutions. However, calculations with non-admissible heuristics are faster but return longer solutions.
The thesis shows that heuristic search is a promising approach to reduce calculation time. Also, the large influence of blanks in this system is discussed. To exhaust the potential of heuristic search the behaviour of blanks has to be considered in future heuristics.
작업공간에서 필요한 재료는 주로 고정된 롤러 컨베이어 상에서 정렬되며, 다른 종류의 제품을 생산하기 위해서는 재료 혹은 부품 보관함이 수동으로 재정렬되어야 한다. 본 학위논문은 이러한 재료 공급 과정의 자동화를 목표로 하는 dFlow 프로젝트의 일환으로 진행되었다. 이 시스템은 N X N 행렬의 퍼즐로 구성되며, 한 개 이상의 공백을 포함하고 시스템 내에서 복수의 배치 이동이 가능하다. 본 학위논문은 휴리스틱을 이용하여 현재 대규모 시스템에 적용하기 어려운 현재 시스템의 연산 시간을 줄이는 것을 목표로 한다.
N X N 행렬에 적용 가능한 다양한 휴리스틱이 dFlow 시스템 적합성에 의해 평가되었다. 먼저 가장 발전성이 있는 탐색법들이 적용되었으며, 일반적인 N X N 퍼즐과 다른dFlow 시스템에 적용하기 위해 휴리스틱을 확장하였다. 이러한 과정으로 최적화된 휴리스틱과 탐색법이 최종적으로 평가되었다.
상기 과정으로 개발된 탐색법들은 비슷한 연산 속도를 보였다. 이 연산 속도는 초기 시스템 구성에 의존하며, 본 연구에서 개발된 접근법은 최적해에 가까운 값을 제공한다. 허용 불가능 휴리스틱을 사용해 계산할 경우 연산 속도는 빨라지지만 더 긴 해를 제공하게 된다.
본 연구를 통해 적용된 휴리스틱 탐색은 연산 시간 단축을 위해 효과적인 것으로 나타났으며, 이와 더불어 퍼즐 내 공백이 연산 결과에 미치는 영향에 대해 기술하였다. 휴리스틱 탐색을 향상시키기 위해서는 향후 연구에서 공백의 동작에 대한 연구가 이루어져야 한다.
