Warianty tytułu
Phase transitions in time-dependent scheduling
Konferencja
XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
Języki publikacji
Abstrakty
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.
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
Rocznik
Tom
Strony
163-172
Opis fizyczny
Bibliogr. 14 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0007-0067
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.