Rozważono problem szeregowania n zadań jednostkowych na 4 procesorach jednorodnych o szybkościach s1>=s2>=s3>=s4. Celem szeregowania jest utworzenie najkrótszego możliwego harmonogramu. Zadania podlegają ograniczeniom zasobowym mówiącym, że niektóre pary zadań nie mogą być wykonane na tym samym procesorze. Podajemy algorytm dokładny, który rozwiązuje problem w czasie liniowym, o ile graf niezgodności jest kubiczny. Ponadto podajemy algorytm przybliżony, który znajduje rozwiązanie optymalne, gdy s1>12s2 i s2=s3=s4, o ile graf niezgodności jest podbikwartyczny.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja monograficzna
- Typ
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku o zasięgu krajowym
- Język
- polski
- Rok wydania
- 2016
