서지주요정보
회전을 고려한 2차원 상자 채우기 문제에 대한 새로운 개미 군집 알고리즘 = A new ant colony algorithm for the 2-dimensional bin packing problem with rotations
서명 / 저자 회전을 고려한 2차원 상자 채우기 문제에 대한 새로운 개미 군집 알고리즘 = A new ant colony algorithm for the 2-dimensional bin packing problem with rotations / 현도경.
저자명 현도경 ; Hyun, Do-Kyung
발행사항 [대전 : 한국과학기술원, 2012].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8023670

소장위치/청구기호

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

MIE 12012

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

The two-dimensional bin-packing problem (2D-BPP) with rotations is an important optimization problem which has a large number of practical applications. It consists of the non-overlapping placement of a set of rectangular pieces in the lowest number of bins of a homogenous size, with the edges of these pieces always parallel to the sides of bins, and with free 90 degrees rotation. A large number of methods have been proposed to solve this problem, including heuristic and meta-heuristic approaches. In this thesis, we presents a new heuristic algorithm to solve the 2D-BPP that incorporates ant colony algorithm specially designed for this problem. The performance of this algorithm is compared with other heuristics previously proposed by other authors in ten classes of frequently used benchmark problems. It is observed that, in some cases, the method here proposed is able to equal or even outperform to the results of the other two heuristics in most test problems.

2 차원 상자 채우기 문제 (The two-dimensional bin-pacing problem; 2D-BPP)는 사각형 아이템들과 동일한 면적의 사각형 상자들이 주어질 때, 상자들 안에 모든 아이템들이 서로 겹치지 않고 쌓일 수 있는 최소의 상자 개수를 찾는 문제이다. 또한 본 논문에서는 아이템의 회전을 고려하므로 상자에 아이템이 쌓일 때 90˚회전이 가능하다. 2D-BPP 는 목재 산업에서의 규격화된 크기로 자르는 작업, 철판과 유리 산업, 선반이나 트럭 그리고 창고에서 물건 쌓는 일, 그리고 신문 등에서 기사들을 배치하는 일 등의 재질을 자르거나 제품을 쌓는 산업에서 많이 응용되고 있으며, 이 문제를 해결하기 위해 많은 휴리스틱과 메타 휴리스틱 알고리즘들이 소개되어 왔다. 본 논문에서는 2D-BPP 를 해결하기 위한 새로운 휴리스틱 알고리즘을 제안했고, 이 휴리스틱의 성능 향상을 위하여 새롭게 변형시킨 개미 군집 알고리즘을 적용하였다. 새롭게 제안된 개미 군집 알고리즘의 성능을 객관적으로 측정하기 위해서 다른 논문들에서 제안된 알고리즘들에 빈번하게 사용되어 온 벤치마크 데이터에 개미 군집 알고리즘을 적용하였다. 본 논문에서 연구된 새로운 개미 군집 알고리즘의 성능 측정 결과는 이전의 다른 논문들과 비교하여 대부분 같은 값을 같거나 때로는 더 나은 결과를 갖는 부분도 존재하였다.

서지기타정보

서지기타정보
청구기호 {MIE 12012
형태사항 ⅱ,36 p. : 삽도 ; 30 cm
언어 한국어
일반주기 저자명의 영문표기 : Do-Kyung Hyun
지도교수의 한글표기 : 박성수
지도교수의 영문표기 : Sung-Soo Park
학위논문 학위논문(석사) - 한국과학기술원 : 산업및시스템공학과,
서지주기 참고문헌 : p. 33-34
주제 상자 채우기 문제
휴리스틱
개미 군집
개미 시스템
빈 팩킹
Bin packing
2D-BPP
Ant colony
Ant system
Heuristic
QR CODE qr code