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

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

Warianty tytułu

EN

A greedy algoritm for a time-dependent scheduling problem

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

Abstrakty

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.

Słowa kluczowe

PL

szeregowanie zadań; problem jednomaszynowy; zadania czasowo-zależne; algorytm zachłanny

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

Twórcy

autor

Gawiejnowicz S.

autor

Kurc W.

autor

Pankowska L.

• Uniwesytet im. Adama Mickiewicza, Poznań