Wyniki wyszukiwania - BazTech

1

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

Gawiejnowicz S., Kurc W., Pankowska L.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 134

163-172

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.

2

Dwukryterialne szeregowanie zadań czasowo-zależnych

Gawiejnowicz S., Kurc W., Pankowska L.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 134

151-162

PL

W pracy rozważany jest jednomaszynowy problem szeregowania zadań czasowo-zależnych z jednoczesną minimalizacją dwu kryteriów. Czas wykonywania pj zadania j jest funkcją czasu rozpoczęcia t tego zadania, pj=1+alfa jt, gdzie alfa j > 0 dla j=0,1,2,...,n. Zadania są niepodzielne, niezależne, nie ma czasów gotowości ani linii krytycznych. Kryterium optymalności uszeregowania ||.||(lambda) jest ważoną sumą kryteriów Cmax oraz SigmaCj postaci ||C||(lambda) = LambdaSigmaCj + (1-lambda)Cmax, gdzie lambda < [0,1] jest dowolną, ustaloną liczbą rzeczywistą, a C jest wektorem czasów zakończenia zadań. Przedstawiono twierdzenia mówiące, iż istnieje takie lambda o > 0, że dla wszystkich lambda < [0,lambda o] problem ten jest rozwiązywalny w czasie 0(nlogn) oraz takie lambda 1< 1, że dla wszystkich lambda < [lambda 1, 1] optymalne uszeregowanie dla tego problemu jest V-kształtne. Podano także dolne i górne oszacowania stosunku wartości kryterium ||.||(lambda) do wartości kryteriów Cmax oraz SigmaCj.

EN

In the paper a single machine time-dependent scheduling problem with simultaneous minimization of two criteria is considered. Processing time pj of job j is a function of the starting time t of the job, pj=1+alfa jt, where alfa j > 0 for j=0,1,2,...,n. The jobs are nonpreemptable, independent, there are neither ready times nor deadlines. The criterion of a schedule optimality ||.||(lambda) is a weighted sum of Cmax and SigmaCj criteria, ||C||(lambda) = lambda SigmaCj + (1-lambda)Cmax, where lambda < [0,1] is an arbitrary, fixed real number and C is a vector of completion times of jobs. There are presented theorems saying that there exists lambda o > 0 such that for all lambda < [0,lambda o] the problem is solvable in 0(nlogn) time and lambda 1 < 1 such that for all lambda < [lambda 1,1] an optimal schedule for the problem has a V-shape. There are also given lower and upper bounds for the ratio of values of the criterion ||.||(lambda) and values of Cmax and SigmaCj criteria.

3

Algorytm zachłanny dla pewnego problemu szeregowania zadań czasowo-zależnych

Gawiejnowicz S., Kurc W., Pankowska L.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 134

139-150

PL

W pracy jest rozważany jednomaszynowy problem szeregowania zadań czasowo-zależnych. Czas wykonywania pj zadania j jest funkcją czasu t rozpoczęcia tego zadania, pj(t) = 1 + alfa jt, gdzie alfa j > O dla j = O, 1, ... ,n. Zadania są niepodzielne, niezależne, nie ma czasów gotowości ani linii krytycznych, a kryterium optymalności uszeregowania jest łączny czas zakończenia wykonywania zadań. Dla danego ciągu współczynników alfa j, j = O, 1, ... ,n definiowana jest sygnatura, której własności stanowią podstawę do skonstruowania algorytmu zachłannego.

EN

A single machine time-dependent scheduling problem is considered. The processing time pj of job j is a function of the starting time t of the job, pj(t) = 1 + alfa jt, where alfa j > 0 for j = 0, 1, ... ,n. Jobs are non-preemptable and independent, there are neither ready times nor deadlines, and the criterion of optimality is the total completion time. On the ground of properties of a signature for a given sequence of coefficients alfa j, j = 0,1, ... ,n a greedy algorithm for the problem is constructed.