Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: modele kolorowania

Sortuj według:

Ogranicz wyniki do:

Wybrane zastosowania niestandardowych modeli kolorowania w szeregowaniu dwuprocesorowych zadań jednostkowych

Giaro K.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2003

T. 7, z. 1-2

105-111

Metodologia szeregowania zadań angażuje znaczne bogactwo środków: zastosowanie znajdują techniki optymalizacji kombinatorycznej, programowania liniowego, programowania dynamicznego, a także teorii grafów. 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. Ma on obrazować wzajemne zależności między zadaniami m.in. to, które pary zadań nie mogą być podejmowane równocześnie. Rozważmy więc system niepodzielnych jednostkowych zadań dwuprocesorowych. Wówczas zagadnienie szeregowania można zobrazować za pomocą formalizmu kolorowania krawędziowego, jako że warunki poprawności dla kolorowania i harmonogramu są równoważne. Pewne praktyczne zastosowania wprowadzają jednak do definicji nowe, bardziej złożone ograniczenia. W ten sposób dwie teorie: chromatyczna grafów i szeregowania zadań wzajemnie inspirują się. Bowiem pewne znane własności pokolorowań okazują się mieć bezpośrednie konsekwencje, określając cechy dopuszczalnych harmonogramów, zaś problemy szeregowania pozwalają tłumaczyć się na język grafów, definiując niestandardowe modele kolorowania. Omówimy niektóre zastosowania takich modeli w kontekście równoważenia obciążeń systemu w czasie oraz układania szkolnych planów zajęć.

Methods used in task scheduling engage many different tools like those of combinatorial optimization, linear programming, dynamic programming and graph theory. This work is a review of applications of chromatic graph theory in scheduling. The basic idea is to describe a set of tasks as edges of the so-called conflict graph. Its purpose is to present dependencies between tasks, for instance which pairs of them cannot be executed in the same time. For example, let us consider a set of nonpreemptive biprocessor unit time tasks. Then scheduling can be regarded as edgecoloring of conflict graph, because legality conditions for schedule and coloring are equivalent. However, some practical applications force new, more complicated conditions. In this way the two theories: task scheduling and graph coloring inspire each other. Some of coloring properties give features of legal schedules and scheduling problems can be expressed in the language of graph theory, which results in nonstandard coloring models. We deal with some of them having in a special view the problems of constructing school timetables and equalizing work in time.