선형 상자포장 문제의 다항시간 최적 알고리즘 (A Polynomial Time Optimal Algorithm for Linear Bin Packing Problem)

서지정보

· 발행기관 : 한국정보기술학회
· 수록지 정보 : 한국정보기술학회논문지 / 11권 / 8호 / 9 ~ 16페이지
· 저자명 : 이상운

초록

일반적으로 상자포장 문제는 다항시간으로 근사 해를 찾는 알고리즘만이 존재하여 NP-완전 문제로 알려져 있다. 본 논문은 선형 상자문제의 정확한 해를 다항시간으로 찾을 수 있는 알고리즘을 제안한다. 개 물품의 물품 크기 를 내림차순으로 정렬시켜 용량이 인 필요한 상자 수 의 약 75 % 상자들에 개의 물품을 순서대로 1개씩 넣고, 나머지 물품을 찾아 넣는 방법으로 문제를 25%로 단축시켰다. 나머지 필요한 상자 25%에 대해서도 유사한 방법으로 물품을 채우는 방법을 적용하였다. 제안된 알고리즘을 OR-LIB의 120, 250과 500개의 데이터에 적용한 결과 100% 정확한 해를 얻는데 성공하였다. 제안된 알고리즘은 상자 포장 문제가 P-문제임을 증명하였으며, NP-완전으로 알려진 멀티프로세서 스케쥴링 문제에도 적용할 수 있을 것이다.

영어초록

Generally, the bin packing problem has been regarded as NP-complete, and the sole algorithm in existence can only obtain approximate solutions for the problem. This paper proposes a polynomial time algorithm capable of obtaining the precise solution for the linear bin packing problem. The proposed algorithm sorts items in the descending order of the item size . The algorithm then places of these items 75% of bins, given the number of bins each with a capacity of , required to accommodate n items. This method has allowed the algorithm to drastically reduce the given problem to 25%. Subsequently, it fills the remaining 25% of the needed boxes following the same method. When applied to 120, 200, and 500 data of OR-LIB, the proposed algorithm has been successful in yielding the 100% accurate solutions. This algorithm has therefore proved that the bin packing problem is in fact P-problem and it could also be applied to a multiprocessor scheduling problem, which is also currently regarded as NP-complete.

참고자료

· 없음