Wyniki wyszukiwania dla: ZŁOŻONOŚĆ OBLICZENIOWA

• Szeregowanie zadań metodami kolorowania grafów.Monografie 37.

  Publikacja

  • K. Giaro

  - Rok 2003

  Niniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów w szeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.

• NP-completeness of convex and weakly convex domiating set decision problems.

  Publikacja

  • J. Raczek

  - Opuscula Mathematica - Rok 2004

  Liczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.

  Pełny tekst do pobrania w portalu

• Classical coloring of graphs.

  Publikacja

  • A. Kosowski
  • K. Manuszewski

  - Rok 2004

  Rozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.

• Chromatyczne szeregowanie zadań w cyklicznych systemach produkcyjnych.

  Publikacja

  • A. Nadolski

  - Rok 2005

  Głównym celem pracy jest klasyfikacja złożoności obliczeniowej problemu szeregowania zadań w przypadku cyklicznej pracy systemu produkcyjnego. Rozważane są przy tym trzy modele szeregowania: system zadań dwuprocesorowych, system otwarty i system przepływowy. Kryterium optymalizacyjnym które jest analizowane jest długość cyklu wyrażająca częstość realizacji poszczególnych zestawów operacji. W pracy posługiwano się teorią grafów...

• Cykliczny system otwarty z ograniczeniami obustronnych przestojów

  Publikacja

  • A. Nadolski

  - Rok 2005

  W pracy badany jest system otwarty, który pracuje cyklicznie, tj. po ukończeniu jednego zestawu zadań przetwarzany jest kolejny zestaw identycznych zadań. Narzucone jest przy tym ograniczenie polegające na braku przestojów zarówno po stronie procesów jak i zadań. Wykazana jest NP-trudność problemu konstrukcji uszeregowania spełniającego te założenia jak i problemu minimalizacji długość i cyklu.

• Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych

  Publikacja

  • K. Giaro
  • M. Kubale

  - Rok 2005

  Szeregowanie jednostkowych zadań 1- i 2-procesorowych z dodatkowym ograniczeniem w postaci zróżnicowanych okien czasowych, w których zadania te mogą być wykonywane zamodelowano przy pomocy listowego kolorowania i multikolorowania krawędzi grafów. Kryteria jakości harmonogramu: maksymalny koszt wykonania zadania w jednostce czasu oraz suma tychże kosztów po wszystkich zadaniach można przedstawić rozszerzając kolorowanie listowe...