Wyszukiwarka
Abstrakt
W pracy rozważany jest problem szeregowania zadań dwuoperacyjnych w systemie otwartym (open-shop), z kryterium minimalizacji długości harmonogramu oraz sumy czasów zakończenia wszystkich zadań. Zakładając jednostkowe czasy wykonywania operacji można stosować efektywne metody chromatyczne rozwiązywania problemu, poprzez sprowadzenie go do modelu grafowego oraz zastosowanie w nim wybranego modelu kolorowania, które pozwala uzyskać optymalny harmonogram. W kontekście przetwarzania zadań w obliczeniach bazodanowych oraz komunikacji między serwerami, zaproponowany został szczególny model systemu otwartego, w którym operacjom przypisujemy dwa dedykowane procesory, o asymetrii wykorzystania: jeden procesor przetwarza operację w trybie wyłączności (write), drugi jest wykorzystywany w trybie współdzielenia (read). Przedstawiony został wielomianowy algorytm 2-przybliżony dla sumacyjnego kolorowania końcówkowego drzew oraz wielomianowe algorytmy optymalne dla sumacyjnego kolorowania końcówkowego prostych klas grafów. Słowa kluczowe: szeregowanie chromatyczne, sumacyjne kolorowanie końcówkowe, szeregowanie zadań, kolorowanie końcówkowe
Autorzy (4)
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:
- W : Aplikacyjne metody obliczeniowe oraz zarządzanie danymi strony 60 - 70
- Język:
- polski
- Rok wydania:
- 2017
- Opis bibliograficzny:
- Małafiejska A., Małafiejski M., Ocetkiewicz K., Pastuszak K.: Szeregowanie zadań dwuprocesorowych w systemach otwartych// Aplikacyjne metody obliczeniowe oraz zarządzanie danymi/ ed. Jakub Pizoń, Beata A. Nowak Lublin: Wydawnictwo Naukowe TYGIEL sp. z o.o., 2017, s.60-70
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 229 razy