로드 밸런싱 및 제 2 종류의 스털링 번호 적용

Question

필자는 앞서 말한 것을 사용하여 P 스레드와 N> P 태스크를 수행했습니다. 각 작업과 관련된 양의 정수 값은 특정 작업이 의미하는 작업의 양을 나타냅니다.

P 스레드 중 N 개의 작업을 분할하여 각 스레드의 "작업 정수"의 합계를 고려하면 거의 같습니다.

그런 "스케줄링"을 수행하는 순진하지만 정확한 방법은 S (N, P)가 두 번째 종류의 스털링 수인 S (N, P) 태스크 파티션을 고려해야합니다. 실제 컴퓨팅).

Q : "로드 균형 조정 된"작업 파티션을 계산하기위한 우수하고 효율적인 근사 알고리즘이 있습니까?

Answer 1

프로세서가 2 개 밖에없는 경우 작업을 두 개의 동일한 작업으로 나누는 문제를 partition problem이라고합니다. 그것은 NP 하드로 알려져 있습니다. 따라서 최상의 솔루션을 찾는 것이 어려운 문제 일 수 있습니다. 나만 근사값을 원한다면, 나는 어떤 종류의 욕심 많은 알고리즘을 찾아 갈 것이다 : 더 적은 작업을 가진 가장 큰 나머지 작업을 체계적으로 할당하라. 이렇게하면 시간 복잡도 O (작업 ​​수 * 스레드 수)의 알고리즘을 쉽게 구현할 수 있습니다.