근사 알고리즘/Job scheduling (2) 썸네일형 리스트형 상관없는 기계에서 가중치 완성 시간 최소화하기 (Minimizing Weighted Completion Time on Unrelated Machines) 한 회사에서 어떤 작업들을 처리해야 한다고 합시다. 이 작업들을 처리하기 위해 기계 수 대를 갖고 있습니다. 각 기계들은 회사가 성장해 가면서 하나씩 사들이는 바람에 제원이나 사양이 모두 다릅니다. 다만, 모든 기계는 한 번에 하나의 작업만을 처리할 수 있으며, 한 작업이 시작되면 이를 중단하지 않고 끝까지 처리합니다. 회사 내에서 거의 유일하게 머리 좀 쓰는 공돌이인 여러분은 기계를 활용하여 작업들을 적절히 처리하라는 지시를 받았습니다. 지시 사항을 전달 받은 여러분은 상사에게 곧장 되물었습니다. 목표가 무엇인가요? 기계의 수행 시간을 최소화해야 하는지, 마감 기한을 어기는 정도를 최소화해야 하는지, 아니면 전기비 절감을 위해 기계가 사용하는 에너지를 최소화해야 하는지 등 작업 스케줄을 평가하는 요소는.. 동일한 기계 여러 대에 작업 할당하기 (Load Balancing on Identical Machines) 여러분이 어떤 작업들을 처리해야 한다고 해봅시다. 작업들은 특수한 기계에 의해 처리되며, 여러분은 동일한 성능을 가진 기계를 여러 대 받았습니다. 작업들 사이에는 선후행 관계가 없습니다. 다시 말해, 어떤 작업을 처리하기 위해서 다른 어떤 작업이 처리되어야 한다는 식의 조건은 존재하지 않습니다. 당연히 여러분은 일을 빨리 끝내고 싶어 합니다. 과연 어떻게 작업을 기계에 할당해야 할까요? 만약 모든 작업이 수행되는 시간이 동일하면 이 문제는 쉽게 해결됩니다. 작업의 개수를 \(n\), 기계의 대수를 \(m\)이라고 했을 때, 각 기계마다 최대 \( \lceil n/m \rceil \) 개씩 넣어주면 되겠습니다. 모든 작업이 끝나는 시각이 이보다 빠를 수 없다는 것은 비둘기집 원리를 사용하면 쉽게 증명할 수.. 이전 1 다음
