w artykule rozważany jest problem szeregowania zadań uwarunkowanych czasowo, w notacji trójpolowej opisywany przez 1 | pi = a + bisi | ?ci. wprowadzona jest koncepcja zdominowanych częściowych harmonogramów oraz przedstawiony jest niewielomianowy algorytm dla problemu, który bazuje na eliminacji zdominowanych częściowych harmonogramów. przedstawione są wyniki eksperymentów obliczeniowych, porównujących zaprezentowany algorytm oraz inne algorytmy dokładne dla problemu 1 | pi = a + bisi | ?ci (pełne przeszukiwanie, branch-and-bound). na koniec sprawdzona jest skuteczność algorytmu jako algorytmu przybliżonego dla problemów 1 | pi = a + bisi | ?wici, 1 | pi = ai + bisi | ?ci oraz 1 | pi = ai + bisi | ?wici.
Authors
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Language
- angielski
- Publication year
- 2010
