Wyszukiwarka
Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów
Abstrakt
Rozważono problem szeregowania n zadań jednostkowych na 4 procesorach jednorodnych o szybkościach s1>=s2>=s3>=s4. Celem szeregowania jest utworzenie najkrótszego możliwego harmonogramu. Zadania podlegają ograniczeniom zasobowym mówiącym, że niektóre pary zadań nie mogą być wykonane na tym samym procesorze. Podajemy algorytm dokładny, który rozwiązuje problem w czasie liniowym, o ile graf niezgodności jest kubiczny. Ponadto podajemy algorytm przybliżony, który znajduje rozwiązanie optymalne, gdy s1>12s2 i s2=s3=s4, o ile graf niezgodności jest podbikwartyczny.
Autor (1)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja monograficzna
- Typ:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
- Tytuł wydania:
- Automatyzacja procesów dyskretnych : teoria i zastosowania, T. 1 strony 163 - 170
- Język:
- polski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- Kubale M.: Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów// Automatyzacja procesów dyskretnych : teoria i zastosowania, T. 1/ ed. Andrzej Świerniak, Jolanta Krystek Gliwice: Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, 2016, s.163-170
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 126 razy
Publikacje, które mogą cię zainteresować
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
- H. Furmańczyk,
- A. Kosowski,
- P. Żyliński
2008