5102077449

3 PROBLEM HARMONOGRAMOWANIA

3.1    ZADANIE

Analizowany problem harmonogramowania polega na wybraniu oraz ułożeniu w odpowiedniej kolejności zadań tak, aby jak najszybciej osiągnąć wymaganą sumę nagród za zadania.

Z problem tym można się zetknąć, np.: w różnego rodzaju grach komputerowych. Aby bardziej przybliżyć to zagadnienie, sformułowano je nieco inaczej-w sposób „fabularny":

Które questy (poi. zadania) najlepiej wykonać i w jakiej kolejności tak, aby jak najszybciej zdobyć ilość doświadczenia (eng. exp - experience) (nagrody za zadania) pozwalającą na osiągnięcie kolejnego poziomu doświadczenia (eng. Ievel).

Założenia:

•    Każde zadanie może wymagać wykonania innego, dowolnego zadania przed nim.

•    Każde zadanie ma określony czas trwania.

•    Każde zadanie jest zlokalizowane w przestrzeni dwuwymiarowej, a koszt przejścia pomiędzy nimi jest zależny od odległości.

3.2    MODEL PROBLEMU I REALIZACJA

Aby zamodelować problem konieczne było podzielenie go na pomniejsze ograniczenia, a następnie zamodelowanie każdego z nich.

3.2.1 Wykonanie poprzedniego zadania

Każde zadanie otrzymało swoją zmienną isDone oznaczającą to, czy jest ono wykonywane czy też nie. Przyjmuje ona wartości 1, jeżeli zadanie jest wykonywane oraz 0 jeżeli nie. Zatem, zależność wymuszająca wykonanie wymaganego zadania:

3.2.2 Czas zakończenia poprzedniego zadania

Wymagane zadanie powinno zostać wykonane przed zadaniem, które go wymaga - czyli czas rozpoczęcia i czas trwania wymaganego zadania po zsumowaniu, powinny być mniejsze lub równe czasowi rozpoczęcia zadania, które go wymaga.

■^>rimitiveConstraint cl = new XeqC(quest.getlsDone(),1);

■^>rimitiveConstraint c2 = new

;plusYlteqZ(previousQuest.getBeginTime(),previousQuest.getDuration(),quest.getB :ginTime());

storę.imposejnew IfThen(cl,c2));_

3.2.3 Minimalizowany wskaźnik

Ponieważ czas zakończenia ostatniego zadania powinien być jak najmniejszy, tworzony jest wskaźnik jakości, definiowany jako maksymalna wartość z czasów zakończeń zadań, których isDone = 1.