Filters
total: 58
filtered: 51
-
Catalog
Chosen catalog filters
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.
-
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.
-
Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych
Publicationartykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. model matematyczny, który tutaj zastosowano to szeregowanie zadań uwarunkowanych czasowo. przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie
-
Porównanie wybranych algorytmów szeregowania zadań dla potrzeb redukcji poboru mocy cyfrowych układów CMOS.
PublicationSzeregowanie zadań stosowane dla potrzeb redukcji poboru mocy cyfrowych układów CMOS prowadzi do problemów NP trudnych. Stąd też brakuje analitycznych algorytmów gwarantu-jących uzyskanie optymalnego rozwiązania w akceptowalnym czasie. Praca prezentuje porównanie jakości rozwiązań wyznaczonych heurystycznymi algorytmami szeregowania zadań stosowanych na etapie syntezy wysokiego poziomu cyfrowych układów CMOS, które zostały uzyskane...
-
Shared processor scheduling
PublicationWe study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an (log)-time optimization algorithm for a class...
-
Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
PublicationArtykuł podejmuje problem szeregowania zadań przy założeniu podziału czasu na sloty jednakowej długości, gdzie każde z zadań ma ustaloną długość oraz czas jego zakończenia, który jest relatywny do końca slotu. Problem znalezienia uszeregowania polega na dokonaniu przydziału zadań do poszczególnych slotów, przy czym w ogólności długość zadania może wymuszać sytuację, w której zadańie jest realizowane nie tylko w slocie, w którym...
-
Normal-form preemption sequences for an open problem in scheduling theory
PublicationStructural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems,...