Earticle

초록

영어

The equitable partitioning problem(EPP) is classified as [0/1] binary skill existence or nonexistence and integer skill levels such as [1,2,3,4,5]. There is well-known a polynomial-time optimal solution finding algorithm for binary skill EPP. On the other hand, tabu search a kind of metaheuristic has apply to integer skill level EPP is due to unknown polynomial-time algorithm for it and this problem is NP-hard. This paper suggests heuristic greedy algorithm with polynomial-time to find the optimal solution for integer skill level EPP. This algorithm descending sorts of skill level frequency for each field and decides the lower bound(LB) that more than the number of group, packing for each group bins first, than the students with less than LB allocates to each bin additionally. As a result of experimental data, this algorithm shows performance improvement than the result of tabu search.

한국어

동등분할 문제(EPP)는 학생이 특정 분야에 대한 경험 유무인 [0/1]이진수 형태를 갖는 경우와 [1,2,3,4,5]와 같은 정수형의 기량 수준을 갖고 있는 문제로 분류된다. 이진수형 EPP에 대해서는 다항시간으로 최적 해를 구하는 알고리즘 이 알려져 있다. 반면에, 정수형 기량 수준을 갖는 EPP에 대해서는 다항시간으로 해를 구하는 알고리즘이 존재하지 않아 아직까지는 메타휴리스틱의 일종인 타부탐색법만이 알려져 있는 난제이다. 본 논문은 NP-난제인 정수형 기량 수준을 갖는 EPP에 대해 다항시간으로 해를 찾아가는 규칙을 가진 휴리스틱 탐욕방법을 제안한다. 제안된 알고리즘은 각 분야 의 기량 수준별 빈도수 내림차순으로 그룹 수를 충족하는 하한치(LB)를 구하고, LB 이상인 기량수준을 가진 학생들을 각 그룹 상자에 우선하여 채우고, LB 이하 기량수준을 가진 학생들을 추가로 각 상자에 배분하는 방법을 제안하였다. 제안된 알고리즘을 실험 데이터에 적용한 결과 기존의 타부탐색법으로 구한 결과를 개선하는 효과도 얻었다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 동등분할 문제의 성능평가기준
Ⅲ. 상자 채우기 알고리즘
Ⅳ. 알고리즘 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380