Numer: 09/2010 Str. 91
Autorzy: Adam Janiak , Paweł Kołodka , Tomasz Krysiak :
Tytuł: Szeregowanie zadań o zmiennych wartościach z różnymi terminami dostępności – algorytmy rozwiązania
Streszczenie: Praca dotyczy problemu szeregowania zadań o zmiennych wartościach i niezerowych terminach dostępności na pojedynczej maszynie. Analizowano potęgowy model wartości zadań, a jako kryterium – maksymalizację sumy wartości wszystkich zadań. Problem powyższy jest co najmniej NP-trudny. Do jego rozwiązania skonstruowano algorytm dokładny typu podziału i ogranicze´n oraz szereg algorytmów heurystycznych typu konstrukcyjnego, a także jeden typu popraw. Efektywność skonstruowanych algorytmów przebadano eksperymentalnie.
Słowa kluczowe: szeregowanie zadań, zmienne wartości, metoda podziału i ograniczeń, algorytm heurystyczny