Abstract

w pracy przedstawiono wyniki badań nad problemami szeregowania zadań uwarunkowanych czasowo. dla problemu 1|pi=a+bisi|σci przedstawiono nowe heurystyki, przypadek wielomianowy oraz w pełni wielomianowy schemat. wprowadzono koncepcję eliminacji zdominowanych fragmentów harmonogramu, oraz pokazano jak wykorzysta¢ ją do konstrukcji algorytmu dokładnego dla tego problemu, a także jak przy jej pomocy przyspieszy¢ inne algorytmy. następnie przeniesiono tę koncepcję na jednoprocesorowy problem 1|pi=ai+bisi|σwici i wieloprocesorowe problemy p| pi=a+bisi|σci i p| pi=ai+bisi|σwici. eliminacja zdominowanych fragmentów harmonogramów pozwoliła na zwiększenie rozmiaru instancji tych problemów, które jesteśmy w stanie rozwiązać w rozsądnym czasie, o średnio 50%. wreszcie przedstawiono wyniki zastosowania algorytmów metaheurystycznych do szeregowania zadań uwarunkowanych czasowo.

Author (1)