We suggest several algorithms for a military training timetabling problem (MTTP) that occurs in the Korea army. The MTTP is a generalized version of the professor-lecturer model that was considered for the first time in 1980. Professor-lecturer model is composed of several elements: classes, groups, professors that have only group-lectures and lecturers that have only individual-lectures. Unlike the typical professor-lecturer model, one needs to consider additional constraints to reflect restrictions in real situation, such as those for lunch time, duration of each lecture (2 hours and 4 hours), set-up time occurs between the lectures have different place for lecture (indoor and outdoor) and so on. Since this type of problem is known to be NP-hard, in this research, we propose heuristic algorithms to obtain a reasonably good solution in a reasonable amount of computation time. Since the MTTP is closely related with the edge-coloring problem of a bipartite graph, which is the problem of minimizing the number of colors to color all edges in such a way that adjacent edges receive different colors, we use results of previous research on the graph theory. We present three algorithms including four edge-ordering rules for finding a solution on a bipartite graph, and each edge-ordering rule has weight factors concerned about types of teachers and places for lectures. Results of a series of computational experiments show that the suggested algorithms give good schedules in a reasonably short time and that they can be applied to the real situation.
이 논문에서는 현재 육군 훈련소에서 발생할 수 있는 신병 훈련 시간표 작성 문제를 해결하기 위한 알고리듬을 제시하고 있다. 이 논문에서 다루고 있는 신병 훈련 시간표 작성 문제는 teacher들의 구성이나, class 구성 측면에서 이 전에 제시된 professor-lecturer 모델과 상당히 흡사한 점을 많이 가지고 있다. 결국, 이 기본적인 professor-lecturer 모델에 실 상황에서 발생하는 특수한 제약을 첨가한 형태의 문제로 볼 수 있다. 점심 시간, 날짜 변경, 강의 장소, 단위강의 시간 등의 추가적인 고려사항들을 그 예로 들 수 있겠다. 이러한 형태의 문제는 NP-hard 인 것으로 잘 알려져 있어, 이 논문에서는 문제를 해결할 수 있는 3가지 탐색적 기법의 알고리듬을 제시하였다.
흔히 시간표 작성(Timetabling) 문제는 bipartite 그래프의 edge coloring 문제와 깊은 연관성을 가지고 있다. Edge Coloring 문제는 인접한 edge가 서로 다른 색깔을 가지도록 색을 칠하는 문제이며, 가장 적은 수의 색깔로 모든 edge를 위의 조건이 만족하도록 칠하는 문제이다. 이런 그래프와 관련한 이전의 연구결과를 사용하기 위해서 시간표 작성 문제를 Edge Coloring 문제로 변환하여, 그래프 상에서 문제를 해결하는 알고리듬을 개발하였다. 또한, 이 알고리듬에는 좀 더 좋은 해를 구하기 위한 edge ordering rule과 가중치 등의 추가적인 요소들이 포함되어 있다. 마지막으로 이런 알고리듬을 평가하기 위해 실제 발생할 수 있는 형태의 문제들과 일반화 시킨 형태의 문제들에 대해서 각각 200개의 문제를 생성하여 테스트를 실시한 결과, 짧은 시간 안에 현실에서도 사용 가능할 정도의 좋은 해를 얻을 수 있었다.
