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.

4

Minimalizacja maksymalnej nieterminowości dla zadań czasowo zależnych

Bachman A., Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 123

23-31

PL

W pracy rozpatrywano jednomaszynowy problem szeregowania zadań czasowo zależnych przy kryterium minimalizacji maksymalnej nieterminowości wykonania. Założono, że czas wykonywania zadania, dany w postaci liniowej, niemalejącej funkcji terminu rozpoczęcia wykonywania składa się z dwóch części: stałej i zmiennej. Stała część, niezależna od terminu rozpoczęcia, określa pewną minimalną długość czasu wykonywania zadania, wynikającą z uwarunkowań technologicznych. Natomiast zmienna część, charakteryzowana przez czynnik wzrostu, opisuje wpływ terminu rozpoczęcia wykonywania na wydłużenie zadania. Pokazano, że przy tak scharakteryzowanym modelu jednomaszynowy problem szeregowania zadań przy kryterium minimalizacji maksymalnej nieterminowości jest NP-zupełny.

EN

The paper deals with the single machine scheduling problem, where the job processing time is given as a linear, nondecreasing function dependent on the processing start time. The function describing the job processing time consists of two parts, where one is constant and describes the minimal time required to complete the job if its starting moment is equal to zero. The second part, characterized by the growth rate, describes how fast the job processing time deteriorate. We showed that such a described problem for the maximum lateness criterion is NP-complete by reducing to it NP-complete Partition Problem.