No/VOL: 09/2010 Page no. 91
Authors: Adam Janiak , Paweł Kołodka , Tomasz Krysiak :
Title: Szeregowanie zadań o zmiennych wartościach z różnymi terminami dostępności – algorytmy rozwiązania
Abstract: 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.
Key words: szeregowanie zadań, zmienne wartości, metoda podziału i ograniczeń, algorytm heurystyczny