Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Algorytm przydzielania pracy.

arnoldziq 11 Paź 2018 18:08 201 10
  • #1 11 Paź 2018 18:08
    arnoldziq
    Moderator Programowanie

    Witam wszystkich serdecznie.

    Mam niewielki problem z wymyśleniem spójnego algorytmu który wykonywałby pewne zadanie i w związku z tym mam do kolegów i koleżanek takie pytanie; czy może ktoś się z czymś takim spotkał, lub robił coś podobnego w przeszłości.

    Problem polega na wykonaniu określonych czynności, przez jak najmniejszą liczbę osób, na podstawie listy zadań.

    Oto przykład :
    Mamy do posprzątania biurowiec, który ma pięć pięter. Na każdym piętrze są przewidziane do wykonania jakieś czynności na które jest przeznaczony odpowiedni czas. Cały problem polega na tym, że niektóre czynności (chociaż nie wszystkie) mogą być wykonywane tylko w określonym czasie.
    I tak, np. :
    1. wysypywanie pojemników na śmieci - czas wykonania jednej czynności 15 minut, liczba potrzebnych pracowników - 1 osoba.
    2. czyszczenie kubków po kawie/herbacie - czas wykonania 10 minut, liczba potrzebnych pracowników - 1 osoba
    3. mycie okien - czas wykonywania 120 minut, liczba pracowników - 3 osoby
    4. .... itd, itp....

    A teraz utrudnienie, np. :
    Na wszystkich piętrach 1-5 można wyrzucać kosze tylko w godzinach od 6:00 do 7:00
    Na wszystkich piętrach 1-5 można myć kubki tylko od 8:00 do 9:00
    Na pietrach 1,2 i 3 - kawę można robić tylko pomiędzy 10:00 i 11:00
    Na piętrach 4 i 5 można robić kawę cały dzień, bez żadnych ograniczeń czasowych, ale dokładnie 3 razy dziennie
    Na wszystkich piętrach 1-5 można myć okna tylko od godziny 17:00 do 20:00

    Liczba poszczególnych czynności, przypadających na każde piętro jest zmienna, może się zdarzyć, że nie potrzeba zupełnie nic robić.
    Przyjmijmy, że liczba pracowników jest nieograniczona oraz, że każde zadanie musi być wykonane a pracownicy mogą poruszać się dowolnie pomiędzy piętrami.

    Teraz chodzi o to, żeby w zadanych ramach czasowych i przy użyciu jak najmniejszej liczby pracowników, wykonać wszystkie zadane czynności na każdym piętrze.

    Trochę się rozpisałem, ale wydaje mi się, że dość dokładnie opisałem problem :)
    Jeżeli ktoś miał styczność z takim lub podobnym problemem, to bardzo proszę o jakieś podpowiedzi. Język programowania nie ma znaczenia, bardziej chodzi o metodologię.

    Z góry dziękuje, Arnoldziq

    0 10
  • #2 11 Paź 2018 20:40
    Dżyszla
    Poziom 42  

    Ja bym nie pracował w firmie z takimi ograniczeniami! ;)

    A tak serio... Chyba najlepiej sobie to uzmysłowić wychodząc od Gantta. Jeśli w jednej linii coś się nie udaje - trzeba dorzucić następną. Zadania wymagające > 1 pracownika od razu generują tyle linii ile pracowników. Myślę, że takie rozrysowanie powinno trochę przybliżyć do znalezienia algorytmu, bo na chwilę obecną też mi nic do głowy nie przychodzi.

    PS. Rozumiem, że każdy pracownik może robić wszystko?

    0
  • #3 11 Paź 2018 21:04
    krisRaba
    Poziom 25  

    Jeszcze pytanie, czy należy pracę rozkładać równomiernie, czy najpierw zapełniasz czas jednego pracownika, a potem kolejnych, których dodano ze względu na prace wymagające większej liczby osób.
    Kolejna rzecz, czy wymagana jest rotacja, by dany pracownik nie wykonywał ciągle tej samej pracy.

    Ja bym wyszedł od zadań wymagających więcej niż jednego pracownika. Jeżeli takie występują danego dnia, to one determinują bezwzględne minimum pracowników. Na wstępie należałoby nimi obsadzić te sloty czasowe, które są krytyczne / ciasne w stosunku do długości czynności. Potem tymi samymi pracownikami próbowałbym obsadzić inne wieloosobowe zadania, tak by liczba pracowników była minimalna. W następnej kolejności dłuższe bloki, potem luki można zapychać krótkimi czynnościami.

    Pewnie trzeba by przeprowadzić kilka wariantów, porównać wyniki i wybrać optymalny.

    0
  • #4 11 Paź 2018 21:51
    drobok
    Poziom 28  

    Można by podzielić czas na sloty(z krokiem o najmniejszym czasie wykonania), dokładać każde zadanie w wszystkie możliwe sloty (3d, czas, pracownik, kolejne zadania do zrobienia) a następnie poszukać możliwej kombinacji gdzie waga sumy zadań i ich priorytetów była by największa gdzie zadania z danej sumy by się nie pokrywały czasowo.
    Jeśli brakło by zadań (lub ilość zadań do odłożenia byłą by odpowiednio mała), to zwiększyłbym priorytet zadań odłożonych i je odłożył na kolejny dzień.
    Jeśli suma by była zbyt duża dołożyłbym pracownika, gdzie zadanie na x pracowników zajmowało by daną liczbę wymiarów - pozwoliło by ci na to ew podział zadania niepodzielnego na większą ilość pracowników optymalizując koszty.

    Może nie było by to zbyt optymalne pod względem pamięciowym, ale dało by się to rozdzielić na wątki, a pamięci dzisiaj tanie - no chyba że chcesz to udostępnić na serwerze na ludu.

    0
  • #5 12 Paź 2018 10:43
    arnoldziq
    Moderator Programowanie

    Dżyszla napisał:
    Rozumiem, że każdy pracownik może robić wszystko?
    Każdy pracowniek może robić wszystko, na każdym piętrze, sam lub w zespole.
    krisRaba napisał:
    by dany pracownik nie wykonywał ciągle tej samej pracy.
    Pracownik może ciągle robić to samo, nawet cały dzień. To nie ma żadnego znaczenia.
    krisRaba napisał:
    Ja bym wyszedł od zadań wymagających więcej niż jednego pracownika. Jeżeli takie występują danego dnia, to one determinują bezwzględne minimum pracowników.
    Problem polega na tym, że zadania zespołowe mogą w ogóle nie wystąpić, albo występowac tylko na jednym piętrze. Poza tym, może się okazać, że jedno takie zadanie wystąpi w ramach czasowych "zajętych" przez inne zadania.
    drobok napisał:
    zwiększyłbym priorytet zadań odłożonych i je odłożył na kolejny dzień.
    Nie ma takiej możliwości. Wszystkie zadania MUSZĄ być wykonane w zadanych ramach czasowych, choćby to wymagało zatrudnienia tysiąca pracowników. Liczba dostępnych pracowników jest nieograniczona.
    drobok napisał:
    no chyba że chcesz to udostępnić na serwerze na ludu
    To ma być część programu, do użytku wewnętrznego, w mojej firmie.

    Może coś takiego, jak zaproponował Dżyszla, spowoduje, że ktoś wpadnie na jakiś pomysł :)

    Załóżmy, że mamy do wykonania tylko jedną czynność, zrobienie wszystkim kawy z rana :)
    Każdy, na każdym piętrze musi dostać swoją kawę pomiędzy 9:00 i 10:00.
    Normalnie, zatrudniamy 5 osób, na każdym piętrze inną i tak wygląda plan pracy :
    Algorytm przydzielania pracy.

    Przy niewielkich zmianach, gdy jedna osoba robi kawę na różnych piętrach, ograniczamy ilość potrzebnych pracowników do 3 zamiast 5 :
    Algorytm przydzielania pracy.

    Używając tej metody, możemy w zadanym czasie ograniczyć ilość potrzebnych pracowników tylko do jednej osoby.

    Cały problem polega na tym; w jaki sposób to oprogramować, żeby zatrudnić jak najmniej pracowników :)

    0
  • #6 12 Paź 2018 14:24
    krisRaba
    Poziom 25  

    A czy każdego dnia ilość pracowników musi być jednakowa? Bo znając zadania z wyprzedzeniem i obsługując więcej obiektów można ich przerzucać. Wtedy mamy bufor na skoki obciążenia ;-)

    Dodano po 9 [minuty]:

    Aha, Twoje wykresy chyba nadal są spójne z tym co powiedziałem, jeśli minimalna liczba osób do zadania jest znana i optymalna. Bo pierwszy przykład z kawą był nieoptymalny i nie wykorzystywał w pełni dostępnych slotów czasowych.
    Generalnie to też można wyznaczać z automatu. Masz ilość miejsc, czas czynności i ograniczenie czasowe. Z tego da się wyznaczyć optymalne rozwiązanie jak podałeś później.
    Pytanie tylko, bo zmienia to postać rzeczy, czy ktoś po kawę może przyjść o dowolnej porze w ustalonym slocie, czyli musisz obsadzić cały slot (wydłużyć czas czynności do długości slotu), czy też możesz skrócić slot danego piętra i zamiast 2 godzin mieć tam pracownika przez 1/3 tego czasu. Bo czy zetrzesz kurze o 8:20 czy o 9:10 to nie ma znaczenia. Ale z tą kawą to wg mnie przypadek, gdy musisz być dostępny nawet jeśli przez pierwszą godzinę nikt nie przyjdzie.

    0
  • #7 12 Paź 2018 15:21
    arnoldziq
    Moderator Programowanie

    Widzę, że kolega podchodzi do tego ze złej strony :/
    Liczba pracowników jest najmniej znacząca zmienną. Może się wąchać z godziny na godzinę i może się zdarzyć, że seria zadań do wykonania nigdy nie powtórzy się w konkretnej konfiguracji.
    Chodzi o znalezienie optymalnego rozłożenia zadań, przy użyciu jak najmniejszej liczby pracowników. Ale jeszcze raz powtórzę; liczbę pracowników należy obliczyć/wyznaczyć i nie jest z góry znana.
    Każde zadanie ma swoje ramy czasowe, np. zrobienie kawy zajmuje 10 minut, ale może być wykonane w dowolnym momencie w przedziale czasu; np. 1h.

    krisRaba napisał:
    Z tego da się wyznaczyć optymalne rozwiązanie jak podałeś później.
    JAK???
    krisRaba napisał:
    Pytanie tylko, bo zmienia to postać rzeczy, czy ktoś po kawę może przyjść o dowolnej porze w ustalonym slocie, czyli musisz obsadzić cały slot (wydłużyć czas czynności do długości slotu)
    Kawa jest zrobiona, czeka w kuchni => zadanie wykonane. Nikt się nie przejmuje czy ktoś te kawę wypije czy nie. Ma być zrobiona.

    0
  • #8 12 Paź 2018 16:57
    krisRaba
    Poziom 25  

    Aha, bo kawę robisz w termosie a nie każdemu w filiżance ;-) Ma to sens.

    Liczba pracowników nie ma znaczenia, ale ma ich być jak najmniej.. ;-) Wesołe.

    Algorytm wyznaczania minimum powinien działać tak jak to rozrysowałeś. Slot 1h, czas zadania 10min, liczba lokalizacji 5 pięter. Nie uwzględniając przejścia pomiędzy piętrami, co można skompensować korygując czas zadania, jedna osoba ogarnie ilosc_lokalizacji=slot/czas_zadania, tutaj 6. Jeśli to mniej niż ilość lokalizacji do ogarnięcia, to minimum równa się jeden, jeśli więcej, to musisz zwiększyć liczbę osób - zaokrąglone w górę liczba_lokalizacji/do_ogarniecia_przez_1_osobe.
    Przy czym tu wyznaczasz bezwzględne minumum. Potem może się okazać, że przez inne obostrzenia osób będzie musiało być więcej.

    0
  • #9 12 Paź 2018 17:52
    Dżyszla
    Poziom 42  

    Ja bym to jeszcze inaczej rozrysował... I podejdź może od drugiej strony: Masz spis zadań i możliwe ramy czasowe. Teraz układaj od początku zadanie 1, następnie po zakończeniu zadania 1 zadanie 2 (jako minimum czasu rozpoczęcia wszystkich zadań o ile zmieści się przed limitem - jak nie, to olej). I tak w kółko aż do końca dnia. Teraz jak zostało zadań, to drugi przebieg (drugi pracownik) i od nowa taki algorytm.

    Jeśli w pierwszym przebiegu trafi się zadanie dla większej liczby pracowników, to automatycznie wpisz je też do siatki pozostałych przebiegów (tyle, ile wymagane). Czyli mniej więcej jeszcze raz:

    1. Spośród wszystkich nieprzeanalizowanych zadań wybieramy to z minimalnym czasem rozpoczęcia.
    2. Wkładamy na pierwsze wolne miejsce siatki pracownika n sprawdzając, czy jego zakończenie będzie przed limitem - jeśli nie, odrzucamy i wracamy do 1. Jeśli zadanie dla większej liczby pracowników - wkładamy w siatkę n+(1..m) pracownika.
    3. Zwiększamy czas do końca ostatniego zadania i wracamy do 1 i tak do końca dnia.
    4. Jeśli pozostały nieprzydzielone zadania - zwiększamy n i powtarzamy od 1.

    Uważaj na dwa aspekty w pętlach - zadanie przydzielone i zadania przeanalizowane.

    0
  • #10 15 Paź 2018 07:25
    ble___
    Poziom 11  

    Wątpię że się uda znaleźć akceptowalnie szybki sposób który by gwarantował najlepsze rozwiązanie.

    http://ttic.uchicago.edu/~cjulia/papers/scheduling-upper.pdf
    Jeśli rozumiem opisany jest sposób szukania rozwiązania przybliżonego dla bardzo podobnego problemu, nie ma tylko wymagania wielu pracowników dla pracy.
    Nie czytałem całości i pewnie się nie przyda.

    ------------------------------

    Po podziale całego czasu możliwego do przydzielenia na sloty (w przypadku pracy wymagającej większej ilości pracowników jednocześnie ilość slotów pomnożona przez ilość pracowników),
    np. dla 7 slotów i 9 pracowników, WSZYSTKIE możliwości można by zapisać tak:

    1234567

    0000000
    0000001
    0000002
    ...
    9999999

    Pierwszy wiersz zawiera numery slotów.
    Każdy kolejny wiersz to jedna z możliwości w której:
    - 0 to czas nie przydzielony
    - cyfra > 0 to numer pracownika

    Dość łatwo napisać kod iterujący po WSZYSTKICH (nawet najgłupszych) możliwościach.
    Każdą możliwość da się wtedy sprawdzić.

    Złożoność obliczeniowa jest tak duża że sposób jest niepraktyczny.
    Po ilości opracowań tematu znalezionych w sieci zgaduję że optymalizacja nie będzie prosta.

    0
  • #11 15 Paź 2018 09:13
    adamas_nt
    Moderator Programowanie

    Tak się zastanawiam od strony matematycznej.
    A gdyby policzyć ilość osób dla wszystkich czynności, a następnie odejmować wg czasów te czynności, które się nie pokrywają. W wyniku powinno wyjść minimum pracowników niezbędnych do wykonania wszystkiego...

    Tzn coś w tym rodzaju (dla trzech czynności na początek):
    Kosze na śmieci - / 6:00 - 7:00/, 0,25godz x 5 pięter >> 2 osoby
    Mycie kubków - /9:00-10:00/ 0,2godz * 5 pięter >> 1 osoba
    Robienie kawy - brak danych o normie czasowej,

    Suma = 3

    W związku z tym, że godziny się nie pokrywają, potrzebuję 3-1=2 pracowników (lub MAX z kolumny wynikowej).

    Teraz liczę czas. 2 osoby kosze opróżnią w 1,25/2=0.63godz. kubki umyją w 0,5godz. + czas na "podróż" między piętrami + czas na otarcie potu/higienę/wc/itp (jeśli nie obejmuje tego norma).

    Czas, który zostaje między 7:00-10:00 przeznaczam na robienie kawy na 4 i 5-tym (1-sza z 3), a po 10:00 na pozostałych piętrach (bo te zadania nie zostały obłożone za 1-szym przejściem).

    Licząc jeszcze dokładniej, osoba Nr.2 w tym przypadku w godz 6:00 - 10:00 nie wychodzi nawet poza piętro 4 i 5. A kawę robi (przed myciem kubków?) w czasie gdy osoba Nr.1 wyrzuca kosze na 3#5 piętrze.

    0