Szeregowanie zadań w systemach silnie uwarunkowanych czasowo metodą cyklicznego obciążenia

W artykule przedstawione są wyniki badań dotyczących zastosowania metody minimalizacji obciążeń cyklicznych do szeregowania zadań silnie uwarunkowanych czasowo o okresach tworzących postęp binarny. Pokazano, że problem taki jest silnie NP-trudny i w związku z tym algorytm o złożoności wielomianowej nie istnieje. W tej sytuacji zaproponowana została prosta heurystyka zachłanna, która - jak wynika z przeprowadzonych eksperymentów obliczeniowych - zachowuje się lepiej od innych tego typu znanych heurystyk. Zastosowana do szeregowania zadań w samolocie F-16 dała w bardzo krótkim czasie optymalne rozwiązanie.

---

In the paper scheduling hard real-time by minimising periodic loading is studied. It is assumed that task periods belong to a binary geometrical progression. It is shown that such a problem is strongly NP-hard. Thus, a simple greedy heuristics is proposed, which - due some computational experiments - is pretty effective and better than other greedy heuristics for the periodic loading problem. Applied to scheduling tasks for F-16 the heuristics returned an optimal solution in a very short time.