나는 최적의 작업/작업자 할당을 달성하기위한 효과적인 방법을 찾고 있습니다. 헝가리 알고리즘을 사용 하겠지만 한 번에 한 작업에만 할당 할 수 있으며 각 작업에는 등급이 있으며 각 작업자는 자신의 평점을가집니다. 4 등급의 작업은 등급이 4 인 근로자 또는 작업 등급에 합산 된 여러 명의 근로자가 해결할 수 있습니다 (예 : 4). 2+2 또는 3+1 또는 2+1+1 또는 1+1+1+1입니다. 2 등급의 직업은 1 등급의 근로자 2 명 또는 2 등급의 근로자가 해결할 수 있습니다. 가능할 때마다 일대일 과제를 선호하고 싶습니다.하나의 강력한 근로자 또는 여러 명의 약한 근로자가 해결할 수있는 작업을 최적으로 할당
이 경우 최적의 알고리즘을 구현하기위한 알려진 알고리즘이나 간단한 방법이 있습니까?
실현 가능한 해결책이 있는지를 아는 것조차도 적어도 문제가 분명히 Partition Problem만큼 어렵습니다. 이를 보여주기 위해 파티션 인스턴스를 만들어 봅시다. 두 개의 작업을 생성하고 파티션 문제의 요소 수만큼의 작업자를 생성하여 문제로 쉽게 변형 될 수 있습니다. 각 작업에는 파티션 문제의 해당 요소 값과 동일한 등급이 있습니다. 파티션 문제에 해결책이있는 경우에만 문제가 해결 될 수 있으므로 문제가 NP 하드임을 증명할 수 있습니다.
우리는 Subset Sum을 고려해 볼 때 문제가 적어도 NP-Complete만큼 어렵다는 논쟁을 제기 할 수 있다고 생각합니다. 평점은 [0, M에 난에 대한 내가을 R로 평가 값이 모든 실수의 집합에 N과 M 근로자
우리의 경우 우리는 문제를 양의 정수로 제한 할 수 있지만 많은 문제가 있기 때문에 의사 결정 문제가 여전히 남아 훨씬 더 어려워지고 있으며 완료된 작업의 수를 최대화하고 싶습니다 .을 감안할 때 하나의 작업 :
하면이 의사 결정 문제로 변환), 각 등급이 모든 실수의 집합에 속하는 경우 등급이 N까지 추가되는 근로자의 하위 집합이 있습니까?
... NP 하드와 비슷합니다. – displayName
문제의 제약 조건은 무엇입니까? 작업자가 여러 작업에 배정 될 수 있습니까? 당신의 목적 함수는 무엇입니까? 작은 예가 사물을 분명히합니다. –
@DamienProt 작업자는 한 번에 하나의 작업에만 할당 될 수 있습니다. 여러 작업자가 작업에 배정 된 경우 해당 작업의 평점과 작업의 평점이 같아야합니다. – Tom