-
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/