근로자 선호도에 따라 팀에 근로자를 할당하는 알고리즘

Question

직원 수는 N이고 M 수퍼바이저 중 하나에 배정되어야합니다. 각 팀은 최대 K 명의 근로자를 보유 할 수 있습니다. 각 작업자는 가장 선호하는 팀의 경우 1에서 가장 선호하지 않는 팀의 경우 M으로 시작하여 우선 순위에 따라 팀 순위를 매 깁니다. 이제 문제는 일치를 찾는 것이므로 각 팀이 최대 K 명의 근로자를 가질 수 있다는 점을 감안할 때 가장 선호하는 팀에서 근로자가 마무리됩니다.

처음에는 생각했는데, 이것은 을 사용하여 해결할 수있는 Assignment problem입니다. 그러나 헝가리 알고리즘은 각 작업자가 정확히 하나의 항목에 할당 된 경우에만 사용할 수 있음을 알게되었습니다. 하지만 제 경우에는 여러 팀원을 같은 팀에 배정 할 수 있습니다.

이제는 이것이 실제로 어떤 종류의 문제인지 확신 할 수 없습니다. 이 (복수형) Knapsack problem 또는 Bin packing problem입니까? 어떤 종류의 알고리즘을 사용하여 문제를 해결할 수 있습니까? 다음 팀에 각 직원을 지정해야하고 각 팀은 할 수있다 - 당신은 하나의 용량 K 팀으로 각 팀을 복제하는 경우

이 : 작은 조정으로

Answer 1

이 문제를 해결하는 방법에는 두 가지가 있으며, 얼마나 많은 사람과 팀이 있고 얼마나 큰지 K의 크기에 따라 더 효율적입니다.

(@Alex L.의 대답에서 이미 언급 한) 쉬운 방법은 각 팀을 K 팀으로 나눠서 헝가리 알고리즘으로 해결할 수있는 정기적 인 가중치 이진 검색으로 변환하는 것입니다. 이제 헝가리 알고리즘의 복잡성은 O(n^2 * m)입니다. 여기서 우리는 사람 수인 n을 선택하고 팀 수인 m을 선택합니다. 각 팀을 k으로 나눈 후 최종 복잡도는 O(n^2 * m * k)이됩니다.

또 다른 방법은이 문제를 최소 비용 최대 흐름 문제로 처리하는 것입니다. 두 개의 추가 노드 인 소스와 싱크, 용량이 1이고 가중치가 0 인 모든 작업자, 모든 팀이 용량이 k이고 무게가 0 인 싱크대에 연결되어 있고 작업자가 용량이 많은 팀에 연결되어있는 작업자 1 및 비용은 선호도에 따라 다릅니다. 최소 비용 최대 흐름에는 O(n^3 * m)의 복잡성이 있습니다. 자, 우리가 n이고 팀의 수를 m으로 선택하면, 우리는 헝가리보다 더 나쁜 것을 얻습니다 (아마 k < n이기 때문에). 그러나 우리가 n을 팀 수, m을 노동자 수로 취하면 노동자의 수가 많고 팀 수가 적고 k도 큰 경우 잠재적으로 헝가리보다 더 나은 것을 얻을 수 있습니다.

그래서 모두 제약 조건에 따라 다릅니다. m이 k 및 n보다 현저히 작은 경우 최소 비용 최대 흐름을 사용하는 것이 유리합니다. 그렇지 않으면 팀을 k으로 분할하고 바닐라 헝가리 알고리즘을 사용합니다.

Answer 2

, 그것은 할당 문제가 될 수 있습니다 한 명의 작업자에게 할당됩니다.

할당 문제에서 에이전트와 작업의 수는 같지 않아도됩니다.