Search
Abstract
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
Authors (4)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Monographic publication
- Type:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
- Title of issue:
- W : Aplikacyjne metody obliczeniowe oraz zarządzanie danymi strony 60 - 70
- Language:
- Polish
- Publication year:
- 2017
- Bibliographic description:
- 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
- Verified by:
- Gdańsk University of Technology
seen 229 times