414223738

62 Sławomir Herma

Sposób przeprowadzenia procedury eliminacji stanów nieperspektywicznych według reguły sondow ania przedstawia się następująco:

1.	peJ, r J, P^eJl -* T’-^h	Dla dwóch dowolnych stanów na tym samym etapie „e” należy wyznaczyć chwile zakończenia trwania ostatniej przyporządkowanej operacji.
2.	Ti= Z ». T>= Z 9. wn<ł£f'^h	Wyznaczyć sumaryczny czas dla wszystkich dotąd nie przydzielonych operacji dla obydwu badanych stanów.
3.	t^NJi = r^A + tx J'^N Ji _ jeJi _j_ J	Wyznaczyć chwile zakończenia wykonywania operacji na etapie końcowym „vV”.
4.		Wyznaczyć wartości stanów końcowych P^NJ> dM,i2 oraz r
5.	(V^XA <V^NJl'j =>F^Jl(V^NJ‘ >V^NJ‘)	Porównać wartości obu stanów. Ten z nich, który ma większą wartość jest nieperspektywiczny i należy go odrzucić ze ścieżki generacyjnej stanów.

Eliminacja stanów wg reguły dominacji polega na odrzuceniu ze ścieżki generacyjnej jednego z dwóch stanów P^e’' lub P^e’² znajdujących się na tym samym etapie „e” dla których zbiory przyporządkowanych elementów są sobie równe lecz chwile zakończenia obsługi ostatniego elementu są różne. Wówczas stan dla którego V'¹ jest większy jest stanem zdominowanym - zatem nieperspektywicznym.

= cf^Ą)/\(r^Ą <r^A )]=>(/>*•'■ t/>'■'•)

Obydwie powyższe reguły eliminacji są łatwe do implementacji informatycznej i można je stosować na każdym etapie poszukiwania harmonogramu optymalnego. Ich skuteczność okazuje się na tyle duża, że znalezienie rozwiązania dokonywane jest w akceptowalnym czasie. Korzyść ta ma bezpośrednie znaczenie w sytuacji gdy algorytm byłby uruchomiony w środowisku symulacji cyfrowej fabryki.

9. Implementacja informatyczna algorytmu

Przedstawiony w poprzednich rozdziałach model matematyczny został opracowany w postaci programu komputerowego, którego nadrzędnym celem była praktyczna weryfikacja użyteczności zastosowanych struktur danych oraz skuteczności zaprojektowanego algorytmu.