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 396 18
  • #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 18
  • #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 26  

    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 26  

    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 26  

    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 12  

    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
  • #12 18 Paź 2018 11:02
    arnoldziq
    Moderator Programowanie

    Ruszyłem do przodu (odrobinę) z tym projektem.

    Stworzyłem klasę która przechowuje dane a następnie ( bardzo się stara :) ) przydziela konkretne wydarzenia poszczególnym pracownikom.
    Karmię ją (tę klasę) np. takimi danymi:

    Kod: delphi
    Zaloguj się, aby zobaczyć kod

    Gdzie kolejno idą: ID piętra, ilość pracowników niezbędna do wykonania, czas wykonania oraz ramy czasowe wyznaczone na konkretne zadanie.
    Na obrazki, wygląda to mniej więcej tak (zielone pola, to tam gdzie potrzeba więcej niż jednej osoby):
    Algorytm przydzielania pracy.
    Tak to wygląda, po procesie przydzielania zadań:
    Algorytm przydzielania pracy.
    A tak to wygląda "od strony" samych pracowników:
    Algorytm przydzielania pracy.

    Wszystko dział, zgodnie z założeniami, ale cała procedure nie jest optymalna. Od strony wykonania zadań, wszystko jest perfekcyjnie i na 100%. Natomiast gorzej to wygląda od strony optymalizacji listy pracowników :/
    Co mam na myśli? "Ręcznie" można "przesunąć" wydarzenia tak, że bez problemy można zredukować liczbę pracowników o 1 ( w tym przypadku jest to aż 25%):
    Algorytm przydzielania pracy.
    Takie, lub podobne rozwiązanie uznałbym za optymalne.

    Co gorsze, nie mam na to żadnego pomysłu.

    Kod udostępniam, może komuś się przyda w takiej ( działającej na 75% ) formie.
    Kod: delphi
    Zaloguj się, aby zobaczyć kod


    Dodam, że jest to kod "pierwszego podejścia" i jest strasznie zaśmiecony, więc proszę tego nie komentować :P
    Natomiast chętnie przyjmę wszelkie uwagi dotyczące samej metodologii.

    0
  • #13 18 Paź 2018 17:29
    Dżyszla
    Poziom 42  

    Wybacz, że nie przejrzę długawego kodu, ale czy ten mój algorytm nie powinien właśnie zoptymalizować tego? A bankowo przynajmniej pierwszemu by wypełnił cała linię.

    To ograniczenie na dostępne piętra dla pracowników zaimplementowałeś? (nie widzę nic wśród danych).

    0
  • #14 19 Paź 2018 10:13
    arnoldziq
    Moderator Programowanie

    Dżyszla napisał:
    To ograniczenie na dostępne piętra dla pracowników zaimplementowałeś? (nie widzę nic wśród danych).
    Nic takiego nie zrobiłem, bo nic takiego nie ma prawa zaistnieć.
    Dżyszla napisał:
    A bankowo przynajmniej pierwszemu by wypełnił cała linię.
    No nie tak do końca. Przy jednakowej długości zadaniach, tak jak w tym przykładzie, pierwszy pracownik po prostu nie ma wystarczającej liczby zadań, żeby "wypełniło" mu czas na 100%. Ate to także nie jest problem, jak długo wszystkie zadania są komuś przydzielone i wykonane.

    0
  • #16 19 Paź 2018 23:11
    ble___
    Poziom 12  

    arnoldziq napisał:
    Co gorsze, nie mam na to żadnego pomysłu.


    Jeśli zrobiło się coś ręcznie to prawdopodobnie zna się sposób jak to zrobić (szczególnie jak to "operacje logiczne").
    Pewnie jakby opracować opis własnego sposóbu wnioskowania to udało by się na jego podstawie opracować kod.

    0
  • #17 20 Paź 2018 11:28
    arnoldziq
    Moderator Programowanie

    Dżyszla napisał:
    A spróbuj jeszcze zacząć od przydzielania tych, które mają największą liczbę osób wymaganych.
    W poniedziałek do tego wrócę i spróbuję.
    ble___ napisał:
    Pewnie jakby opracować opis własnego sposóbu wnioskowania to udało by się na jego podstawie opracować kod.
    Mówi kolega o sztucznej inteligencji :)

    0
  • #18 22 Paź 2018 12:20
    arnoldziq
    Moderator Programowanie

    Przesunięcie "podwójnych" prac nie dało oczekiwanego efektu:
    "Oryginalny" rozkład :
    Algorytm przydzielania pracy.
    "Podwójne rozpatrywane na końcu":
    Algorytm przydzielania pracy.

    Już nawet "lepiej" wygląda gdy umieścimy "podwójne" zadania na początku listy:
    Algorytm przydzielania pracy.

    Muszę coś pokombinować z przesuwaniem zadań na wolne sloty na wolne miejsca i wciskaniem w nowo-powstałe przerwy zadań, należących do innych pracowników.

    0
  • #19 22 Paź 2018 14:16
    Dżyszla
    Poziom 42  

    Wg mnie dało - zmniejszyło o 1 liczbę osób potrzebnych. Natomiast błąd leży tu, że chyba tych zadań nie przydzielałeś w pierwszej kolejności, dlatego wepchnęło pojedyncze dla #1 i #2, a podwójne wylądowały w #3 i #4. Gdyby je przydzielić na początku w pierwszym przebiegu (czyli najpierw tylko podwójne), to powinno właśnie wyjść bardziej jak w ostatnim przykładzie.

    Po prostu całą listę musisz wielokrotnie przelecieć tylko szukając w niej zadań z różnymi warunkami. Pierwszy przebieg przydzielanie tych o max n potrzebnych osób, drugi o n-1 aż do n=1. I za każdym razem szukać w pierwszej osobie wolnego miejsca, a jak nie ma, to przydzielić kolejnej/nowej. Lub alternatywnie - jak sugerowałem, w pętli po n-potrzenych robić pętlę po istniejących osobach i po przebiegu, jeśli wciąż zostają - dołożyć osobę i znów od początku, aż cała list zadań zostanie przydzielona. Mam rażenie, że na siłę chcesz raz przeglądając listę zadań rozdysponować od razu wszystkie.

    0