b) fiecare set de noduri intermediare de-a lungul secțiunilor ne-alungite ale căii cu lungimea zero definește o operație. Astfel de exemple vor fi;
c) fiecare arc intermediar cu o lungime a unității determină schimbarea mașinii. În consecință, lungimea căii fără unitate este egală cu numărul de operațiuni.
Din aceste proprietăți urmează reductibilitatea, deoarece prin calea cea mai scurtă de la sursă la rularea pe digraph construit ponderat există fără îndoială o împărțire a secvenței de tranziții în numărul minim de operații [22].
În Fig. 2.14 arcurile orizontale sunt încărcate cu zero, celelalte - una; arcele grase denotă calea cea mai scurtă corespunzătoare soluției (b) din Fig. 2.13; lungimea căii fără unitate este egală cu numărul de operațiuni, adică cu trei operații:
· Operațiunea include tranziții și este efectuată pe mașină;
· Operațiunea include o tranziție și este efectuată pe mașină;
· Operațiunea include tranziții și este efectuată pe mașină.
Fig. 2.14 Un exemplu de formare a operațiunilor tehnologice ca o căutare a celei mai scurte căi pe digraf
2.2.7 Echilibrarea traseului
Următoarea sarcină de producție, reducătoare la sarcina de a găsi o cale pe un grafic, are loc atunci când se aleg căile tehnologice pentru prelucrarea pieselor într-un sistem flexibil de fabricație (FMS).
Permiteți unui lot de piese identice să ajungă la intrarea unei anumite unități GPS pentru fabricarea produselor dintr-o singură nomenclatură. Se stabilește secvența operațiilor tehnologice stabilite pentru această nomenclatură. Pentru fiecare operație se determină alocările admise mașinilor FMS și timpul de execuție a acestora de către fiecare mașină adecvată. Timpul operației poate depinde de mașina care o execută. Se cunoaște transportul pieselor de la o mașină la alta. Prin urmare, este necesar să se atribuie operațiuni mașinilor, astfel încât calea tehnologică rezultată pentru trecerea mașinilor să fie echilibrată (adică timpul de procesare și de transport al pieselor pe toate secțiunile traseului este, dacă este posibil, aliniat). Echilibrarea rutei tehnologice conduce la încărcarea cea mai uniformă a echipamentului GPS [22].
Fie - o secvență de operații, și - mașini FMS. Construim un digraph cu vârfuri s, t și vârfuri pentru fiecare operație și fiecare mașină care o poate executa. Vârfurile sunt conectate prin arce pentru toate seturile admisibile de valori i, j, k.
Toate arcurile speciei vor fi încărcate cu timpul de funcționare a mașinii, toate arcurile speciei, - timpul de transport din mașină; la mașină, iar toate arcurile formei sunt zero.
Fig. 2.15 Exemplu de sarcini admise ale mașinilor
Să luăm în considerare un exemplu de construcție a unui digraph pentru n = 4, m = 5. Alocările admise ale operațiilor pe mașini sunt determinate de marginile graficului bipartit din Fig. 2.15, în timp ce timpul de efectuare a operațiunilor de către utilaje adecvate și timpul de transport sunt prezentate în tabelele 2.9 și 2.10. Celulele care corespund asignărilor inacceptabile ale operațiunii la mașini nu sunt ocupate. În Fig. 2.16 arată digraphul corespunzător.
O traiectorie arbitrară a digraphului construit de la s la t trece prin noduri intermediare și are următoarele proprietăți:
a) determină opțiunea de a permite asignarea operațiilor la mașini, deoarece - acestea sunt numerele mașinilor care trebuie să efectueze operații. Și nu există nici o singură variantă a alocării admisibile a operațiilor, pe care o anumită cale de la s la t nu s-ar potrivi.
b) traseul corespunzător traseului trece succesiv mașina. Cel mai lung arc al căii determină cel mai lung proces pe traseu. Dacă se găsește un astfel de arc, atunci cel mai lung proces va fi o operație, dacă aceasta este transportul de la mașină la mașină
Un traseu echilibrat este pus în corespondență cu calea de la s până la t cu cel mai scurt arc lung. Astfel, timpul celui mai lung proces pe traseu va fi făcut cât mai mic posibil și apropiat de timpul celuilalt. Această interpretare a criteriului de echilibrare în final reduce problema inițială la problema CALEA DE SILENȚĂ [22].
Trimiteți-le prietenilor: