eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingalgorytm szeregownia i grupowania zadan
Ilość wypowiedzi w tym wątku: 40

  • 1. Data: 2009-02-17 23:25:26
    Temat: algorytm szeregownia i grupowania zadan
    Od: "qweer" <cisrudlow[wytni]@o2.pl>

    Witam,
    Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
    Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
    koncowego. Musze okreslic kolejnosc wykonywania zadan i je pogrupowac.
    Kryterium grupowania, to mozliwosc wykonania kliku zadan w jednej chwili
    (grupa sklada sie z zadan, ktore moga byc wykonywane w danej chwili).
    Zakladam, ze ilosc maszyn jest nieograniczona. Oczywiscie zadania sa od
    siebie zalezne, ale dla kazdego mamy tylko informacje o jego najblizszych
    zaleznosciach, tj. wiemy tylko, jakie zadania ma sie wykonac krok wczesniej,
    zeby to moglo sie rozpoczac (tzn. taka informacja jest zawarta w samej
    definicji zadania). Koncowym wynikiem ma byc lista grup zadan (oczywiscie
    musze miec informacje co w tej grupie sie znajduje) uporzadkowana wg.
    kolejnosci wykonywania.
    Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
    optymalny dla takiego problemu.
    Z gory dzieki za pomoc



  • 2. Data: 2009-02-17 23:52:57
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: Michoo <m...@v...pl>

    qweer pisze:
    > Witam,
    > Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
    > Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
    > koncowego. Musze okreslic kolejnosc wykonywania zadan i je pogrupowac.
    > Kryterium grupowania, to mozliwosc wykonania kliku zadan w jednej chwili
    > (grupa sklada sie z zadan, ktore moga byc wykonywane w danej chwili).
    > Zakladam, ze ilosc maszyn jest nieograniczona. Oczywiscie zadania sa od
    > siebie zalezne, ale dla kazdego mamy tylko informacje o jego najblizszych
    > zaleznosciach, tj. wiemy tylko, jakie zadania ma sie wykonac krok wczesniej,
    > zeby to moglo sie rozpoczac (tzn. taka informacja jest zawarta w samej
    > definicji zadania). Koncowym wynikiem ma byc lista grup zadan (oczywiscie
    > musze miec informacje co w tej grupie sie znajduje) uporzadkowana wg.
    > kolejnosci wykonywania.
    > Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
    > optymalny dla takiego problemu.

    Najprostsze, choć może lekko nieoptymalne pamięciowo(przyjmuję założenie
    o jednostkowym rozmiarze zadania): Robisz graf skierowany w którym w
    węzłach masz licznik - na ile zadań dane zadanie czeka bezpośrednio oraz
    listę zadań które czekają na nie (odwrotnie niż w danych wejściowych).
    Przeglądasz dane 1 raz i do listy wrzucasz wszystkie zadania z
    licznikiem=0 - to jest 1 grupa. ->Dopóki są jakieś zadania na tej
    liście. Wypisz grupę, odejmij 1 od liczników każdego zadania na które
    wskazują te z listy dodając do drugiej listy te którym licznik się
    wyzerował. Wywal pierwszą listę. Aktualną listą jest 2 lista. Powtórz
    ->. Jeżeli w grafie zostały zadania z niezerowym licznikiem to znaczy,
    że był cykl.


    --
    Pozdrawiam
    Michoo


  • 3. Data: 2009-02-18 02:00:15
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: A.L. <a...@z...com>

    On Wed, 18 Feb 2009 00:25:26 +0100, "qweer" <cisrudlow[wytni]@o2.pl>
    wrote:

    >Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
    >optymalny dla takiego problemu.


    Nie ma algorytmu "najbardziej optymalnego"

    A.L.


  • 4. Data: 2009-02-18 02:01:31
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: A.L. <a...@z...com>

    On Wed, 18 Feb 2009 00:25:26 +0100, "qweer" <cisrudlow[wytni]@o2.pl>
    wrote:

    >Witam,
    >Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
    >Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
    >koncowego.

    No i co ten graf nam mowi?...

    A.L.


  • 5. Data: 2009-02-18 07:12:49
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: Wit Jakuczun <w...@g...com>

    On 18 Lut, 00:25, "qweer" <cisrudlow[wytni]@o2.pl> wrote:

    > Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
    > optymalny dla takiego problemu.

    Jak A.L. powiedział, nie ma najbardziej optymalnego algorytmu. Wg
    jakiego
    kryterium masz ułożyć te zadania?

    Pozdrawiam,
    Wit Jakuczun [ http://wlogsolutions.pl ]


  • 6. Data: 2009-02-18 09:15:31
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: Adam Kłobukowski <a...@k...pl>

    qweer pisze:
    > Witam,
    > Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
    > Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
    > koncowego. Musze okreslic kolejnosc wykonywania zadan i je pogrupowac.
    > Kryterium grupowania, to mozliwosc wykonania kliku zadan w jednej chwili
    > (grupa sklada sie z zadan, ktore moga byc wykonywane w danej chwili).
    > Zakladam, ze ilosc maszyn jest nieograniczona. Oczywiscie zadania sa od
    > siebie zalezne, ale dla kazdego mamy tylko informacje o jego najblizszych
    > zaleznosciach, tj. wiemy tylko, jakie zadania ma sie wykonac krok wczesniej,
    > zeby to moglo sie rozpoczac (tzn. taka informacja jest zawarta w samej
    > definicji zadania). Koncowym wynikiem ma byc lista grup zadan (oczywiscie
    > musze miec informacje co w tej grupie sie znajduje) uporzadkowana wg.
    > kolejnosci wykonywania.
    > Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
    > optymalny dla takiego problemu.
    > Z gory dzieki za pomoc

    Polecam książkę pt. "Badania operacyjne dla informatyków", niestety
    autora czy wydawnictwa nie pomnę, ale tam są całe stada algorytmów
    szeregowania zadań opisane.

    Adam Kłobukowski


  • 7. Data: 2009-02-18 13:00:05
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: A.L. <a...@z...com>

    On Tue, 17 Feb 2009 23:12:49 -0800 (PST), Wit Jakuczun
    <w...@g...com> wrote:

    >On 18 Lut, 00:25, "qweer" <cisrudlow[wytni]@o2.pl> wrote:
    >
    >> Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
    >> optymalny dla takiego problemu.
    >
    >Jak A.L. powiedział, nie ma najbardziej optymalnego algorytmu. Wg
    >jakiego
    >kryterium masz ułożyć te zadania?

    Ja powiedzialem dwie rzeczy:

    1. Jak ktos mowi "najbardziej oprtymalny" to ma klopoty z jezykiem
    polskim,,
    2. Algorytmy szeregowania zadan sa NP-complete, wiec trudno mowic o
    "optymalnym" algorytmie

    A.L.


  • 8. Data: 2009-02-18 13:04:38
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: A.L. <a...@z...com>

    On Wed, 18 Feb 2009 10:15:31 +0100, Adam K?obukowski
    <a...@k...pl> wrote:

    >
    >Polecam książkę pt. "Badania operacyjne dla informatyków", niestety
    >autora czy wydawnictwa nie pomnę, ale tam są całe stada algorytmów
    >szeregowania zadań opisane.
    >
    >Adam Kłobukowski

    Blazewicz, Cellary, Slowinski, Weglarz, "Badania operacyjne dla
    informatykow", WNT, 1983

    G. Coffman, "Teoria szeregowania zadan", WNT, 1980.

    Z nowszych:

    Smutnicki, "Algorytmy szeregowania" Akademicka Oficyna Wydawnicza
    EXIT, 2002

    Grabowski, Nowicki, Smutnicki, "Metoda blokowa w zagadnieniach
    szeregowanai zadan". EXIT, 2003

    A.L.


  • 9. Data: 2009-02-18 13:23:57
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: A.L. <a...@z...com>

    On Wed, 18 Feb 2009 07:00:05 -0600, A.L. <a...@z...com> wrote:

    >2. Algorytmy szeregowania zadan sa NP-complete, wiec trudno mowic o
    >"optymalnym" algorytmie

    Powinno byc

    Problemy szeregowania sa NP-complete...

    A.L.


  • 10. Data: 2009-02-18 13:36:37
    Temat: Re: algorytm szeregownia i grupowania zadan
    Od: " qweer" <c...@g...pl>


    > Najprostsze, choć może lekko nieoptymalne pamięciowo(przyjmuję założenie
    > o jednostkowym rozmiarze zadania): Robisz graf skierowany w którym w
    > węzłach masz licznik - na ile zadań dane zadanie czeka bezpośrednio oraz
    > listę zadań które czekają na nie (odwrotnie niż w danych wejściowych).
    > Przeglądasz dane 1 raz i do listy wrzucasz wszystkie zadania z
    > licznikiem=0 - to jest 1 grupa. ->Dopóki są jakieś zadania na tej
    > liście. Wypisz grupę, odejmij 1 od liczników każdego zadania na które
    > wskazują te z listy dodając do drugiej listy te którym licznik się
    > wyzerował. Wywal pierwszą listę. Aktualną listą jest 2 lista. Powtórz
    > ->. Jeżeli w grafie zostały zadania z niezerowym licznikiem to znaczy,
    > że był cykl.

    Tak, tak, ale nie mam tutaj ograniczen czasowych. Jest tylko ograniczenie
    zaleznosci kolejnosciowych. Jezeli byloby tak, to bym mogl tutaj wykorzystac
    lekko zmodyfikowany algorytm wyznaczania sceizki krytycznej (juz nie pamietam
    kogo to byl wynalazek)


    --
    Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

strony : [ 1 ] . 2 ... 4


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: