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

이 글은 새로운 블로그로 옮겼습니다. 5초후 자동으로 이동합니다.

▶ 새로운 블로그 주소: https://prodskill.com/

▶ 새로운 글 주소: https://prodskill.com/job-scheduling-using-1d-bin-packing-algorithm-3/

목차

 

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 결과

 

 

 

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

 

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

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

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

 

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

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

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

 

2.10. 내림차순 정렬을 적용한 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 구성 목록 등은 서로 다를 수 있다.

정렬하지 않은 결과와 정렬한 결과를 비교하면 다음과 같다. 먼저, Bin에 채워진 item들의 구성이다.

알고리즘	정렬 전	정렬 후
Next Fit
First Fit
Worst 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 알고리즘에 대해 상세히 살펴보았다. 다음에는 이 알고리즘을 구현한 도구에 대해 살펴본다.