Sprawdzanie warunków pierwszeństwa - algorytm.

Witam,
jestem umiarkowanym laikiem jeśli chodzi o programowanie, ale muszę napisać program balansujący linię montażową. Aktualnie borykam się z problemem sprawdzania warunków pierwszeństwa. Oto przykładowy diagram pierwszeństwa:

![user image](http://i.imgur.com/fKEok.png)

Zrobiłem macierz/tabelę, w której, dla każdego z 25 zadań ( Ti ), wypisana jest lista zadań, które nie mogą być bez jego ukończenia wykonane ( P(Ti,:) ). Wygląda to tak:

P = [ 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 ;             
    10 16 17 18 19 20 21 22 23 24 25 0 0 0 0 0 0 0 0 0 0 0 0 0  ;
    4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 0;
    8 12 15 23 24 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
    8 9 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0 0 0 0 0 0 0;
    11 10 13 15 16 17 18 19 20 21 22 23 24 25 0 0 0 0 0 0 0 0 0 0;
    20 24 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
    12 15 23 24 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
    12 14 15 19 23 24 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
    16 17 18 19 20 21 22 23 24 25  0 0 0 0 0 0 0 0 0 0 0 0 0 0;
    13 15 16 17 18 19 20 21 22 23 24 25  0 0 0 0 0 0 0 0 0 0 0 0;
    15 23 24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0;
    15 16 17 18 19 20 21 22 23 24 25  0 0 0 0 0 0 0 0 0 0 0 0 0;
    19 23 24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0;
    23 24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0;
    17 18 19 20 21 22 23 24 25  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
    21 22 23 24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0;
    19 20 23 24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0;
    23 24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0;
    24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0;
    22 23 24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0;
    24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0;
    24 25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0;
    25  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0];

Mam też tablicę, w której dla poszczególnych stacji roboczych ( W(Ti,:) ) wypisane są zadania należące w danej chwili do danej stacji (ograniczenie do pięciu miejsc jest tylko na czas testów). Aktualne rozwiązanie wzięło się z podanego w przykładzie 'initial solution', doprowadzeniem do którego zajmę się w późniejszej fazie projektu.

W = [ 1 3 0 0 0 ; 
	5 0 0 0 0 ; 
	6 7  0 0 0 ; 
	11  0 0 0 0 ; 
	13  0 0 0 0 ; 
	2  0 0 0 0 ; 
	4 10 16  0 0 ; 
	8 9 14 0 0 ; 
	18  0 0 0 0 ; 
	12 19 0 0 0 ; 
	17 21 0 0 0 ; 
	15  0 0 0 0 ; 
	23 0 0 0 0 ; 
	20  0 0 0 0 ; 
	22 24 0 0 0 ; 
	25  0 0 0 0 ]; 

Program ma za zadanie wymieniać ze sobą zadania T1 i T2 (wybrane poprzez kontrolowane losowanie) w różnych stacjach roboczych, aż nie trafi na lepsze rozwiązanie. Oczywiście wymienić zadania może tylko wtedy, gdy spełnią one kilka warunków. Jednym z nich jest właśnie reguła pierwszeństwa i to ona sprawiła mi do tej pory największy problem.

PROBLEM:

Zrobiłem sprawdzanie w następujący sposób: program sprawdza czy dwa wybrane do wymiany zadania T1 i T2 nie mają siebie nawzajem w liście pierwszeństwa. Niestety wyniki nie są dobre i program zawsze wymienia zadania w taki sposób, że prawa pierwszeństwa nie są zachowane. Moje sprawdzanie nie wystarczy, ale nie mam pomysłu w jaki sposób do tego problemu podejść, dlatego proszę o pomoc na tym forum. Na co muszę zwrócić uwagę i jak ugryźć ten problem? Jeśli ktoś jest mi w stanie pomóc, będę wdzięczny.

Pozdrawiam serdecznie,
J.A.

ps. proszę się nie przejmować składnią bo piszę w matlabie, zależy mi na pomocy w wymyśleniu/napisaniu algorytmu sprawdzania precendesów.

Jeśli dobrze Cię zrozumiałem to po prostu musisz zastosować tu sortowanie grafu. Kolejność po posortowaniu da Ci odpowiedź w jakiej kolejności należy wykonać kolejne operacje....

Gregory_Scot napisał(a)

Jeśli dobrze Cię zrozumiałem to po prostu musisz zastosować tu sortowanie grafu. Kolejność po posortowaniu da Ci odpowiedź w jakiej kolejności należy wykonać kolejne operacje....

Nie wiem, czy dobrze Cię rozumiem, ale ja mam posortowane poszczególne zadania do odpowiednich stacji. Jednak, jako że można to zrobić na wiele sposobów, teraz muszę to zoptymalizować.

Mój problem polega na tym, że nie wiem jak sprawdzić czy dane zadanie można zamienić miejscem z innym (w ówcześnie posortowanej kolejności), żeby zachować konieczną kolejność zadań.

@johnalabama to o czym pisał @Gregory_Scot to jest tzw sortowanie topologiczne skierowanego grafu acyklicznego.

Shalom napisał(a)

@johnalabama to o czym pisał @Gregory_Scot to jest tzw sortowanie topologiczne skierowanego grafu acyklicznego.

Tak myślałem po przeczytaniu wikipedii. Niestety to nie rozwiązuje mojego problemu.
dzięki!

Witam, poradziłem sobie z problemem.

Pozdrawiam wszystkich!
J.A.

Warto napisać jak sobie poradziłeś, bo ktoś moze miec podobny problem ;)

Jasne, mam nadzieję, że kod powie sam za siebie ;) Albo nie. Zaczynam od danego na wejściu taska T1 i sprawdzam kaj jest w macierzy W (taski ustawione w stacjach roboczych) wcześniej przekształcając tę macierz do pojedynczego wektora. Następnie biorę do innego wektorka wszystkie taski, które następują po T1 i sprawdzam, czy zawierają się w nich taski z P(T1,:). Haczyk polega na tym, że tak naprawdę najpierw zamieniam miejscami taski, a potem sprawdzam czy jest ok, jeśli nie, to zamieniam z powrotem ;)

function y=checkP(T1,W,P)

y=1;
i=1;
W2=nonzeros(W')';

while W2(i)~=T1
    
    i=i+1;
    
end



lW2 = length(W2);

for o = i:lW2
    
    nW(o-i+1)=W2(o);
    
end


nP = nonzeros(P(T1,:))';


tf = ismember (nP,nW);



if length(nonzeros(tf)) == length(nP);
    
    y=0;
    
end

pozdrawiam,
j.a.