Orzejścia fazowe w szeregowaniu zadań czasowo-zależnych

• Autorzy: Gawiejnowicz S. , Kurc W. , Pankowska L.

Warianty tytułu

EN

Phase transitions in time-dependent scheduling

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

W pracy rozważamy złożoność problemu szeregowania postaci 1 | pj(t)=1+alfa jt | ||C||p jako funkcję parametru p. Dowodzimy istnienia takich liczb po < p1, że w kolejnych przedziałach: (1, po ], (po < p1], (p1, + ) złożoność wyrażona jest odpowiednio wzorami: 0(2n), 0(nk + nlogn), 0(nlogn), gdzie k=1,2,...,0(f(n)),. Wyniki te ujawniają wewnętrzną naturę badanego problemu dostarczając argumentów, że dla 1 < p < po należy oczekiwać złożoności 0(2n). Zastosowaniem rezultatów są wielomianowe metody przybliżone dla kryterium ||C||1 = SigmaCj.

EN

In the paper we study the complexity of the linear time-dependent problem 1 | pj(t)=1+alfa jt | ||C||p as a function of a parameter p. We show that there exist numbers po < p1 such that in the intervals (1, po ], (po < p1], (p1, + ) the complexity is given by 0(2n), 0(nk+nlogn) and 0(nlogn), respectively, for k=1,2,...,0(f(n)). Such approach explains intrinsic nature of the problem and gives a basis for construction of approximate algorithms in the case of ||C||1=SigmaCj.

Słowa kluczowe

PL

szeregowanie zadań; zadania czasowo-zależne; przejścia fazowe

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 163--172
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Gawiejnowicz S.

autor

Kurc W.

autor

Pankowska L.

• Uniwersytet im. Adama Mickiewicza, Poznań