earticle

논문검색

IT 경영 및 정책

기량수준 동등분할 문제의 상자 채우기 알고리즘

원문정보

Bin Packing Algorithm for Equitable Partitioning Problem with Skill Levels

이상운

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

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. 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과

참고문헌

자료제공 : 네이버학술정보

    함께 이용한 논문

      ※ 기관로그인 시 무료 이용이 가능합니다.

      • 4,000원

      0개의 논문이 장바구니에 담겼습니다.