부하균형 (1) 썸네일형 리스트형 동일한 기계 여러 대에 작업 할당하기 (Load Balancing on Identical Machines) 여러분이 어떤 작업들을 처리해야 한다고 해봅시다. 작업들은 특수한 기계에 의해 처리되며, 여러분은 동일한 성능을 가진 기계를 여러 대 받았습니다. 작업들 사이에는 선후행 관계가 없습니다. 다시 말해, 어떤 작업을 처리하기 위해서 다른 어떤 작업이 처리되어야 한다는 식의 조건은 존재하지 않습니다. 당연히 여러분은 일을 빨리 끝내고 싶어 합니다. 과연 어떻게 작업을 기계에 할당해야 할까요? 만약 모든 작업이 수행되는 시간이 동일하면 이 문제는 쉽게 해결됩니다. 작업의 개수를 \(n\), 기계의 대수를 \(m\)이라고 했을 때, 각 기계마다 최대 \( \lceil n/m \rceil \) 개씩 넣어주면 되겠습니다. 모든 작업이 끝나는 시각이 이보다 빠를 수 없다는 것은 비둘기집 원리를 사용하면 쉽게 증명할 수.. 이전 1 다음
