1차원 Bin Packing 알고리즘을 활용한 작업 배분 최적화_2.알고리즘(2)

2.6. Item 크기로 내림차순 정렬 적용

지금까지 Next Fit, First Fit, Worst Fit, Best Fit의 각 알고리즘의 동작 방식과 실행 결과를 살펴보았다. 입력 자료의 크기가 일정 순서로 정렬되지 않은 상태에서 무작위 순서로 처리할 때와 정렬한 상태에서의 처리는 그 결과가 달라진다. 크기가 큰 Item을 먼저 채우는 것이 일반적으로 좋은 결과가 도출되므로 Item의 크기로 먼저 내림차순 정렬하고 처리하는 방법을 생각해 볼 수 있다.

먼저 입력 자료와 이를 내림차순으로 정렬한 자료는 다음과 같다.

# 입력자료
26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 35 12 43 36 72 14 28 3 11 46 27 42 59 26 41 15 41 68
# 내림차순 정렬 입력자료
72 68 63 59 57 57 54 54 46 45 45 43 42 41 41 36 35 32 29 28 27 27 27 26 26 24 22 21 18 18 17 16 16 15 14 14 13 12 11 11 8 8 6 5 3

내림차순으로 정렬한 자료를 입력으로 각 알고리즘을 실행한 결과를 살펴보자.

2.7. 내림차순 정렬을 적용한 Next Fit

내림차순 정렬을 적용한 Next Fit 결과
내림차순 정렬을 적용한 Next Fit 결과

전체 공간은 1,840(Bin 하나당 크기 80 * Bin 개수 23)이고, 잔여공간합계는 488로 공간비효율은 약 26.52% (488/1,840) 이다.

2.8. 내림차순 정렬을 적용한 First Fit

내림차순 정렬을 적용한 First Fit 결과
내림차순 정렬을 적용한 First Fit 결과

전체 공간은 1,440(Bin 하나당 크기 80 * Bin 개수 18)이고, 잔여공간합계는 88로 공간비효율은 약 6.11% (88/1,440) 이다.

2.9. 내림차순 정렬을 적용한 Worst Fit

내림차순 정렬을 적용한 Worst Fit 결과
내림차순 정렬을 적용한 Worst Fit 결과

전체 공간은 1,440(Bin 하나당 크기 80 * Bin 개수 18)이고, 잔여공간합계는 88로 공간비효율은 약 6.11% (88/1,440) 이다.

2.10. 내림차순 정렬을 적용한 Best Fit

내림차순 정렬을 적용한 Best Fit 결과
내림차순 정렬을 적용한 Best Fit 결과

전체 공간은 1,440(Bin 하나당 크기 80 * Bin 개수 18)이고, 잔여공간합계는 88로 공간비효율은 약 6.11% (88/1,440) 이다.

2.11. 알고리즘 적용 결과 비교

 위에서 살펴본 사례에서 가장 비효율이 큰 Next Fit을 제외하고 First Fit, Worst Fit, Best Fit의 잔여공간합계와 공간비효율이 모두 동일한 결과가 나왔고, 각 Bin에 채워진 item은 서로 다르게 구성되었다.

참고로, 동일한 결과가 나온 것은 이 사례의 입력 데이터와 제약 사항에 따라 발생한 우연이다. 입력 데이터와 제약사항이 달라지면 잔여공간합계와 공간 비효율, Bin의 item 구성 목록 등은 서로 다를 수 있다.

정렬하지 않은 결과와 정렬한 결과를 비교하면 다음과 같다.

▼ Next Fit

정렬 전 Next Fit
정렬 전 Next Fit
정렬 후 Next Fit
정렬 후 Next Fit

▼ First Fit

정렬 전 First Fit
정렬 전 First Fit
정렬 후 First Fit
정렬 후 First Fit

▼ Worst Fit

정렬 전 Worst Fit
정렬 전 Worst Fit
정렬 후 Worst Fit
정렬 후 Worst Fit

▼ Best Fit

정렬 전 Best Fit
정렬 전 Best Fit
정렬 후 Best Fit
정렬 후 Best Fit

아래는 각 알고리즘의 실행에서 산출된 정량적 정보이다.

알고리즘 항목 정렬 전 정렬 후 비교
Next Fit 비교횟수 44 44 변화 없음
전체공간 1,840 1,840
잔여공간합계 488 488
공간비효율 26.525 26.525
First Fit 비교횟수 330 448 비교횟수는 늘어났으나 공간비효율이 줄어들어 개선됨
전체공간 1,520 1,440
잔여공간합계 168 88
공간비효율 11.05% 6.11%
Worst Fit 비교횟수 465 643
전체공간 1,680 1,440
잔여공간합계 328 88
공간비효율 19.52% 6.11%
Best Fit 비교횟수 428 643
전체공간 1,520 1,440
잔여공간합계 168 88
공간비효율 11.05% 6.11%

위 표에서 비교 횟수는 다음에 소개할 엑셀 VBA 기반 도구에서 대략적으로 측정한 수치이다. 위의 내용을 보면 item의 크기로 내림차순 정렬 후 Bin Packing을 실행한 결과가 공간비효율이 줄어들어 더 촘촘하게 채워진 것을 확인할 수 있다. 이를 통하여 먼저 정렬하고 알고리즘을 적용하는 것이 더욱 최적화된 결과를 얻을 수 있음을 알 수 있다.

항상 Best Fit이 최적이라고 볼 수는 없다. 각 알고리즘의 실행 결과를 검토하고 그때 그때의 상황에 맞는 최적 결과를 선택하는 것이 바람직하다.


여기까지 Bin Packing 알고리즘에 대해 상세히 살펴보았다. 다음에는 이 알고리즘을 구현한 도구에 대해 살펴본다.


<< 관련 글 목록 >>

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

ko_KR한국어