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

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

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

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

목차

 

3.2. Python Bin Packing 패키지 활용

3.2.1. Python Bin Packing 패키지 소개와 설치

Python에서 활용할 수 있는 Bin Packing 패키지는 Pypi(Python Package Index) 웹 페이지의 https://pypi.python.org/pypi/bin-packing-problem/1.0.0 에서 제공한다. 이 URL에서 Bin Packing package에 대한 간략한 설명과 예시 소스 코드를 참고할 수 있고, package 파일을 다운로드하여 구현되어 있는 소스 코드를 확인할 수 있다.

bin-packing-problem

 

bin-packing-problem 1.0.0 package

 

 

 

 

이 package의 Fit 모듈 내에 다음과 같은 Bin Packing을 구현한 method를 제공한다.

알고리즘	method(정렬 적용하지 않음)	method(정렬 적용함)
Next Fit	nf	- (v1.0에 구현되어 있지 않음)
First Fit	ff	ffd
Worst Fit	wf	wfd
Best Fit	bf	bfd

 

설치는 다음과 같이 Python package manager인 pip를 이용한다.

pip install bin-packing-problem

 

3.2.2. Bin Packing 샘플 소스 코드

다음은 위에서 설치한 Bin Packing package를 활용한 샘플 소스 코드이다. 목차 2에서 Bin Packing 알고리즘을 설명하는 내용에서 사용한 입력 값을 동일하게 사용하였다.

참고로, Package 개발자의 의도인지 실수인지는 모르겠으나 nfd(next fit descending) method는 구현되어 있지 않아 주석으로 처리해 놓았다

from binpackp import NumberBin, Fit

def print_result(fit_name, fit_result):
    print(fit_name + " Result: ", fit_result)
    for bin in fit_result.bins:
        print(bin)
    print()

bin_size = 80
fit_these = [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]

next_fit_results = Fit.nf(NumberBin, bin_size, fit_these)
first_fit_results = Fit.ff(NumberBin, bin_size, fit_these)
worst_fit_result = Fit.wf(NumberBin, bin_size, fit_these)
best_fit_result = Fit.bf(NumberBin, bin_size, fit_these)

# sorted_next_fit_results = Fit.nfd(NumberBin, bin_size, fit_these) # not implemented
sorted_first_fit_results = Fit.ffd(NumberBin, bin_size, fit_these)
sorted_worst_fit_result = Fit.wfd(NumberBin, bin_size, fit_these)
sorted_best_fit_result = Fit.bfd(NumberBin, bin_size, fit_these)

print_result("Next Fit", next_fit_results)
print_result("First Fit", first_fit_results)
print_result("Worst Fit", worst_fit_result)
print_result("Best Fit", best_fit_result)

# print_result("Next Fit With Sort", next_fit_results) # not implemented
print_result("First Fit With Sort", sorted_first_fit_results)
print_result("Worst Fit With Sort", sorted_worst_fit_result)
print_result("Best Fit With Sort", sorted_best_fit_result)

 

3.2.3. Bin Packing 샘플 소스 코드 출력

샘플 소스 코드를 실행한 결과는 다음과 같다. 목차 2에서 설명한 각 알고리즘의 실행 결과와 출력되는 순서가 다르긴 하나 채워진 내용은 동일함을 확인할 수 있다.

Next Fit Result:  <BPResult (Total Bins: 23, Total Volume: 1840, Unused Volume: 488)>
<NumberBin>(Volume: 26/80, Items: [26])
<NumberBin>(Volume: 75/80, Items: [57, 18])
<NumberBin>(Volume: 69/80, Items: [8, 45, 16])
<NumberBin>(Volume: 75/80, Items: [22, 29, 5, 11, 8])
<NumberBin>(Volume: 27/80, Items: [27])
<NumberBin>(Volume: 67/80, Items: [54, 13])
<NumberBin>(Volume: 38/80, Items: [17, 21])
<NumberBin>(Volume: 77/80, Items: [63, 14])
<NumberBin>(Volume: 67/80, Items: [16, 45, 6])
<NumberBin>(Volume: 32/80, Items: [32])
<NumberBin>(Volume: 57/80, Items: [57])
<NumberBin>(Volume: 69/80, Items: [24, 18, 27])
<NumberBin>(Volume: 54/80, Items: [54])
<NumberBin>(Volume: 47/80, Items: [35, 12])
<NumberBin>(Volume: 79/80, Items: [43, 36])
<NumberBin>(Volume: 72/80, Items: [72])
<NumberBin>(Volume: 56/80, Items: [14, 28, 3, 11])
<NumberBin>(Volume: 73/80, Items: [46, 27])
<NumberBin>(Volume: 42/80, Items: [42])
<NumberBin>(Volume: 59/80, Items: [59])
<NumberBin>(Volume: 67/80, Items: [26, 41])
<NumberBin>(Volume: 56/80, Items: [15, 41])
<NumberBin>(Volume: 68/80, Items: [68])

First Fit Result:  <BPResult (Total Bins: 19, Total Volume: 1520, Unused Volume: 168)>
<NumberBin>(Volume: 80/80, Items: [54, 26])
<NumberBin>(Volume: 79/80, Items: [26, 18, 8, 16, 5, 6])
<NumberBin>(Volume: 79/80, Items: [57, 22])
<NumberBin>(Volume: 77/80, Items: [45, 29, 3])
<NumberBin>(Volume: 76/80, Items: [11, 8, 27, 13, 17])
<NumberBin>(Volume: 75/80, Items: [54, 21])
<NumberBin>(Volume: 77/80, Items: [63, 14])
<NumberBin>(Volume: 79/80, Items: [16, 45, 18])
<NumberBin>(Volume: 79/80, Items: [32, 24, 12, 11])
<NumberBin>(Volume: 71/80, Items: [57, 14])
<NumberBin>(Volume: 77/80, Items: [27, 35, 15])
<NumberBin>(Volume: 79/80, Items: [43, 36])
<NumberBin>(Volume: 72/80, Items: [72])
<NumberBin>(Volume: 74/80, Items: [28, 46])
<NumberBin>(Volume: 69/80, Items: [27, 42])
<NumberBin>(Volume: 59/80, Items: [59])
<NumberBin>(Volume: 41/80, Items: [41])
<NumberBin>(Volume: 41/80, Items: [41])
<NumberBin>(Volume: 68/80, Items: [68])

Worst Fit Result:  <BPResult (Total Bins: 21, Total Volume: 1680, Unused Volume: 328)>
<NumberBin>(Volume: 80/80, Items: [29, 5, 11, 8, 27])
<NumberBin>(Volume: 41/80, Items: [41])
<NumberBin>(Volume: 46/80, Items: [46])
<NumberBin>(Volume: 54/80, Items: [54])
<NumberBin>(Volume: 56/80, Items: [41, 15])
<NumberBin>(Volume: 56/80, Items: [32, 24])
<NumberBin>(Volume: 57/80, Items: [57])
<NumberBin>(Volume: 59/80, Items: [59])
<NumberBin>(Volume: 61/80, Items: [35, 12, 14])
<NumberBin>(Volume: 61/80, Items: [45, 16])
<NumberBin>(Volume: 63/80, Items: [63])
<NumberBin>(Volume: 67/80, Items: [54, 13])
<NumberBin>(Volume: 68/80, Items: [42, 26])
<NumberBin>(Volume: 68/80, Items: [68])
<NumberBin>(Volume: 69/80, Items: [28, 3, 11, 27])
<NumberBin>(Volume: 69/80, Items: [45, 6, 18])
<NumberBin>(Volume: 72/80, Items: [72])
<NumberBin>(Volume: 74/80, Items: [57, 17])
<NumberBin>(Volume: 74/80, Items: [26, 18, 8, 22])
<NumberBin>(Volume: 78/80, Items: [21, 14, 16, 27])
<NumberBin>(Volume: 79/80, Items: [43, 36])

Best Fit Result:  <BPResult (Total Bins: 19, Total Volume: 1520, Unused Volume: 168)>
<NumberBin>(Volume: 80/80, Items: [57, 18, 5])
<NumberBin>(Volume: 80/80, Items: [63, 14, 3])
<NumberBin>(Volume: 80/80, Items: [54, 26])
<NumberBin>(Volume: 79/80, Items: [26, 8, 45])
<NumberBin>(Volume: 79/80, Items: [8, 27, 17, 21, 6])
<NumberBin>(Volume: 79/80, Items: [16, 45, 18])
<NumberBin>(Volume: 79/80, Items: [54, 13, 12])
<NumberBin>(Volume: 79/80, Items: [43, 36])
<NumberBin>(Volume: 78/80, Items: [16, 22, 29, 11])
<NumberBin>(Volume: 76/80, Items: [27, 35, 14])
<NumberBin>(Volume: 74/80, Items: [28, 46])
<NumberBin>(Volume: 74/80, Items: [59, 15])
<NumberBin>(Volume: 72/80, Items: [72])
<NumberBin>(Volume: 69/80, Items: [27, 42])
<NumberBin>(Volume: 68/80, Items: [57, 11])
<NumberBin>(Volume: 68/80, Items: [68])
<NumberBin>(Volume: 56/80, Items: [32, 24])
<NumberBin>(Volume: 41/80, Items: [41])
<NumberBin>(Volume: 41/80, Items: [41])

First Fit With Sort Result:  <BPResult (Total Bins: 18, Total Volume: 1440, Unused Volume: 88)>
<NumberBin>(Volume: 80/80, Items: [45, 35])
<NumberBin>(Volume: 80/80, Items: [54, 26])
<NumberBin>(Volume: 80/80, Items: [54, 26])
<NumberBin>(Volume: 80/80, Items: [59, 21])
<NumberBin>(Volume: 80/80, Items: [63, 17])
<NumberBin>(Volume: 80/80, Items: [68, 12])
<NumberBin>(Volume: 80/80, Items: [72, 8])
<NumberBin>(Volume: 80/80, Items: [45, 29, 6])
<NumberBin>(Volume: 80/80, Items: [57, 18, 5])
<NumberBin>(Volume: 79/80, Items: [57, 22])
<NumberBin>(Volume: 78/80, Items: [46, 32])
<NumberBin>(Volume: 79/80, Items: [43, 36])
<NumberBin>(Volume: 78/80, Items: [42, 28, 8])
<NumberBin>(Volume: 79/80, Items: [41, 27, 11])
<NumberBin>(Volume: 79/80, Items: [41, 27, 11])
<NumberBin>(Volume: 72/80, Items: [27, 24, 18, 3])
<NumberBin>(Volume: 75/80, Items: [16, 16, 15, 14, 14])
<NumberBin>(Volume: 13/80, Items: [13])

Worst Fit With Sort Result:  <BPResult (Total Bins: 18, Total Volume: 1440, Unused Volume: 88)>
<NumberBin>(Volume: 80/80, Items: [63, 17])
<NumberBin>(Volume: 72/80, Items: [13, 12, 11, 11, 8, 8, ...])
<NumberBin>(Volume: 72/80, Items: [45, 27])
<NumberBin>(Volume: 72/80, Items: [43, 29])
<NumberBin>(Volume: 72/80, Items: [72])
<NumberBin>(Volume: 73/80, Items: [68, 5])
<NumberBin>(Volume: 73/80, Items: [46, 27])
<NumberBin>(Volume: 73/80, Items: [45, 28])
<NumberBin>(Volume: 74/80, Items: [42, 32])
<NumberBin>(Volume: 75/80, Items: [16, 16, 15, 14, 14])
<NumberBin>(Volume: 75/80, Items: [57, 18])
<NumberBin>(Volume: 76/80, Items: [54, 22])
<NumberBin>(Volume: 76/80, Items: [41, 35])
<NumberBin>(Volume: 77/80, Items: [59, 18])
<NumberBin>(Volume: 77/80, Items: [41, 36])
<NumberBin>(Volume: 78/80, Items: [57, 21])
<NumberBin>(Volume: 78/80, Items: [54, 24])
<NumberBin>(Volume: 79/80, Items: [27, 26, 26])

Best Fit With Sort Result:  <BPResult (Total Bins: 18, Total Volume: 1440, Unused Volume: 88)>
<NumberBin>(Volume: 80/80, Items: [45, 35])
<NumberBin>(Volume: 80/80, Items: [54, 26])
<NumberBin>(Volume: 80/80, Items: [54, 26])
<NumberBin>(Volume: 80/80, Items: [59, 21])
<NumberBin>(Volume: 80/80, Items: [63, 17])
<NumberBin>(Volume: 80/80, Items: [68, 12])
<NumberBin>(Volume: 80/80, Items: [27, 24, 18, 11])
<NumberBin>(Volume: 80/80, Items: [72, 8])
<NumberBin>(Volume: 80/80, Items: [45, 29, 6])
<NumberBin>(Volume: 80/80, Items: [57, 18, 5])
<NumberBin>(Volume: 79/80, Items: [43, 36])
<NumberBin>(Volume: 79/80, Items: [57, 22])
<NumberBin>(Volume: 79/80, Items: [41, 27, 11])
<NumberBin>(Volume: 78/80, Items: [46, 32])
<NumberBin>(Volume: 78/80, Items: [42, 28, 8])
<NumberBin>(Volume: 78/80, Items: [16, 16, 15, 14, 14, 3])
<NumberBin>(Volume: 68/80, Items: [41, 27])
<NumberBin>(Volume: 13/80, Items: [13])

 

4. 향후 발전방향 및 참고자료

지금까지 살펴본 Bin Packing 알고리즘은 각 Item이 서로 관련성이 없이 독립적임을 전제로 구성되어 있다. 다시 말해서 Item간에 서로 선후 관계가 있어서 하나의 Bin에 함께 채워져야 할 필요가 있는 경우 등의 종속성을 고려하지 않은 알고리즘이다.

현실적으로는 종속성이 없는 경우보다는 종속성이 있는 경우가 훨씬 많다고 할 수 있다. 예를 들어, Job1, Job2, Job3가 각각 독립적으로 실행되어도 무방한 경우보다는 Job2와 Job3가 Job1이 먼저 실행되고 난 다음에 실행되어야 하는 경우가 실무에서는 더 많이 발생한다.

지금까지 알려진 Bin Packing 알고리즘에 종속성을 반영하여 발전시킬 필요가 있다. 이 글에서는 종속성을 반영한 Bin Packing은 살펴보지 않았다. 누구라도 추가 연구를 통해 개선, 발전시킨 내용을 공유해 주면 매우 감사하겠다.

이 글의 내용에 대한 feedback은 댓글 또는 https://github.com/DAToolset/1D-bin-packing github issue, 저자 이메일로 보내주기 바란다.

DAToolset/1D-bin-packing