서지주요정보
Heuristic algorithms for a military training timetabling problem = 신병 훈련 계획 시간표 작성을 위한 알고리듬 개발
서명 / 저자 Heuristic algorithms for a military training timetabling problem = 신병 훈련 계획 시간표 작성을 위한 알고리듬 개발 / Si-Young Lee.
발행사항 [대전 : 한국과학기술원, 2004].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8015039

소장위치/청구기호

학술문화관(문화관) 보존서고

MIE 04028

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

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개의 문제를 생성하여 테스트를 실시한 결과, 짧은 시간 안에 현실에서도 사용 가능할 정도의 좋은 해를 얻을 수 있었다.

서지기타정보

서지기타정보
청구기호 {MIE 04028
형태사항 41 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 이시영
지도교수의 영문표기 : Yeong-Dae Kim
지도교수의 한글표기 : 김영대
학위논문 학위논문(석사) - 한국과학기술원 : 산업공학과,
서지주기 Reference : p. 40-41
주제 TIMETABLING
EDGE COLORING
MILITARY
PROFESSOR LECTURER MODEL
HEURISTIC
시간표
신병 훈련
QR CODE qr code