Wybrane zastosowania niestandardowych modeli kolorowania w szeregowaniu dwuprocesorowych zadań jednostkowych

• Autorzy: Giaro K.

Warianty tytułu

EN

A survey of applications of some nonstandard coloring models in task scheduling

• Języki publikacji: PL

Abstrakty

PL

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ęć.

EN

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 non­standard coloring models. We deal with some of them having in a special view the problems of constructing school timetables and equalizing work in time.

Słowa kluczowe

PL

grafy; szeregowanie zadań; modele kolorowania; teoria chromatyczna grafów; niestandardowe modele kolorowania

EN

graph; nonstandard coloring models; task scheduling

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 105--111
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Giaro K.

• Wydział Elektroniki, Telekomunikacji i Informatyki, Politechnika Gdańska

Bibliografia

• [1] Asratian A.: A note on weekly school timetables without interruptions. Res. Report, 14, Lulea University of Technology 1998
• [2] Asratian A., Kamalian R.: Investigation on interval edge-colorings of graphs. J. Comb. Theory, (B) 62, 1994, 34-43
• [3] Brelaz D., Nicolier Y., de Werra D.: Compactness and balancing in scheduling. Zeitschr. Oper. Res., 21, 1977, 65-73
• [4] Coffman E. Jr., Garey M., Johnson D., LaPaugh A.: Scheduling file transfers. SIAM J. Computing, 14, 1985, 744-780
• [5] Cole R., Ost K., Schirra S.: Edge coloring bipartite multigraphs in O(ElogD) time. Combinatorica, 21,2001,5-12
• [6] Even S., Itai A., Shamir A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Computing, 5, 1976, 691-703
• [7] Giaro K.: Szeregowanie zadań na procesorach dedykowanych bez obustronnych postojów. Gdańsk, Politechnika Gdańska, Wydział ETI 1999 (praca doktorska)
• [8] Giaro K.: NP-hardness of compact scheduling in simplified open and flow shops. EJOR, 130, 2001, 90-98
• [9] Giaro K.: Zwarte kolorowanie krawędzi, [w:] Kubale M. (Ed.), Optymalizacja dyskretna. Modele i metody kolorowania grafów, Warszawa, WNT 2002, 167-189
• [10] Giaro K., Kubale M.: Edge-chromatic sum of trees and bounded cyclicity graphs. Inf. Process. Lett., 75, 2000, 65-69
• [11] Holyer: The NP-completeness of edge-coloring. SIAM J. Comput., 10, 1981, 718-720
• [12] Krawczyk H„ Kubale M.: An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans. Comp., C-34, 1985, 869-872
• [13] Sanders P., Solis-Oba R.: How helpers hasten h-relations. J. Algorithms, 41, 2001, 86-98
• [14] Meyer W.: Equitable coloring. Amer. Math. Monthly, 80, 1973, 920-922
• [15] Sevastianow S.: On interval colorability of a bipartite graph, (po rosyjsku), Met. Diskret. Analiz., 50, 1990, 61-72
• [16] Vizing V.: On an estimate of the chromatic class of a p-graph. (po rosyjsku), Met. Diskret. Analiz., 3, 1964, 25-30
• [17] de Werra D.: On the particular conference scheduling problem. INFOR, 13, 1975, 308-315