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

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

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

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

목차

 

3. Bin Packing 알고리즘 구현

Item의 목록과 제약사항을 입력하고 알고리즘을 구현하여 결과를 확인하려면 개발 환경이 필요하다. 개발 환경은 엑셀 VBA, Python, R 등 여러가지가 있다. 이 중 엑셀 VBA는 공개되어 있는 library가 없어 소스코드를 거의 대부분 직접 작성해야 한다. Python과 R은 Bin Packing 알고리즘을 직접 구현할 수도 있고, 이미 제공되는 package를 이용할 수도 있다. 여기에서는 엑셀 VBA로 필자가 직접 알고리즘을 구현한 도구와 Python에서 제공되는 package를 이용한 활용 방법을 살펴본다.

 

3.1. 엑셀 VBA 기반 도구

알고리즘을 구현하는 도구나 언어들은 보통 프로그램의 소스코드에서 데이터 파일을 별도로 입력으로 받는다. 엑셀 VBA는 프로그램 소스코드와 데이터를 하나의 파일에서 관리할 수 있고 분리하여 관리할 수도 있는 특성이 있다. 여기에서는 프로그램 소스코드와 데이터를 하나의 파일에서 관리하도록 구현하였다.

Item의 목록을 엑셀 Sheet로 입력하여 관리하고, 1차원 Bin Packing 알고리즘을 VBA로 구현한 도구의 구성과 소스코드에 대해 아래에서 간략하게 소개한다. 소스코드 전체는 별첨으로 제공하고 https://github.com/DAToolset/1D-bin-packing 에서도 확인할 수 있다.

DAToolset/1D-bin-packing

 

**참고: 이 글에서는 엑셀 VBA의 개념이나 문법 등에 대해서는 다루지 않고, 향후 별도 글로 상세히 작성할 예정이다.

도구의 전체 구성은 다음 그림과 같다. “Run” sheet에 자료를 입력하고 옵션을 설정한 다음 “Run Bin Packing”버튼을 클릭하여 실행 결과를 확인한다.

1차원 Bin Packing 알고리즘을 활용한 작업 배분 최적화 도구 화면

위 그림의 4가지 영역에 대한 세부 내용은 다음 각 목차에서 설명한다.

 

3.1.1. 입력 자료 구성

Item 목록은 다음과 같은 형태로 Name과 Size를 입력한다.

입력 자료 구성

여기에서 Bin Item Name은 Item이 어떤 개체인지를 식별하기 위한 명칭으로 Item의 유형에 따라 적절하게 지정하면 된다. 예를 들면 다음과 같다.

• Item이 Database Table인 경우에 해당 table 명칭
• Item이 Job인 경우 해당 job 명칭
• 그 외, 각 Item을 식별하기에 적합한 명칭(순번 등도 가능)

주의할 것은 Item 목록에 명칭 중복이 없어야 한다는 점이다. Size는 동일하더라도 서로 다른 개체임을 알 수 있어야 Bin에 어떤 개체를 채울지 판단할 수 있기 때문이다.

Size에는 각 Item의 크기를 입력한다. Size는 table의 경우 row수, byte수를 사용할 수 있고, job의 경우 실행 소요시간을 분 또는 초단위로 입력하여 사용할 수 있다. 소요시간은 job 의 실행 기록에서 확인하여 기입하되, 가급적 최근 5회 이상의 소요시간 중 최대값과 최소값을 제외한 평균값을 계산하여 사용하는 것이 좋다.

여러가지 자료 set가 필요하다면 “Run” sheet를 복사하여 입력하면 된다. Sheet의 명칭은 어떤 이름이라도 상관없지만, <Run_자료 세트명>의 형태로 지정하는 것이 다른 sheet와 구별할 수 있어 좋다. 예를 들어 다음과 그림과 같이 “Run_Org” 등으로 지정한다.

자료 Set

자료 set를 여러 개를 만들어 각 자료 set sheet에서 서로 다른 자료 또는 서로 다른 옵션을 설정하여 Bin Packing을 실행할 수 있다. 실행 결과가 표시되는 sheet는 자료 set 마다 만들어지지는 않고 고정적으로 사용된다. 만약 각 자료 set로 실행되는 결과를 각각 유지하고자 한다면 엑셀 파일을 다른 이름으로 저장하여 별도 파일로 생성하는 방법을 사용하면 된다.

 

3.1.2. 옵션 설정

제약 조건인 Bin의 최대 Size와 기준 컬럼, 내림차순 정렬 여부는 다음과 같은 형태로 입력한다.

옵션 설정

Max Bin Size는 하나의 Bin에 지정할 최대 크기이다. 즉, 여러 Item을 하나의 Bin에 채울 때 Item Size의 합계에 대한 제약사항이다.

Item Size 기준 컬럼은 하나의 Bin Item에 여러가지 Size값이 있을 때 어떤 값을 사용할지 지정하는 컬럼이다. 예를 들어, 다음과 같이 하나의 item에 여러 size를 입력할 수 있게 구성하는 경우를 가정해 보자.

Item Size로 사용할 수 있는 값 예시 (C ~ I)

Size 값으로 사용할 수 있는 컬럼은 C ~ I까지이다. 이 중에서 어떤 컬럼을 Size 입력 값으로 사용할지 선택하기 위하여 컬럼명을 기입한다. Size에 임의의 값을 생성하여 모의 실험해보려면, J 컬럼(Rando Size)에서 수식으로 생성된 값을 복사하고 I컬럼 (Simulation)으로 값으로 붙여넣기 한 다음 기준 컬럼을 I로 지정하여 실행하면 된다. J 컬럼을 지정하지 않아야 하는 이유는, J 컬럼에는 수식이 사용되어서 계산될 때마다 새로운 값이 생성되고 따라서 어떤 값을 입력 값으로 사용했는지 알 수 없게 되기 때문이다.

Item Size 내림차순 정렬 옵션을 선택(체크)하면 먼저 Item의 Size로 내림차순 정렬하고 Bin Packing 알고리즘을 적용한다.

 

3.1.3. Bin Packing 실행

입력 자료 구성과 옵션 설정까지 완료하면 “Run BinPacking” 버튼을 클릭하여 실행한다.

Bin Packing 실행 버튼

실행할 때 “Bin Item Name”에 중복이 있는 경우 오류가 발생할 수 있는데, 확인하여 중복을 제거하고 실행하면 된다.

 

 

3.1.4. 실행 결과 확인

실행 결과는 5개의 Sheet로 구성되어 있다. 전체 요약은 각 알고리즘의 실행 결과를 취합해 놓은 Result summary sheet에서 확인하고, 각 알고리즘의 세부 결과는 각 sheet에서 확인한다.

Bin Packing 실행 결과

• Result Summary: 각각의 알고리즘을 실행한 결과를 한눈에 볼 수 있도록 취합해 놓은 sheet
• Next Fit: Next Fit 알고리즘을 실행한 결과 sheet
• First Fit: First Fit 알고리즘을 실행한 결과 sheet
• Worst Fit: Worst Fit 알고리즘을 실행한 결과 sheet
• Best Fit: Best Fit 알고리즘을 실행한 결과 sheet

Result summary sheet의 내용은 다음과 같다.

Bin Packing Result Summary sheet

 

상단에는 옵션에서 설정한 Max Bin Size를 참조 정보가 표시되고, 하단에는 4가지 각 알고리즘을 실행한 결과 차트를 보여준다.

각 알고리즘을 실행한 결과 sheet에서 표시되는 정보의 구성은 다음과 같다.

각 알고리즘을 실행한 결과 sheet 구성

항목	내용
① 결과 목록	Bin Packing 알고리즘을 실행한 결과로 어떤 Item이 어떤 Bin에 채워졌는지 확인할 수 있다. 여기에서 Bin 명칭은 프로그램 처리 과정에서 임의로 <Bin_순번5자리>의 규칙을 가지고 생성한다.
② Bin 합계	Bin단위로 Item Size의 합계를 계산하기 위한 피벗 테이블이다. <④ Bin 합계 Chart>는 이 피벗 테이블을 데이터 소스로 만들어 진다.
③ 실행 정보	알고리즘을 처리하는데 걸린 소요시간, Bin 전체 잔여 공간의 합계, 전체 공간 합계, 공간 비효율 정보를 표시한다. 공간 비효율은 (Bin 전체 잔여 공간 합계)/(전체 공간 합계)로 계산한다.
④ Bin 합계 Chart	<② Bin 합계 피벗 테이블>을 세로 막대형 차트로 표현하여 시각화한 내용이다.

 

▼ Next Fit 실행 결과

Next Fit 실행 결과

 

▼ First Fit 실행 결과

First Fit 실행 결과

 

▼ Worst Fit 실행 결과

Worst Fit 실행 결과

 

▼ Best Fit 실행 결과

Best Fit 실행 결과

 

3.1.5. VBA 코드 구성

Bin Packing을 VBA로 구현한 소스코드에 대해 간략하게 설명한다. VBA Project의 전체 구성은 다음과 같다.

VBA 코드 구성

• Sheet(엑셀 UI)는 입력 자료의 목록을 관리하고 입력과 알고리즘 처리 결과의 출력을 표시한다.
• 모듈은 전체 처리 과정을 처리하고 제어하는 역할과 클래스의 인스턴스 생성, 공통 기능 등을 담당한다.
• 클래스는 입력 자료의 메모리 적재와 알고리즘 구현, 결과 데이터 출력 등의 기능을 담당한다.

 

세부 항목의 용도는 다음과 같다.

구분	항목	설명
Sheet	각 sheet	입력자료/옵션 설정, 실행결과 출력
모듈	modControl	클래스를 개체화하고 입력자료 적재, Bin Packing각 알고리즘 구현, 결과 출력 등의 전체 처리 관리
	modFactory	클래스의 개체화 관리 VBA의 클래스는 생성자(constructor)의 입력 parameter를 지정할 수 없어 Factory Pattern으로 개체를 생성하도록 구성함
	modUtil	Logging, 소요시간의 문자열 포맷 설정 등의 기능 관리 여기에서 Logging은 파일로 남기지 않고, Windows API중 OutputDebugString으로 Debugger상에서 log 메시지를 확인할 수 있도록 구성함. Debugger는 DebugView를 이용 권고
클래스	CBin	Bin 1개 단위의 클래스 주요 method: AddBinItem, IsAbleToAdd
	CBinItem	Bin에 담기는 Item 1개 단위의 클래스 즉 입력자료 1줄에 해당하는 클래스 주요 method: CompareTo
	CBinItemCollection	여러 BinItem의 목록을 관리하는 컬렉션 클래스 주요 method: Add, Sort, GetString
	CPacker	Bin 목록을 Collection으로 관리하는 클래스 입력자료를 기존 Bin 목록 중 적합한 곳에 채우거나 새로운 Bin을 생성하여 채우는 알고리즘 구현 주요 method: DoPacking, Add, GetNewBin, GetBinNextFit, GetBinFirstBit, GetBinWorstFit, GetBinBestFit, PackToBin, DoOutput, GetRemainSizeSum
	CTimer	소요시간을 측정하기 위한 클래스 Windows API QueryPerformanceCounter, QueryPerformanceFrequency 사용 주요 method: StartCounter, TimeElasped

OOP 개념을 제대로 적용하려면 클래스에는 public 멤버 변수 없이 Getter/Setter로 구성된 public Property를 노출시키는 것이 정석이다. 하지만, 이 도구에서는 구현의 편의상 public Property를 사용하지 않았다. 다만, 외부에서 접근 가능한 멤버 변수와 함수, 프로시저는 public으로 선언하고, 외부에서의 접근을 제한할 대상은 private으로 선언하여 구분하였다.

VBA 소스코드에서 정의한 클래스들간의 관계를 UML Class Diagram으로 간략하게 표현하면 다음과 같다.

Class Diagram

위 Class Diagram의 클래스들 간 관계는 has a 관계이다. 즉, 두 클래스 간에 정의된 composition 관계에서 채워진 마름모(◆)쪽이 container 이다.

 우측에서 좌측으로 갈수록 하위 클래스에서 상위 클래스로 연결된다고 볼 수 있다. 입력자료 1개는 CBinItem 클래스에서 관리하고, CBinItemCollection 클래스는 입력자료 전체를 CBinItem의 collection으로 관리한다. CBin 클래스는 Bin 개별개체를 관리하고 각 Bin에 채워진 Item의 목록을 CBinItemCollection 클래스의 개체로 관리한다. CPacker 클래스는 알고리즘을 구현하고 결과 Bin 전체 개체를 CBin 클래스의 collection으로 관리한다. 각 클래스들은 composition 관계로 container 개체가 제거될 때 하위 개체는 모두 제거된다. CTimer 클래스는 알고리즘의 실행시간을 측정하기 위하여 CPacker 클래스에서 사용한다.

여기에서 CBinItemCollection 클래스는 입력자료 전체를 관리하는 용도로도 사용하고, 각 Bin에 채워진 Item 목록을 관리하는 용도로도 사용한다. 예를 들어, 100개의 Item이 10개의 Bin에 각각 10개씩 채워졌다고 했을 때, 전체 100개 item을 관리하는 개체도 CBinItemCollection 클래스 type이고, 각 Bin에 채워진 10개씩의 item을 관리하는 개체도 CBinItemCollection 클래스 type이다.

각 클래스의 소스코드는 별첨을 참고하고, 입력 자료 적재부터 알고리즘 실행, 결과 데이터 출력의 전 과정을 제어하는 모듈 modControl의 pseudo code는 다음과 같다.

Public Sub RunBinPacking()
    입력자료를 읽어들여 CBinItemCollection type의 oInputItemCol 변수에 적재
    입력자료의 정렬 실행을 선택했으면 oInputItemCol 내림차순 정렬
    각 알고리즘의 실행결과를 담을 변수 선언
    각 변수에 최대 Bin 크기와 PackingType을 설정하여 개체 생성
    각 변수에 입력자료 채우기
    결과출력
    각 변수 메모리에서 삭제하여 정리
End Sub

---

다음 글에서는 Python Bin Packing 패키지를 활용하여 구현한 소스코드와 실행결과에 대해 살펴본다.