1차원 Bin Packing 도구 최근 변경 사항 (2021-03-21 기준)

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

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

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

목차

 

1. 변경사항 요약

블로그에 작성한 1차원 Bin Packing 도구에 대한 설명은 2017-11-19 기준으로 작성된 내용이다.

Bin Packing 과정 예시

관련글: 2021.05.20 - [엑셀&VBA/Tools] - 1차원 Bin Packing 알고리즘을 활용한 작업 배분 최적화_1.개요

1차원 Bin Packing 알고리즘을 활용한 작업 배분 최적화_1.개요

2021-03-21에 K사 프로젝트를 수행하면서 개선사항이 있어 별도로 정리한다.

• Item Size를 정수(Long)에서 실수(Double)로 변경(변수명 prefix 변경)
• BinItem 명칭 대소문자 구분 (Collection 에서 Dictionary로 변경)
    - Class명 변경(CBinItemCollection -> CBinItemDic)
• 배분 결과 홀수, 짝수 그룹별 순서 정렬
• BinItem loading 코드 개선(Loop using offset --> get Variant array from range)
• Bin Item Name에 중복이 있는 경우, 중복 목록 메시지 박스로 알려주고 실행 중단

변경된 버전은 아래 github repository에서 다운로드받을 수 있다.

https://github.com/DAToolset/1D-bin-packing

DAToolset/1D-bin-packing

또는, 아래 Link를 클릭하면 바로 받을 수 있다.

https://github.com/DAToolset/1D-bin-packing/raw/main/1차원 Bin Packing_20210321_1.xlsb

 

2. 변경사항 상세

2.1 Item Size를 정수(Long)에서 실수(Double)로 변경(변수명 prefix 변경)

기존 버전은 0.1, 21.8 등의 실수 Size 값을 입력하면 정수형으로 변환되어 소수점 아래 값들이 잘렸고, 정확하게 배분되지 못하는 문제가 있었다. Size 값을 Byte수가 아닌 KB, MB, GB, TB 등으로 사용하는 경우에 주로 문제가 되었다.

CBinItem 클래스의 "Public m_lSize As Long" 멤버변수 선언을 "Public m_dSize As Double"로 변경하였다.

 

2.2 BinItem 명칭 대소문자 구분 (Collection 에서 Dictionary로 변경)

기존 CBinItemCollection Class의 member변수로 각 item을 Collection에 담아서 관리하였다. Item을 탐색할 때 item 이름을 key로 사용하여 item instance를 찾았는데, Collection의 item key는 대소문자를 구분하지 않는 특성이 있다.

대소문자를 구분하는 데이터베이스에서 추출한 테이블명과 컬럼명이 대소문자를 구분하지 않는 Collection의 item key로 중복이 발생하여 변경하였다.

대소문자를 구분하는 데이터베이스에서는 테이블명 "T1", "t1"을 각각 생성하여 사용할 수 있다. 혼동을 줄 수 있으므로 권장되지는 않으나, 이미 생성되어 있는 개체는 서로 다르게 식별해야 해서 개선이 필요했다.

item key가 대소문자를 구분하도록 Dictionary를 사용하여 Class를 다시 작성하고 Class명도 "CBinItemCollection"에서 "CBinItemDic"으로 변경하였다.

 

2.3 배분 결과 홀수, 짝수 그룹별 순서 정렬

BinPacking결과에서 각 Bin의 Item size는 다음과 같이 정렬된다.

• "Item Size descending order" 옵션을 선택한 경우: 크기가 큰 Item으로부터 작은 Item으로 역순 정렬
• "Item Size descending order" 옵션을 선택하지 않은 경우: 입력순서

Bin Packing을 실행한 결과가 4개의 Bin으로 배분되었다고 가정하자. 이대로 Bin Item 목록을 복사하여 작업 Group을 만들고 각 작업 Group을 실행한다면 다음과 같은 현상이 발생할 수 있다.

• Bin Item이 크기 역순으로  정렬된 경우 실행시 현상
  • 동시에 실행되는 작업 Group 4개가 시작부터 가장 큰 크기의 작업을 실행한다.
  • 서버의 자원(CPU, Memory, I/O) 경합이 심해지고 자원이 부족한 경우 일부 작업은 실패하거나 대기시간이 길어지게 된다.
  • 큰 크기의 작업 실행이 완료되고 점차 작은 크기의 작업으로 이어지면서 자원경합은 점점 해소된다.
• Bin Item이 입력순서로 정렬된 경우 실행시 현상
  • 서버 자원 경합이 심해졌다가 해소되었다가를 반복한다.

이 현상은 자원을 효율적으로 활용하지 못하여 서버의 부하가 극심해지거나, 실행완료 시점을 예측하기 어렵게 하는 문제를 만들 수 있다.

동시에 실행되는 작업의 크기의 합을 거의 균등하게 만들면 이 문제가 발생하지 않을 수 있으나, Bin Item 크기가 균일하지 않아서 균등에 가깝게 만들기는 거의 불가능하다.

이 현상을 최소화하기 위하여 각 Bin의 Item을 크기로 정렬하되, Bin 순서상 짝수번째와 홀수번째의 정렬순서를 반대로 하는 옵션을 추가하였다.

이 옵션을 적용하면 다음과 같은 배분결과가,

Bin1: 2, 5, 3, 1
Bin2: 3, 6, 1, 2

다음과 같이 변경된다.

Bin1: 5, 3, 2, 1 # Decending order
Bin2: 1, 2, 3, 6 # Ascending order

이 옵션을 적용하더라도 실행시점의 자원경합을 완전히 최적화하기는 어렵다. 다만, 자원경합을 가급적 최소화할 수는 있다.

 

2.4. BinItem loading 코드 개선

"Run" 시트에 입력 Bin Item 목록을 읽어서 memory로 loading하는 코드를 Varaint array를 이용하여 개선하였다.

Variant array를 이용하는 방법은 이 글을 참조한다.

2021.05.30 - [엑셀&VBA/코딩패턴] - VBA 코딩 패턴: Range Loop

VBA 코딩 패턴: Range Loop

 

2.5. Bin Item Name에 중복이 있는 경우, 중복 목록 메시지 박스로 알려주고 실행 중단

기존 버전에서는 Bin Item Name에 중복이 있는 경우 무시하고 진행하였다. 이번 버전에서 대소문자를 구분하도록 변경하면서 입력자료에 중복이 있는지 점검하고 그 내용을 알린 다음 실행을 중단하도록 변경하였다. 중복을 제거 또는 중복되지 않도록 변경하여 재실행하면 된다.

---

 

Bin Packing 도구는 자주 사용하지는 않으나, 1년에 4~5회 이상은 꼭 사용하는 것 같다. 가끔이라도 필자에게는 큰 도움이 되곤 한다. 궁금한 점은 댓글로 남겨주시기 바란다.