Repozytorium publikacji - Politechnika Gdańska

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

• dr inż. Anna Małafiejska link otwiera się w nowej karcie ,
• dr hab. inż. Michał Małafiejski link otwiera się w nowej karcie ,
• dr inż. Krzysztof Ocetkiewicz link otwiera się w nowej karcie ,
• mgr inż. Krzysztof Pastuszak link otwiera się w nowej karcie