p051(1)

p051(1), szeregowanie zadań

[ Pobierz całość w formacie PDF ]
HEURYSTYCZNY ALGORYTM SZEREGOWANIA ZADAŃ
W SYSTEMIE MASZYN RÓWNOLEGŁYCH Z KRYTERIUM
MINIMALNO-CZASOWYM
Zbigniew BUCHALSKI
Streszczenie:
Artykuł dotyczy zagadnienia czasowo-optymalnego przydziału zasobu po-
dzielnego w sposób ciągły i
n
zadań do
m
maszyn równoległych. Założono, że zadania są
niezależne i niepodzielne. Dla zadanej funkcji czasu realizacji zadań sformułowano model
formalny zagadnienia i zaproponowano pewien algorytm heurystyczny wyznaczający
czasowo-optymalne szeregowanie zadań i przydział zasobów do maszyn równoległych.
Przed-stawiono wyniki eksperymentów obliczeniowych przeprowadzonych na tym
algorytmie.
Słowa kluczowe:
systemy maszyn równoległych, szeregowanie zadań, rozdział zasobów,
algorytmy heurystyczne.
1. Wstęp
Odczuwalny od wielu lat gwałtowny rozwój równoległych systemów przetwarzania
informacji pociągnął za sobą potrzebę rozwiązywania problemów czasowo-optymalnego
szeregowania zadań i rozdziału zasobów [1, 2, 3, 4, 5]. Znaczenie praktyczne
rozwiązywania tych problemów jest bezsporne w wielu dziedzinach życia. Problemy te
mogą być związane przykładowo ze sterowaniem procesem produkcyjnym, wyznaczaniem
kolejnych etapów montażu urządzeń, harmonogramowaniem zadań transportowych, itp.
Zadania optymalizacji zarówno dyskretnej, jak i ciągłej należą do klasy problemów
bardzo trudnych zarówno z teoretycznego, jak i obliczeniowego punktu widzenia i
najczęściej należą do klasy problemów
NP
- zupełnych [6, 7, 8]. Doświadczenia z
podejmowania prób optymalizacji tego typu problemów wskazują na możliwość
osiągnięcia tą drogą znacznych efektów ekonomicznych. Istnieje więc pilna potrzeba
prowadzenia badań w tym zakresie i to zarówno podstawowych, jak i stosowanych.
W systemach maszyn równoległych spotykamy się z szeregowaniem zadań na
maszynach oraz przydziałem zasobów do maszyn. Przy rozwiązywaniu tych problemów
występują istotne trudności natury obliczeniowej w związku z czym eliminuje się z
rozważań algorytmy dokładne, pozostawiając do zastosowania praktycznego jedynie
algorytmy heurystyczne umożliwiające rozwiązanie postawionych problemów w krótkim
czasie z zadowalającą dokładnością [9, 10, 11].
W niniejszym artykule przedstawiono pewien algorytm heurystyczny wyznaczający
czasowo-optymalny rozdział
n
zadań niezależnych niepodzielnych i
N
jednostek zasobu
nieodnawialnego podzielnego w sposób ciągły do
m
maszyn pracujących równolegle.
Przedstawiono wyniki eksperymentów obliczeniowych przeprowadzonych na tym algo-
rytmie dla losowo generowanych danych.
548
2. Sformułowanie problemu
Rozpatrzmy dyskretny system produkcyjny zawierający maszyny połączone równolegle
przedstawiony na poniższym rysunku:
Rys. 1. System maszyn równoległych
Na system maszyn równoległych nakładamy następujące założenia:
(i) posiada
m
różnych maszyn
M
= {1, 2,...,
k,
... ,
m
}, na których należy wykonać
n
niezależnych zadań
Z
= {1, 2,...
, i
,...,
n
},
(ii) zadanie może być wykonywane na dowolnej maszynie i w trakcie jego
wykonywania nie może być przerywane,
(iii) liczba zadań do wykonania jest większa od liczby maszyn
n
>
m
,
(iv) realizacja każdego z zadań na maszynach musi następować niezwłocznie po
zakończeniu wykonywania poprzedniego zadania lub nastąpić w chwili zerowej,
gdy za-danie realizowane jest jako pierwsze na jednej z maszyn.
Niech
N
oznacza globalną ilość zasobów nieodnawialnych, a przez
u
k
oznaczmy tą
część zasobów, które zostaną przydzielone
k
-tej maszynie w trakcie wykonywania zadań
uszeregowanych na tej maszynie. Ograniczenie dotyczące zasobów jest następujące:
Czas wykonywania
i
-tego zadania na
k
-tej maszynie określony jest przez następującą
funkcję
T
i
(
u
k
,
k
):
549
(1)
Parametry
a
ik
> 0 i
b
ik
> 0 charakteryzują
i
-te zadanie i
k
-tą maszynę.
Należy znaleźć takie uszeregowanie zadań na maszynach i taki przydział ograniczonych
zasobów do maszyn równoległych, aby minimalizować czas zakończenia wykonania całego
zbioru zadań
T
zak
.
3. Model formalny zagadnienia
Jeżeli oznaczymy przez
Z
k

Z
zbiór zadań uszeregowanych na
k
-tej maszynie, to
T
zak
znajdziem
y
rozwiązując następujący problem minimalizacyjny:
(2)
Ograniczenia nałożone na rozwiązanie tego problemu są następujące:
Dla uproszczenia problemu przyjmiemy najpierw, że zasoby nieodnawialne
u
1
,
u
2
, ...,
u
m
są typu ciągłego. Przy tym założeniu wyznaczymy rozwiązanie optymalne, a następnie
zaokrąglimy otrzymane wartości zasobów do najbliższych liczb naturalnych.
Czas
T
zak
znajdziemy rozwiązując następujący problem minimalizacji dyskretno-ciągłej:
przy następujących ograniczeniach:
550
Do rozwiązania postawionego problemu pomocny będzie następujący lemat:
LEMAT 1
Jeżeli
m
*
*
są rozwiązaniami optymalnymi zadania (3), to
:
Zu
k
,
,
k

1
2
,...,
k
Warunek (i) w
LEMACIE 1
oznacza, że w przydziale czasowo-optymalnym zasobów
i zadań do maszyn wykorzystuje się wszystkie jednostki zasobów, a warunek (ii), że czasy
pracy tych maszyn, na których wykonywane są jakieś zadania, są identyczne.
Zdefiniujmy funkcję
F
(
Z
1
,
Z
2
, ...,
Z
m
) określoną dla
m
zbiorów
Z
1
,
Z
2
, ...,
Z
m
, dla których
zachodzi ograniczenie (i) dla wzoru (3). Wartość tej funkcji jest rozwiązaniem
następującego układu równań:
Wykorzystując
LEMAT 1
oraz (5) zadanie minimalizacji (3) można przedstawić w nas-
tępującej postaci:
przy następujących ograniczeniach:
551
*
1
*
2
*
*
*
Jeżeli
ZZ
jest rozwiązaniem zadania (6), to
m
,..,
m
Z
Zu
k
,
,
k

1
2
,...,
, gdzie:
k
jest rozwiązaniem zadania (3).
4. Algorytm heurystyczny
Maszyny wchodzące w skład systemu maszyn równoległych różnią się pod względem
szybkości wykonywanych zadań. Na szybkość tą wpływ ma ilość zasobów przydzielonych
poszczególnym maszynom. Im więcej zasobów zostanie przydzielonych
k
-tej maszynie,
tym będzie ona szybsza.
Zasoby przydzielone zostają do maszyn w następujący sposób:

miarą szybkości realizacji
i
-tego zadania przez
k
-tą maszynę jest tzw. współczynnik
podziału zasobów ;  > 1,

zakładamy, że maszyną najszybszą jest maszyna pierwsza, a maszyną
najwolniejszą jest maszyna
m
-ta,

maszynie
m
-tej przydzielamy
u
m
zasobów wg następującej zależności:

pozostałym maszynom przydzielamy zasoby wg następującej zależności:
Przedstawiony powyżej sposób przydziału zasobów do maszyn wykorzystany zostanie
w zaproponowanym heurystycznym algorytmie szeregowania zadań na równoległych
maszynach. Algorytm ten skonstruowany został w taki sposób, że najpierw szereguje on
zadania na jednakowych maszynach, tj. takich, do których przydzielona została jednakowa
N
liczba dostępnych zasobów, czyli
m
u
k

, 
k
1
2
...
,
(
Kroki
4

11
).
Po
tym
m
uszeregowaniu następuje zróżnicowanie maszyn pod względem liczby przydzielanych im
zasobów i sprawdzenie czy skrócony został czas zakończenia wykonywania wszystkich
zadań
T
zak
(
Kroki 12

15
).
Algorytm heurystyczny wyznaczający czasowo-optymalne
szeregowanie zadań
niezależnych na maszynach równoległych ma następującą postać:
552
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

anio102.xlx.pl