Algorytm procentowy bez znajomości liczby całkowitej

17

Załóżmy, że istnieją nlinie dla infolinii.

Za każdym razem, gdy klient dzwoni na infolinię, połączenie jest przekierowywane na jedną z nlinii. I chcę przypisać procent połączeń do każdej z n linii. Załóżmy, że są dwie linie, a jedna linia ma przypisane 60%, a druga 40%, całkowita liczba połączeń wynosi 10, więc pierwsza linia otrzyma 6 połączeń, a druga otrzyma 4 połączenia.

Znam z góry procent dzwonienia na każdą linię, ale problem polega na tym, że nie znam liczby połączeń, które zostałyby odebrane w ciągu jednego dnia.

Jak mogę rozdzielić liczbę połączeń bez znajomości łącznej liczby połączeń?

akku
źródło
2
Gdy linia 1 otrzyma 6 połączeń, daj linię 2 4 połączenia. Oznacza to, że nie przejmuj się faktyczną całkowitą liczbą, dbaj o rozkład w „znanym” okresie (w tym przypadku 10). Oczywiście możesz robić takie rzeczy, jak linie alternatywne, z wyjątkiem ostatniej wartości, więc nie trzeba też ściśle czekać. Jeśli jest jakaś kolejka, wykonaj wartość procentową na podstawie bieżących wierszy w kolejce.
Clockwork-Muse
co to jest „gwiazdka” i „DID”?
komara
@ Clockwork-Muse: Proponuję zaokrąglić liczby całkowite tutaj zamiast utrzymywania rozkładu 6-4. W przeciwnym razie dystrybucja będzie wyłączona, chyba że wiesz, że masz dokładnie 10 połączeń. Np. Jeśli przyjdzie 6 wszystkich połączeń, sugerowane podejście przypisze je wszystkie do linii A; mając na uwadze, że bardziej poprawnym podejściem byłoby 4 do A i 2 do B (przypisane w kolejności ABAABA, jeśli zaokrąglisz liczby całkowite przypisania liczb całkowitych dla każdej linii)
Flater

Odpowiedzi:

26

Wykonaj kilka ksiąg rachunkowych dotyczących już odebranych połączeń i oblicz ich rozkład w linii n To daje ci n wartości procentowych (już osiągnięty rozkład), które można porównać z n procentami, które chcesz osiągnąć. Za każdym razem, gdy przychodzi nowe połączenie, przypisz je do linii o największym odchyleniu od wartości docelowej (zwróć uwagę, że dopóki nie trafisz dokładnie w dany rozkład, zawsze istnieje linia, która ma za mało połączeń, w porównaniu z rozkładem docelowym).

Na przykład: po przypisaniu pierwszego połączenia do linii 1:

 total calls line1      total calls line2    perc.line 1    perc. line 2
 1                      0                    100%             0% 
                                             *above 60%      *below 40% <- next call to 2
 1                      1                    50%             50% 
                                             * below 60%:    *above40% next to line1
 2                      1                    66%             33%
                                             *above 60%      *below 40% <- next to line 2
 2                      2                    50%             50% 
                                             * below 60%:    *above40% next to line1
 3                      2                    60%             40% 
                                             * both hit the mark: next call arbitrary
 4                      2                    66%             33%
                                             *above 60%      *below 40% <- next to line 2
 4                      3                    57.1%             42.85%
                                             *below 60%      *above 40% <- next to line 1

...

EDYCJA: To podejście można jeszcze ulepszyć, nie stosując bezwzględnej różnicy, ale wybierając linię, która minimalizuje sumę kwadratów wszystkich odchyleń. Dałoby to również lepszy wynik, jeśli dokładnie osiągniesz wartości docelowe.

Doktor Brown
źródło
2
Możesz zmienić to „tak długo, jak” na bardziej wyraźne „użyj innego odwołania rozstrzygającego”, FWIW.
DougM
@DougM: zobacz moją edycję.
Dok. Brown
5
  • Załóżmy, że liczba pracowników jest mniejsza niż 100
  • Utwórz tablicę pracowników o pojemności 100
  • Umieść w tej tablicy pracownika liczbę razy równą odsetkowi połączeń, które powinien uzyskać, na przykład jeśli pracownik1 otrzyma 30% wszystkich połączeń, a następnie umieść go na pozycjach od 0 do 29 tablicy.
  • Na koniec należy użyć każdej pozycji tablicy, a pracownicy powinni pojawić się w tablicy tyle razy, ile procent połączeń, które powinni uzyskać.
  • W pętli wygeneruj liczbę losową z przedziału od 0 do 99 i przypisz połączenie przychodzące do pracownika w tej pozycji tablicy. Jeśli pracownik jest zajęty, powtórz.
  • W ten sposób, z czystego prawdopodobieństwa, połączenia będą dystrybuowane zgodnie z potrzebami
  • W moim przykładzie pracownik1 ma szansę 30/100 na wybór w dowolnej iteracji.
Tulains Córdova
źródło
4

Zgadzam się z rozwiązaniem @ DocBrown. Umieszczenie go w formie algorytmu:

for each incoming call:
    sort lines ascending by delta* (see footnote below)

    // first element in array gets the call 
    increase number of calls for first element by 1
  • Delta jest określana przez rzeczywisty procent minus oczekiwany procent linii. W ten sposób te z największą deltą ujemną to te, które najbardziej wymagają wywołania w celu dostosowania do oczekiwanego procentu.

    Na przykład w przypadku, gdy oczekiwane wartości procentowe dla linii 1 i 2 wynoszą odpowiednio 60% i 40%, a ich rzeczywiste wartości procentowe wynoszą 50% i 50%, zobaczysz wiersz zamówienia 1, a następnie wiersz 2, ponieważ -10 % jest mniejsze niż 10%. Dlatego linia 1 odbierze połączenie.

    Zdecydowanie polecam użycie sortowania wstawianego, ponieważ działa najlepiej, gdy tablica jest już w większości posortowana.

Ponadto, jako drobna optymalizacja, jeśli śledzisz dotychczasową całkowitą liczbę połączeń, zamiast obliczać rzeczywisty procent każdej linii, możesz po prostu obliczyć całkowitą liczbę połączeń dla tej linii minus oczekiwany procent dla tej linii razy linii łączna liczba połączeń (delta = t_i - p_i * T). W tym przypadku delta to po prostu ujemna liczba połączeń, aby osiągnąć oczekiwany procent.

Mam nadzieję, że to wyjaśni inne wątpliwości.

Neil
źródło
dzięki @Neil naprawdę mi pomogłeś, ale kiedy oba uderzają w znak, więc do której linii mam zadzwonić, czy są na to jakieś kryteria.
akku
@akku Z moim algorytmem po prostu bierzesz pierwszy zawsze po sortowaniu, co oznacza, że ​​algorytm nie ma znaczenia. Jeśli musisz zastosować inne kryteria, musisz odpowiednio ważyć podczas sortowania. Innymi słowy, jeśli numer linii był ważny, powinieneś wziąć deltę, pomnożyć przez całkowitą liczbę linii, a następnie dodać bieżący numer linii. To sprzyja wyższym numerom linii, zakładając, że wszystkie pozostałe są równe.
Neil
@ Neil: twoja odpowiedź jest w porządku, ale ilekroć widzę kogoś, kto sugeruje całkowite posortowanie tablicy tylko w celu znalezienia minimalnej wartości, myślę: „Wielki Scott, czy to naprawdę konieczne?”
Dok. Brown
@DocBrown O(n)jest tym, czego możesz oczekiwać, sortując już posortowaną listę z sortowaniem wstawiania i O(n)jest to, czego będziesz musiał użyć, aby znaleźć najmniejszą wartość. Po prostu zakładam, że to posortowałem.
Neil
@ Neil: tylko dlatego, że oba algorytmy są O (n), nie są one równie proste (ani równie szybkie).
Dok. Brown
2

Założenia, jak stwierdził PO

  1. Liczba linii, n, jest znana i;
  2. % Każdej linii jest znany

Projektowanie algorytmów

  1. Zdefiniuj każdą linię według jej%

  2. Posortuj każdą linię według pozycji od 0 zdefiniowanej jako (bieżący% pracowników - przydzielono% pracowników) lub losowo, jeśli wszystkie linie = 0

  3. Przekaż każde połączenie na największą linię poza 0

Przykład: 3 linie z% odpowiednio 20, 30 i 50. W punkcie x w czasie 1 osoba dzwoni, a ponieważ każda linia jest 0 od 0, przydzielana jest losowo - powiedzmy na linii 2, która powinna obsłużyć 30% wszystkich połączeń. Ponieważ linia 2 powinna obsługiwać 30% wszystkich połączeń, a teraz obsługuje 100% wszystkich połączeń, jego pozycja od 0 wzrasta. Następny dzwoniący zostanie teraz przypisany do linii 1 lub linii 3 itd., Aż do osiągnięcia równowagi (0), a zatem pętla się powtarza.

bezwzględny
źródło
0

Jest to naiwne rozwiązanie i zakłada jedynie, że pozwoliłoby na rozkład procentowy. To rozwiązanie można ulepszyć na wiele sposobów, ale to jest sedno. Nie jestem pewien, czy tego właśnie szukasz, ale zapewniłoby to prawdziwą dystrybucję.

kod psuedo ...

int running_total_of_calls = 0

//This is hard coded for clarity. You'd most likely want to dynamically populate this array depending and probably distribute the work by alternating workers. Notice how "worker1" appears 6 out of 10 times in the array.
string[] worker = new string[10]
workers[0] = "worker1"
workers[1] = "worker1"
workers[2] = "worker1"
workers[3] = "worker1"
workers[4] = "worker1"
workers[5] = "worker1"
workers[6] = "worker2"
workers[7] = "worker2"
workers[8] = "worker2"
workers[9] = "worker2"

while(1) //run forever
    //This is where the distribution occurs. 
    //first iteration: 0 modulus 10 = 0. 
    //second: 1 modulus 10 = 1
    //third: 2 modulus 10 = 2
    //...
    //10th: 10 modulus 10 = 0
    //11th: 11 modulus 10 = 1 
    //12th: 12 modulus 10 = 2
    //...
    int assigned_number = running_total_of_calls % workers.Count //count of workers array
    string assigned_worker = workers[assigned_number]
    do_work(assigned_worker)
    running_total_of_calls = ++running_total_of_calls
Odnxe
źródło