여기에 할당 문제가 있습니다. http://en.wikipedia.org/wiki/Generalized_assignment_problem알고리즘과 유사한 '할당 작업'
비슷한 작업이 있지만 알고리즘을 찾을 수 없습니다. 우리는 m 개의 작업, n 개의 작업자, m> n 개 있습니다. 작업이 완료되면, 노동자는 다음 작업 (무료 작업이있는 경우)을 수행합니다. 어떤 일꾼이 과업을 취하는 경우 아무도 그 일을 할 수 없습니다. 각 노동자는 자신의 속도를 가지고 있습니다 : V1..Vn, 각 작업에는 자체 '볼륨'이 있습니다 - W1..Wm. 그래서 나는 모든 일을하는 시간을 최소화하는 목표를 가지고 노동자들 사이에서 일을 나누어 줄 필요가있다.
나 알고리즘 또는 방법이 문제는 이름을 찾아 도와주세요.)
이것은 http://en.wikipedia.org/wiki/Bin_packing_problem의 가능성 NP-완전한 변화처럼 보인다. 따라서 정확한 알고리즘에 대해 걱정할 필요가 없습니다.
작업이 독립적이라고 가정 할 때, 첫 번째 시도는 탐욕적인 발견 적 것입니다. 완료 시간의 예상치가 주어지면, 각 작업자에게 완료 시간 전에 끝낼 수있는 가장 긴 작업을 할당하십시오. 이제 바이너리 검색을 수행하여 얻을 수있는 최단 마무리 시간을 찾으십시오. 초기 시간은 가장 빠른 작업자가 모든 것을 할 시간입니다. 귀하의 초기 시간은 모두가 동시에 일하고 있다면 모든 근로자가 그토록 많은 일을 마칠 수있는 시간입니다.
이것은 분명히 항상 완벽하게 최적화되지는 않습니다. 그러나 그것은 합리적으로 잘 작동해야합니다.
답장을 보내 주셔서 감사합니다.하지만 생각합니다. 빈 포장 문제가 아닙니다. 앞서 언급했듯이 스케줄링 문제가 더 자주 발생합니다. \ 우리 (나와 당신)에게 3 가지 케이크가 있다고 상상해보십시오. 나보다 빨리 먹을 수 있습니다. 그리고 우리는 우리 사이에 케이크를 배포해야합니다. 그래서, 크기와 속도에 따라, 가장 빠른 방법은 가장 큰 것을 먹을 수도 있고, 나는 2 가지를 먹을 수도 있고, 그 반대 일 수도 있고 심지어 3 가지를 전부 먹는 것일 수도 있습니다.) –
@MichaelLevin Flip "5 시간 안에이 작업을 완료 할 수 있습니까?" 이제는 작업자가 "작업 할 수있는 작업"크기의 저장소를 볼 수 있으며, 항목이 작업 (bin)에 배포되어 제한된 용량을 초과 할 수 없게됩니다. 그것은 빈 포장 연결입니다. 내 제안 솔루션은이 연결을 명시 적으로 만듭니다. 가장 짧은 마무리 시간을위한 바이너리 검색을 제안합니다. 그러나 그 검색의 각 단계는 빈 포장 문제를 해결해야합니다. – btilly
이 문제는 작업 공간을 최소화하기 위해 병렬로 균등하게 관련된 기계에서 작업을 예약하는 문제입니다. Hochbaum and Shmoys (다차원 근사 알고리즘을 이용한 스케줄링 문제 : 이론 및 실제 결과, 1988)에 의한 다항식 시간 근사법이 있습니다. 빈 포장 문제는 밀접하게 관련되어 있습니다. Hochbaum-Shmoys와 이전의 최적 근사 MULTIFIT의 분석은 빈 포장을 위해 개척 된 기술을 기반으로합니다.
스케쥴링 문제입니다. (균일하게 관련된 기계의 판도를 최소화하십시오.) –
@DavidEisenstat 고마워, 그게 .. 균일하게 관련된 기계에 관한 기사를 찾았지만 그 내용을 이해하기가 쉽지 않고 문제가 같은지 ..) –