[Algorytm] Podział listów

[kaschata 0]

Cześć.

Chcę sobie uprościć robotę (i kilku innym też) więc piszę (próbuję) program, który będzie to za mnie robił. Najpierw wstęp, który zobrazuje o co chodzi.

Przychodzą do nas większe ilości listów. Listy muszą zostać otwarte i przejrzane, i przydzielone do jakiegoś tematu (mamy tematów 12). Jako, że listów jest dużo, pracuje nad tym około 10 osób (dużo więcej, ale przyjmijmy, że 10). Osoba A lepiej radzi sobie z tematem T1 a osoba B z tematem T2 itd (wszystkie dane są w bazie, więc czasy obróbki danego tematu przez wszystkie osoby są znane, mimo to mogę sztucznie przydzielić kogoś do jakiegoś tematu z wyższym priorytetem, mimo że jest wolniejszy niż to wynika ze statystyk).

Program ma automatycznie ustalić na podstawie ilości listów w danym temacie, kogo i gdzie przydzielić, żeby skończyć o określonej godzinie. Ważne, bo nie chodzi o jak najszybciej, tylko np. przed 16tą ma być gotowe. Jeśli wyjdzie, że jest za dużo ludzi, to należy wytypować osoby w danej chwili niepotrzebne (w danej chwili, bo po kwadransie mogą zostać dosłane kolejne listy).

Wszystkie liczby są znane i obliczane na bieżąco, trzeba tylko jakoś przejrzeć wszystkie obecne osoby i ich wydajność, i przydzielić do bieżącego stanu wejściowego listów (T1 - 20kg, T2 - 15kg, T3 - yx kg...)

Proszę o nakierowanie mnie na właściwy tor, bo nie wiem od czego zacząć.

Pozdrawiam

Tadek

[hot_stuff 0]

Poczytaj o algorytmach planowania przydzialu czasu procesora<czy jak to sie tam konkretnie nazywalo>

Tutaj masz co nieco o tym napisane --> http://www.prz.rzeszow.pl/we/katedry/zsc/projekty/2000/0/index.html -- algorytmy ktore powinny cie interesowac zaczynaja sie gdzies w polowie strony, z tym, ze.. to jest tylko omowienie a nie konkretny algorytm rozpisany krokowo, ale dzieki temu zapewne bedziesz wiedzial gdzie masz szukac.

Wydaje mi sie, ze wspomniane wyzej algorytmy by bardziej byly przydatne w rozwiazaniu problemu niz jakies problemy plecakowe. No i rzecz jasna musialbys ww. algorytmy nieco zmodyfikowac/dostosowac do tego konkretnego zagadnienia.

[januzi 24]

Hmmm ... szeregowanie zadań na maszynach równoległych (wykres Gantta)

 

można by zrobić coś takiego:

1. bierzesz pierwszą wolną maszynę i wrzucasz do niej zadania wykonywane najszybciej aż dojdziesz do czasu granicznego

2. jeśli jest wolna maszyna to wróć do 1

3. posortuj maszyny ze względu na pozostały wolny czas

4. bierzesz najmniej obciążoną maszynę i dorzucasz jej zadania aż dojdziesz do czasu granicznego

5. jeśli wszystkie zadania zostały przydzielone, to skocz do 7

6. jeśli jest wolna maszyna to wróć do 4

7. możesz dokonać zbilansowania maszyn, żeby miały mniej więcej tyle samo zadań do wykonania

[kaschata 0]

Dzięki za podpowiedzi.

Algorytmy szeregowania już przerobiłem i za bardzo nie wiem, jak zastosować "planistę procesorowego" do mojego zadania.

Jest jedna podstawowa różnica: algorytm szeregowania dąży do tego, by jak najszybciej być gotowym z robotą korzystając z wszystkich możliwych rdzeni/procesorów a ja potrzebuję przydzielenia "rdzeni/procesorów" do zadań w ten sposób, żeby byli gotowi w z góry określonym czasie a reszta ma "oszczędzać prąd"

@hot_stuff, dzięki za link, zaraz się wezmę za lekturę i zobaczymy co z "alorytmów planowania" da się zaadaptować do mojego przypadku.

Pozdrawiam