Rok 2002

• Algorytmy przybliżone dla wybranych problemów równoległego przydziału zasobów

  Publikacja

  • R. Janczewski
  • M. Małafiejski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  Artykuł poświęcony jest zachłannym algorytmom przybliżonym dla problemu szeregowania zadań w systemach równoległych z zadaniami dedykowanymi.

• Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.

  Publikacja

  • M. Kubale
  • A. Kosowski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  W pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym, dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.

• Cyrkularny indeks chromatyczny grafów kubicznych

  Publikacja

  • A. Nadolski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  W pracy omówiono własności cyrkularnego indeksu chromatycznego grafów kubicznych. Po zdefiniowaniu tego rodzaju kolorowania zbadano, które ze znanych wyników dla klasycznego kolorowania krawędzi grafów kubicznych można przenieść na rozważany model kolorowania. Dodatkowo podano nietrywialne oszacowanie na cyrkularny indeks chromatyczny dla nieskończonej rodziny grafów kubicznych klasy 2.

• O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach

  Publikacja

  • K. Giaro
  • R. Janczewski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  Niniejszy artykuł poświęcony jest złożoności obliczeniowej problemu przydziału częstotliwości. Zawiera dowód tego, że jest on NP-trudny nawet dla grafów interferencji, będących grafami dwudzielnymi, oraz wielomianowy algorytm rozwiązujący ten problem dla grafów interferencji, będących częściowymi k-drzewami.

• Podzielne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych w celu minimalizacji sumy czasów zakończenia

  Publikacja

  • M. Małafiejski
  • Ł. Kuszner
  • M. Kubale

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  W pracy rozważamy deterministyczne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych, które minimalizuje sumę czasów zakończenia, przy czym dopuszcza się możliwość przerwania wykonywania zadania i ponownego wznowienia obsługi z pomijalnie małym kosztem. Wiadomo, że tak postawione zagadnienie jest problemem silnie NP-trudnym. W pracy badamy złożoność obliczeniową problemu, ograniczając liczbę maszyn.

• Programowanie dynamiczne w rozwiązywaniu problemów szeregowania zadań w systemach o acyklicznej strukturze

  Publikacja

  • K. Giaro
  • M. Kubale

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  Rozważono rozrzedzone systemy niepodzielnych zadań dwuprocesorowych o jednostkowych długościach operacji oraz systemy maszyn dedykowanych (open shop,flow shop, mixed shop) o operacjach zero-jedynkowych. Przedstawiono rodzinę wielomianowych algorytmów opartych na programowaniu dynamicznym, pozwalających na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano...

• Rozproszone kolorowanie grafów

  Publikacja

  • Ł. Kuszner

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  W pracy zaprezentowano nowy rozproszony algorytm kolorowania grafów. Przeprowadzone eksperymenty pokazują, że daje on lepsze wyniki niż znany wcześniej algorytm trywialny.

• T-SL, T-SLF i T-DSATUR - nowe heurystyki dla problemu przydziału częstotliwości

  Publikacja

  • R. Janczewski
  • M. Małafiejski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  Niniejszy artykuł poświęcony został algorytmom T-SL, T-SLF i T-DSATUR - nowym heurystykom dla problemu przydziału częstotliwości. Zawiera opis algorytmów, omówienie ich teoretycznych własności oraz wyniki testów komputerowych, którym zostały poddane.

• Uporządkowane kolorowanie wierzchołków grafów

  Publikacja

  • M. Kubale
  • D. Dereniowski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 2002

  W pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie...