Search
Search results for: SZEREGOWANIE ZADAŃ
-
Szeregowanie zadań uwarunkowanych czasowo
Publicationw pracy przedstawiono wyniki badań nad problemami szeregowania zadań uwarunkowanych czasowo. dla problemu 1|pi=a+bisi|σci przedstawiono nowe heurystyki, przypadek wielomianowy oraz w pełni wielomianowy schemat. wprowadzono koncepcję eliminacji zdominowanych fragmentów harmonogramu, oraz pokazano jak wykorzysta¢ ją do konstrukcji algorytmu dokładnego dla tego problemu, a także jak przy jej pomocy przyspieszy¢ inne algorytmy. następnie...
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublicationW 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ć...
-
Szeregowanie zadań sprzężonych metodą kolorowania grafów
PublicationRozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.
-
Szeregowanie zadań produkcyjnych na jednej maszynie
Publication...
-
Szeregowanie zadań metodami kolorowania grafów.Monografie 37.
PublicationNiniejsza 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.
-
Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi
PublicationW artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.
-
Chromatyczne szeregowanie zadań w cyklicznych systemach produkcyjnych.
PublicationGłó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...
-
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
PublicationProblem szeregowania jednostkowych zadań wieloprocesorowych na maszynach dedykowanych można modelować przy pomocy hipergrafów. Znamy kilka klas hipergrafów, dla których szeregowanie z kryterium kosztu całkowitego jest wielomianowe. Pokażemy jak przy pomocy modelu z kosztem całkowitym można rozwiązać problemy z innymi kryteriami znanymi z teorii szeregowania, oraz jak rozwiązać problemy dwukryterialne.
-
Szeregowanie zadań wieloprocesorowych na maszynach dedykowanych w modelu hipergrafowym
PublicationOstatnimi czasy obserwujemy dwie tendencje w działalności człowieka. Pierwszą jest specjalizacja. Wobec rosnącej wiedzy i zaawansowania technologicznego, niemożliwym stało się, by jedna osoba mogła wiedzieć i robić wszystko. Podobnie jest z maszynami, które im są bardziej wyspecjalizowane tym są tańsze i tym lepiej wykonują swoje zadania. Druga tendencja to wieloprocesorowość, którą inaczej możemy nazwać pracą zespołową. Efekt...
-
Parallel scheduling by graph ranking
PublicationNr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...
-
Podzielne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych w celu minimalizacji sumy czasów zakończenia
PublicationW 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.
-
Badania operacyjne - Szeregowanie zadań
e-Learning CoursesTematyka szeregowania zadań stanowi jeden z głównych nurtów badań operacyjnych. Podejmuje ona problemy planowania pracy i układania harmonogramów, dotychczas zdefiniowała tysiące rozmaitych modeli obejmujących różnorodne rodzaje zadań, wykorzystywane przez nie zasoby i tryby pracy. Głównym celem, jaki stawia sobie teoria jest opracowanie efektywnych algorytmów umożliwiających tworzenie harmonogramów optymalnych w sensie określonego...
-
Badania operacyjne - Szeregowanie zadań (2021)
e-Learning CoursesKurs dla kierunku Informatyka, stopień II, sem. I, studia stacjonarne. Jest to trzecia część przedmiotu Badania Operacyjne.
-
Badania operacyjne - Szeregowanie zadań (2022)
e-Learning CoursesKurs dla kierunku Informatyka, stopień II, sem. I, studia stacjonarne. Jest to trzecia część przedmiotu Badania Operacyjne.
-
Badania operacyjne - Szeregowanie zadań (2024)
e-Learning CoursesKurs dla kierunku Informatyka, stopień II, sem. I, studia stacjonarne. Jest to trzecia część przedmiotu Badania Operacyjne.
-
Badania operacyjne - Szeregowanie zadań (2023)
e-Learning CoursesKurs dla kierunku Informatyka, stopień II, sem. I, studia stacjonarne. Jest to trzecia część przedmiotu Badania Operacyjne.
-
Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów
PublicationRozważono problem szeregowania n zadań jednostkowych na 4 procesorach jednorodnych o szybkościach s1>=s2>=s3>=s4. Celem szeregowania jest utworzenie najkrótszego możliwego harmonogramu. Zadania podlegają ograniczeniom zasobowym mówiącym, że niektóre pary zadań nie mogą być wykonane na tym samym procesorze. Podajemy algorytm dokładny, który rozwiązuje problem w czasie liniowym, o ile graf niezgodności jest kubiczny. Ponadto podajemy...
-
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych
PublicationSzeregowanie 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...
-
Wsadowe i cykliczne szeregowanie 1- i 2-procesorowych zadań jednostkowych na maszynach dedykowanych.
PublicationW pracy autorzy zajmują się modelem szeregowania zadań 1- i 2- procesorowych. Rozważane są przy tym dwa warianty: klasyczny określany jako wsadowy i cykliczny, który występuje w przypadku wielokrotnego powtarzania raz zaprojektowanego harmonogramu. Dla obu przypadków badane są własności teoretyczne i konstruowane algorytmy przybliżone.
-
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublicationRozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.