지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2013.8
- 수록면
- 9 - 16 (8page)
- DOI
- 10.14801/kiitr.2013.11.8.9
이용수
초록· 키워드
오류제보하기
일반적으로 상자포장 문제는 다항시간으로 근사 해를 찾는 알고리즘만이 존재하여 NP-완전 문제로 알려져 있다. 본 논문은 선형 상자문제의 정확한 해를 다항시간으로 찾을 수 있는 알고리즘을 제안한다. n개 물품의 물품 크기 a<SUB>i</SUB>, (i=1, 2, …)를 내림차순으로 정렬시켜 용량이 C인 필요한 상자 수 k의 약 75% 상자들에 ?0.5C≤a<SUB>i</SUB>?개의 물품을 순서대로 1개씩 넣고, 나머지 물품을 찾아 넣는 방법으로 문제를 25%로 단축시켰다. 나머지 필요한 상자 25%에 대해서도 유사한 방법으로 물품을 채우는 방법을 적용하였다. 제안된 알고리즘을 OR-LIB의 120, 250과 500개의 데이터에 적용한 결과 100% 정확한 해를 얻는데 성공하였다. 제안된 알고리즘은 상자 포장 문제가 P-문제임을 증명하였으며, NP-완전으로 알려진 멀티프로세서 스케쥴링 문제에도 적용할 수 있을 것이다.
목차
요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 연구 배경
Ⅲ. 선형 상자포장 알고리즘
Ⅳ. 알고리즘 적용성 평가
Ⅴ. 결론 및 향후 연구과제
References
참고문헌 (11)
참고문헌 신청
1. [인터넷자원] - Wikipedia / / http://en. wikipedia.org/wiki/Bin_packing_problem
2. [단행본] - Mathworld Team / 2013 / Bin Packing Problem / Wolfram Research Inc
3. [인터넷자원] - Wikipedia / / Multiprocessor Scheduling
4. [학술지(정기간행물)] - J. E. Beasley / 1990 / OR-Library : Distributing Test Problems by Electronic Mail / Journal of the Operational Research Society 41 (11) : 1069 ~ 1072
7. [인터넷자원] - Wikipedia / / Cutting Stock Problem
2. [단행본] - Mathworld Team / 2013 / Bin Packing Problem / Wolfram Research Inc
3. [인터넷자원] - Wikipedia / / Multiprocessor Scheduling
4. [학술지(정기간행물)] - J. E. Beasley / 1990 / OR-Library : Distributing Test Problems by Electronic Mail / Journal of the Operational Research Society 41 (11) : 1069 ~ 1072
7. [인터넷자원] - Wikipedia / / Cutting Stock Problem
이 논문의 저자 정보
이 논문과 함께 이용한 논문
컨테이너 사전정렬 문제의 스택 상자 채우기 알고리즘
이상운
한국컴퓨터정보학회논문지
2015
.10
병렬 일괄처리기계의 작업종료시간 최소화 문제의 최장 처리시간 우선 상자 채우기 알고리즘
이상운
한국정보기술학회논문지
2016
.07
상자 채우기 문제를 위한 새로운 유전자 알고리즘
조병헌
,
정성훈
,
김기형
외 2명
한국정보과학회 학술발표논문집
1999
.04
타부서치를 이용한 2차원 직사각 적재문제에 관한 연구
이상헌
,
이정민
경영과학
2005
.05
크기가 다양한 bin-packing 문제에 대한 algorithm
강장하
,
박성수
한국경영과학회 학술대회논문집
2000
.01
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2014-560-002879809