Dwukryterialne szeregowanie zadań czasowo-zależnych

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

Warianty tytułu

EN

Bicriterion time-dependent scheduling

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

Abstrakty

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.

Słowa kluczowe

PL

szeregowanie zadań; szeregowanie dwukryterialne; problem jednomaszynowy; zadania czasowo-zależne

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

Twórcy

autor

Gawiejnowicz S.

autor

Kurc W.

autor

Pankowska L.

• Uniwersytet im. Adama Mickiewicza, Poznań