Search results for: SZEREGOWANIE ZADAŃ
-
Uszeregowania zadań wieloprocesorowych minimalizuje średni czas przepływu
PublicationW artykule rozważane są problemy efektywnego wyznaczania uszeregowań wieloprocesorowych dla zadań jednostkowych na dedykowanych procesorach równoległych, które minimalizują średni czas przepływu.
-
High level synthesis with adaptive evolutionary algorithm for solving reliability and thermal problems in reconfigurable microelectronic systems.
PublicationPraca dotyczy badań efektywności adaptacyjnego algorytmu ewolucyjnego (AEA)zastosowanego do syntezy wysokiego poziomu układów cyfrowych CMOS w celu zredukowania rozpraszanej przez nie mocy. W wyniku obniżenia poziomu mocy pobieranej przez układ mikroelektroniczny uzyskuje się zmniejszenie szczytowej i średniej temperatury układu scalonego co z kolei prowadzi do wzrostu niezawodności całego systemu. Podczas przeprowadzonych...
-
Wybrane zastosowania niestandardowych modeli kolorowania w szeregowniu dwu-procesowych zadań jednostkowych
PublicationNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów wszeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
SDL i prosty scheduler - zastosowania.
PublicationRozdział przedstawia uzupełnienia, usprawnienia i zastosowania prostego schedulera zaproponowanego w [1]. Podstawowym uzupełnieniem jest powiązanie funkcji schedulera z językiem specyfikacji protokołów telekomunikacyjnych SDL [2]. Pokazano na czym polega problem w odmierzaniu czasu w ''procesach'' obsługiwanych przez scheduler oraz istotne ograniczenia mechanizmu odmierzania czasu w systemach warstwowych. Zaproponowano rozwiązania...
-
Shared processor scheduling of multiprocessor jobs
PublicationWe study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublicationW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo
Publicationw artykule tym rozważany jest następujący problem szeregowania zadań: dany jest jeden procesor, zbiór zadań j1, ..., jn, czas przetwarzania zadania i wynosi pi = a + bisi, zaś celem jest minimalizacja całkowitego czasu wykonywania zadań. przedstawiony został pełny wielomianowy schemat aproksymacyjny, który, o ile wszystkie współczynniki wydłużania zadań (bi) w instancji problemu są różne i większe od pewnej, ustalonej liczby u,...
-
Metaheurystyki w szeregowaniu zadań uwarunkowanych czasowo
Publicationw artykule tym zbadano zastosowanie algorytmów metaheurystycznych w problemach szeregowania zadań uwarunkowanych czasowo. porównano wyniki algorytmu genetycznego, ewolucji różnicowej oraz symulowanego wyżarzania, z reprezentacjami rozwiązania: permutacyjną, opartą o priorytety reguł i kodowaniem przedziałowym, osiągnięte w rozwiązywaniu np-trudnego problemu 1 | pi = ai + bisi | sum wici. gdzie to możliwe, wyniki porównano z rozwiązaniami...
-
Zarządzanie opóźnieniami w ruchu kolejowym z zastosowaniem rogramowania ewolucyjnego
PublicationZarządzanie opóźnieniami w ruchu kolejowym zostało potraktowane jako wielokryterialny problem optymalizacyjny, który obejmuje między innymi zapewnienie skomunikowania pociągów na stacjach węzłowych oraz dążenie do uzyskania biegu pociągów najbardziej zgodnego z pierwotnym rozkładem jazdy. Uwzględniono priorytety poszczególnych pociągów uzależnione od sytuacji ruchowej i kategorii pociągów. W przeprowadzonym procesie optymalizacji...
-
Formalizm i metody szeregowania zadań dla potrzeb redukcji poboru mocy cyfrowych układów CMOS
PublicationW pracy przedstawiono związki pomiędzy modelami formalnymi stosowanymi w klasycznym szeregowaniu zadań a metodami wykorzystywanymi w syntezie wysokiego poziomu układów cyfrowych CMOS. Zagadnienia optymalizacyjne pojawiające się w obu tych problemach mogą być w pewnym sensie transformowalne. Pozwala to na przenoszenie wybranych metod rozwiązań z jednego problemu do drugiego.
-
Heuristic scheduling algorithms for uniform load of computer system
PublicationW pracy zaprezentowano opracowany heurystyczny algorytm szeregowania zadań UNILO (ang. UNIform LOad - jednakowe obciążenie), umożliwiający redukcję całkowitego zapotrzebowania na moc obliczeniową systemu komputerowego bez pogarszania jego wydajności. Algorytm ten realizuje takie przydzielenie zadań obliczeniowych do poszczególnych jednostek (procesorów), aby zapewnić ich jednakowe obciążenie. Opracowany algorytm został zweryfikowany...
-
Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania
PublicationW pracy rozważany jest następujący, jednoprocesorowy problem szeregowania zadań czasowo-zależnych. danych jest n+1 zadań o czasach wykonywania postaci pi = a + bisi, gdzie si oznacza czas rozpoczęcia wykonywania i-tego zadania, a > 0, bi > 0, i = 0, 1, ..., n. wszystkie zadania są niepodzielne i dostępne w chwili t0 = 0. należy znaleźć harmonogram minimalizujący łączny czas zakończenia. w pracy przedstawiono algorytm, który, o...
-
A polynomial algorithm for some preemptive multiprocessor task scheduling problems.
Publication.
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublicationRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
Jak transportować produkty chemiczne, czyli przypadek wsadowego szeregowania zadań kompatybilnych
PublicationPokazano, że pewien problem transportu produktów chemicznych może być sprowadzony do problemu szeregowania identycznych zadań kompatybilnych na wsadowych maszynach jednorodnych i rozwiązany metodami kolorowania grafów. Ponieważ problem ten jest NP-trudny, zbadano przypadki szczególne, które dają się rozwiązać w czasie kwadratowym. Rozważania ogólne są wsparte doświadczeniami komputerowymi zebranymi w trakcie implementacji wybranych...
-
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...
-
Zastosowanie metod opartych na ewolucji populacji do szeregowania zadań pro-dukcyjnych.**2002, 120 s. rys. tab. w rozdz. bibliogr. 137 poz. maszyn. Rozprawa doktorska (08.05.2002) Promotor: prof. dr hab. Piotr Jędrzejowicz, Akad. Morska w Gdyni.
Publication.
-
Algorytmy przybliżone dla wybranych problemów równoległego przydziału zasobów
PublicationArtykuł poświęcony jest zachłannym algorytmom przybliżonym dla problemu szeregowania zadań w systemach równoległych z zadaniami dedykowanymi.