주기적 작업의 최적의 공정한로드 밸런싱/다중 프로세서 스케줄링

Question

스케줄링 및로드 밸런싱 알고리즘에 대해 생각해 봤는데 흥미로운 문제가 떠올랐다.

N 개의 보관함과 M 개의 보관함이 있습니다. 각 케이지는 크기 S와 많은 동물 A를 가지고 있습니다. 케이지를 청소해야하는 빈도는 A/S의 일부 기능으로 계산됩니다 (더 많은 동물이있는 더 작은 케이지는 더러워집니다). 새장 청소의 어려움은 A와 S의 다른 기능으로 계산됩니다. 세부 사항은 중요하지 않습니다 (새장의 크기가 대부분의 어려움에 기여하고 동물의 수는 조금 기여합니다). 3 일에 한 번, 청소해야 할 케이지가 청소됩니다 ("청소 당일"). 사육사는 완전히 동일하고 상호 교환 가능합니다. 동물원 관리자는 청소를 할 때마다 비슷한 양의 작업을 수행해야하며, 다른 모든 사육사보다 훨씬 많은 작업을 수행해야합니다. 새장이 청소하는 데 걸리는 시간은 문제의 일부가 아닙니다. 시간은 대략 어려움에 비추어 볼 수 있으며, 사육사가 과제를 완료하는 데 충분한 시간이 항상 필요하다고 가정합니다. 스케줄링 알고리즘은 각각의 케이지 이상적인 주파수로 세척 또는 최대한 가깝

• 되도록 각 세척 날 청소 케이지 각 사육사을 알려야

  ,

• A는 최소 대충 할당 청소 당 하루에 사육사 당 동일한 수의 청소,
• 그리고 모든 사육사에 대해 가능한 한 동일한 작업량을 보장하십시오. (즉, 일정 기간 동안 각 사육사의 작업 부하의 총체적 어려움은 최대한 가깝습니다. 그리고 새끼 es는 대략 1/M 확률로 사육사들에게 배포 됨).

그런 최적화 문제에 대한 근사 알고리즘이 어떻게 생겼는지 궁금합니다. NP 하드 스케줄링/자원 활용 문제에 대한 몇 가지 고전적인 예와 유사합니다. 어쩌면 그것은 그러한 문제 중 하나로 축소 될 수 있으며, 나는 그것을 놓치고 있습니다. 작업 요소의 빈도 /주기를 제거하면 고전 multiprocessor scheduling 또는 유한 bin packing 문제와 유사합니다.

Answer 1

목표가 사육사의 노력을 균등하게하는 것이라면, 이러한 작업을 처리하는 다소 표준적인 방법은 온라인 욕심입니다. 이 경우

, 즉이 금액 :

각 사육사가 처음 제로, 지금까지 소비 한 노력의 집계를 유지한다. 청소 일마다 필요한 청소 작업을 집계하고 작업 합계를 균등하게하는 경향이있는 방식으로 작업을 할당하기 위해 처음 적합, 가장 적합 또는 임의 맞춤을 사용하십시오. 나는. 가장 잘 맞는 것은 지금까지 할당 된 작업에서 가장 멀리 뒤에있는 골키퍼에게 가장 큰 일을 할당합니다. 모든 작업이 할당 될 때까지 반복하십시오.