Zautomatyzowane Systemy Wytwórcze PDF

Zautomatyzowane Zautomatyzowane Systemy Systemy Wytwórcze Wytwórcze Podstawowe Podstawowe pojęcia pojęcia ii koncepcje koncepcje Piotr PiotrSkrzypczyński Skrzypczyński 1. Wstę...

Zautomatyzowane Zautomatyzowane Systemy Systemy Wytwórcze Wytwórcze Podstawowe Podstawowe pojęcia pojęcia ii koncepcje koncepcje Piotr PiotrSkrzypczyński Skrzypczyński 1. Wstęp Automatyzacja procesów produkcyjnych ma na celu zwiększenie efektywności przedsiębiorstwa w wyniku lepszego wykorzystania zasobów ludzkich i środków techniki. Realizacja tego celu jest uwarunkowana wdrożeniem nowych technik i technologii oraz nowych metod organizacji wytwarzania gwarantujących odpowiednio wysoki poziom elastyczności , efektywności i niezawodności działania systemów produkcyjnych. Podstawę każdej produkcji stanowi proces technologiczny określający wzajemne relacje między przetwarzanym surowcem a srodkami produkcji, tzn. proces podczas którego materiał zmienia swoje kształty, wymiary, własności fizykochemiczne lub tez wzajemne położenie. Działania występujące podczas wytwarzania wyrobu finalnego, uwzględniające prace maszyn i ludzi, określa się mianem procesu wytwarzania. Proces wytwarzania obejmuje proces technologiczny, transport, kontrolę i magazynowanie. Podczas realizacji procesu technologicznego, przetwarzającego surowce w wyroby gotowe, występuje wzajemne oddziaływanie na siebie strumieni materiałów, informacji i energii. Zorganizowany zespół działań koordynujących przebieg tych strumieni składa się na proces produkcyjny. Wymagania stawiane przedsiębiorstwom są uwarunkowane postępująca globalizacją oraz wzrostem wymagań rynkowych. Podstawowymi kryteriami konkurencyjności przedsiębiorstw są: jakość, elastyczność, niska cena, czas realizacji dostaw oraz niezawodność. W przemyśle elektro-maszynowym udział produkcji mało isrednio seryjnej wynosi ok.. 70%. W USA znaczna część produkcji w przemysle maszynowym wytwarzana jest w seriach o liczebności poniżej 50 sztuk. Rys. 1. Uwarunkowania konkurencyjności przedsiębiorstw W zależności od charakteru materialnych potoków dominujących w danej produkcji wyróżnia się systemy o: produkcji ciągłej produkcji dyskretnej Produkcja ciągła oparta jest na ciągłych procesach technologicznych, które wystepują w energetyce oraz przemyśle chemicznym, natomiast produkcja dyskretna oparta jest o dyskretne procesy technologiczne. Są one typowe dla przemysłu elektro- maszynowego (samochodowego, wyrobów gospodarstwa domowego itp.). Procesy ciągłe, związane z przetwarzaniem jednorodnych lub zbliżonych do jednorodnych strumieni materiałów: cieczy, gazów, materiałów sypkich lub ich mieszanin, są w wysokim stopniu zautomatyzowane. Dyskretne procesy produkcyjne przetwarzające strumienie materiałów niejednorodnych, związane z obróbka wiórową, plastyczną, spawaniem i montażem, są mało zautomatyzowane. W zależności od wielkości i charakteru realizowanej produkcji dyskretnej, wyróżnia się jej pięć podstawowych typów: jednostkową małoseryjną średnioseryjną wielkoseryjną masową Typ produkcji określa się za pomoca wskaźnika liczby detalooperacji przypadających na przeciętne stanowisko: Wartości powyższego wskaźnika określają produkcję: jednostkową k≤1 małoseryjną 1 > k ≤ 10 średnioseryjną 10 > k ≤ 20 wielkoseryjną 20 > k ≤ 30 masową k > 30 W produkcji masowej i wielkoseryjnej znajduje zastosowanie automatyzacja sztywna. Stosuje się linie produkcyjne zestawione z urządzeń działających automatycznie, przeznaczonych do produkcji określonego wyrobu. Sztywna automatyzacja pracy linii produkcyjnych, zapewniająca realizacje stałego, cyklicznego programu pracy urządzeń, osiągana jest często za pomocą środków mechanicznych, takich jak: zderzaki, krzywki, wzorniki. W krajach wysoko uprzemysłowionych produkcja masowa stanowi około 15% calej produkcji wytwarzanej w dyskretnych systemach produkcyjnych. Osiągany stopień automatyzacji linii produkcyjnych pozwala uzyskiwać wydajność produkcji porównywalna z wydajnością kompleksowo zautomatyzowanych systemów produkcji ciągłej. Pozostała produkcja wytwarzana jest w trybie produkcji średnioseryjnej, małoseryjnej i jednostkowej. Niemasowy charakter produkcji wymuszany jest zapotrzebowaniem rynku na produkty różniące się parametrami użytkowymi, jakością wykonania i cena. Automatyzacja produkcji małoseryjnej i jednostkowej może być efektywnie realizowana przez zastosowanie koncepcji automatyzacji elastycznej (programowalnej). Umożliwia ona osiągnięcie ciągłości, rytmiczności i wydajności produkcji porównywalnej z tą, jaka jest uzyskiwana w liniach automatycznych. Urządzenia programowalne są zdolne do wytwarzania szerokiej grupy wyrobów, przy czym przejście z produkcji jednego typu wyrobu do produkcji innego nie wymaga fizycznej rekonfiguracji urządzeń, a tylko zmiany ich programu działania. Celem automatyzacji programowalnej jest ograniczenie strat spowodowanych spadkiem wydajności produkcji oraz zmniejszeniem stopnia wykorzystaniem maszyn. Przyczyna tych strat są przestoje maszyn i urządzeń wytwórczych, spowodowane koniecznością dokonywania przezbrojeń systemu produkcyjnego. Przesłanki określające możliwości rozwoju systemów automatyzacji elastycznej wiążą się z: pełnym wykorzystaniem rezerw tkwiących w organizacji pomocniczych procesów produkcyjnych (transport, magazynowanie, kontrola jakości); pełnym wykorzystaniem funduszu czasu urządzeń produkcyjnych oraz skróceniem oczekiwania detali na obróbkę; zmniejszeniem kosztów przez zmniejszenie pracochłonności produkcji wykorzystaniem rezerw sprawności organizacji technicznego przygotowania produkcji rozwojem nowych technologii wytwarzania Rys. 2. Ewolucja koncepcji wytwarzania Obserwowany ewolucyjny postęp w zakresie budowy programowalnych urządzeń wytwórczych oraz środków i technik informatyki pozwala przewidzieć dalsze perspektywy rozwoju systemów elastycznej automatyzacji wytwarzania. Ilustracje obecnych i przewidywanych etapów rozwoju przestawiono na Rys. 3. Rys. 3. Zautomatyzowane formy wytwarzania - ewolucja 2. Zarządzanie produkcja Zarządzanie produkcją (inżynieria zarządzania) obejmuje zagadnienia należące do trzech obszarów: 1. Działania poprzedzające proces wytwarzania: projektowanie wyrobu; projektowanie systemu produkcyjnego; 2. Organizację procesu wytwarzania: formowanie przebiegu procesów produkcyjnych; planowanie przebiegu procesów wytwarzania; sterowanie przebiegiem procesów wytwarzania; 3. Organizację procesów pomocniczych (niezbędnych do funkcjonowania procesu wytwarzania) – procesy logistyczne. Do zarządzania produkcja zalicza się następujące zagadnienia: opracowanie i realizację programu produkcji dostosowanego do potrzeb rynku zapewniającego efektywne wytworzenie; określenie zapotrzebowania i efektywnego wykorzystania niezbędnych do tego celu zasobów; stworzenie racjonalnych przebiegów procesów przy uwzględnieniu aspektów przestrzennych, czasowych oraz organizacyjnych Nowoczesny system wytwarzania zatem jest zbiorem stanowisk lub modułów wytwórczych, powiązanych ze sobą relacjami wynikającymi z procesu wytwarzania, które mogą mieć różny charakter: konfiguracyjny, wynikający z rozmieszczenia stanowisk lub modułów wytwórczych, technologiczny, wynikający z faz procesu wytwarzania, operacji, zabiegów, administracyjny, wynikający z administracyjnej obsługi i zarządzania wytwarzaniem, funkcjonalny, wynikający ze sterowania procesem wytwarzania. Proces wytwarzania składa się z: procesu podstawowego, w którym dzięki informacji, kwalifikowanej pracy ludzkiej, funkcjonowaniu maszyn i wykorzystywanej energii następuje przetwarzani materiałów w wyroby, procesu pomocniczego, który polega na: dostarczaniu do elementów systemu wytwarzania materiałów, energii, informacji oraz zapewnieniu prawidłowego funkcjonowania procesu obsługowego, który obejmuje miedzy innymi obsługę administracyjną i zarządzanie wytwarzaniem, zapewnienie bezpieczeństwa pracy, ochronę obiektów wytwórczych, utrzymanie czystości, usługi socjalne w miejscu pracy. Procesowe ujęcie systemu wytwarzania stwarza możliwości zastosowania zarządzania procesowego w strukturach wytwarzania. Jest to argumentowane potrzebą łączenia ze sobą wszystkich działań w celu osiągnięcia efektu synergicznego Prowadzi do przełamania organizacyjnej sztywności, gdzie pojedyncze funkcje lub jednostki często są od siebie odizolowane i spełniają wykluczające się nawzajem funkcje. Podejście procesowe jest zorientowane na zwiększenie efektywności procesów kosztem zmniejszenia funkcjonalnej skuteczności. Takie działania są osiągane poprzez harmonizację i integrację poszczególnych procesów, podprocesów, z odpowiedzialnością funkcjonalną skoordynowaną przez logikę procesu. Pozwala to na tworzenie dynamicznych logicznych struktur wytwarzania, które mogą dostosowywać się do zmian w otoczeniu. Orientacja na procesy polega na wyłonieniu dla każdej grupy wyrobów realizowanych w systemie tzw. Zintegrowanego procesu wytwarzania. Zintegrowany proces to strumień przeplatających się działań: przygotowawczych, obsługowych, transportowo-magazynowych i sterujących wokół procesu podstawowego. Zadanie – realizacja zlecenia produkcyjnego, określone jest głównie przez następujące parametry: czas (termin realizacji), koszt, będące do dyspozycji zdolności produkcyjne. Decyzje podejmowane są na etapie: Planowania - zachowanie zgodności z oczekiwaniami klientów. Sterowania - pogodzenie parametrów określających zadania, aby rozwiązać problem konkurencyjnego dostępu do ograniczonych zasobów produkcyjnych. Systemy planowania i sterowania produkcja współdziałają z innymi systemami informatycznymi przedsiębiorstwa, takimi jak: Computer Aided Design (CAD) komputerowo wspomagane projektowanie Computer Aided Planning (CAP) komputerowo wspomagane planowanie Computer Aided Manufacturing (CAM) komputerowo wspomagane wytwarzanie Computer Aided Quality Control (CAQ) komputerowo wspomagana kontrola jakości Razem podsystemy te tworzą system CIM (Computer Integrated Manufacturing) komputerowo zintegrowane wytwarzanie Można wyróżnić następujące strategie sterowania produkcją: Istniejące zdolności produkcyjne i termin dostawy są nieprzekraczalne. Krótkoterminowe wykorzystanie obcych zdolności produkcyjnych lub zwiększenie własnej wydajności prowadzi do zwiększenia kosztów. Typ produkcji jednostkowej lub maloseryjnej realizowanej przy wykorzystaniu pojedynczych maszyn w konwencjonalnych systemach wytwarzania oraz w pełni zautomatyzowanych, elastycznych systemach wytwarzania FMS (Flexible Manufacturing System). Maksymalizacja obciążenia zdolności produkcyjnych może ograniczać swobodę decyzji w zakresie obciążenia zdolności produkcyjnych dla innych zleceń. Koszty i zdolności produkcyjne traktowane są jako stałe.Jedynym możliwym krokiem są przesunięcia terminów, które mogą dotyczyć wielu zleceń. Produkcja masowa. Zbyt dostosowuje się do zasad określonych przez spływ produkcji zakończonej. Ewentualne wahania zapotrzebowania wyrównywane są przez zapasy magazynowe. Termin i koszt traktowane są jako stałe. Istnieje możliwość krótkoterminowego uruchomienia będących do dyspozycji rezerw zdolności produkcyjnych, które nie mogą zwiększać kosztów produkcji. Zwiększenie potencjału dostępnych zdolności produkcyjnych odpowiednio do aktualnych potrzeb bez zwiększania kosztów stałych. Źródła rezerw: - zapasy - organizacja przepływu produkcji oraz w struktura produkcyjna. Zaopatrzenie przedsiębiorstwa w materiały do produkcji kształtowane jest w ścisłej współpracy odbiorca - dostawca. Dzięki temu możliwe jest zminimalizowanie ewentualnych strat (zapasów) i właściwe reagowanie na dynamiczn epotrzeby rynku. Każde uruchomienie produkcji u dostawcy–dokonywane z odpowiednim wyprzedzeniem–następuje po otrzymaniu przez niego polecenia od bezpośredniego odbiorcy jego wyrobów (system typu pull–ssący). Tak,więc każdy produkt, bez względu na miejsce jego powstawania, wykonywany jest w odpowiedzi na konkretną, występującą wdanej chwili potrzebę (w odróżnieniu od systemu typup ush–tłoczący, w których producent najpierw wytwarza swój wyrób, a następnie poszukuje dla niego potencjalnych nabywców). Metoda planowania i kontroli produkcji Just In Time (JIT) oparta na określonej filozofii działania, której celem jest wyeliminowanie z procesu produkcyjnego wszelkich strat przez produkowanie właściwych wyrobów, w żądanej ilości i terminie oraz dostarczenia ich do miejsc, gdzie są potrzebne dokładnie wtedy gdy potrzeby występują. Nie akumuluje lub minimalizuje zapasy produkcji w toku poprzez dostarczanie produktów „na żądanie” i „dokładnie na czas”: Produkt powinien być zaprojektowany z uwzględnieniem modularności, łatwości wytwarzania i eliminowania zbędnej złożoności. Zastosowanie produkcji potokowej (odejście od produkcji dużymi partiami). Synchronizacja procesów produkcyjnych w warunkach równomiernego obciążenia, przy pewnym poziomie niedociążenia, umożliwiającego natychmiastową reakcję n wszelkie nieprawidłowości przez zatrzymanie całej linii produkcyjnej.  Eliminowanie wszelkich strat powstających w produkcyjnym. Do strat zalicza się: - produkcję nadmiernej liczby wyrobów w stosunku do zapotrzebowania, - produkcję części na zapas (nie wiadomo czy i kiedy zostaną wykorzystane w dalszym procesie produkcyjnym, a na razie stanowią zamrożony kapitał), - zbędny transport, - oczekiwanie (na materiał, na narzędzia, na zakończenie wykonywania poprzedniej operacji), a także bezczynność pracownika w okresie, gdy wyrób jest obrabiany na stanowisku bez jego bezpośredniego udziału, - braki (strata nie tylko materiału, energii, pracy człowieka i maszyny, ale także straty wynikłe z kosztów napraw, z obsługi serwisowej, itp.) - zapasy zabezpieczające (jako zamrożony kapitał) zbędne procesy oraz bezużyteczne działanie robotnika. 5. Zastosowanie manipulatorów, umożliwiających automatyzację operacji produkcyjnych. 6. Precyzyjna kontrola jakości na każdym stanowisku pracy. 7. Sprawny i niezawodny system transportowy. 8. Stabilność dostaw - dostawcy materiałów i kooperanci muszą gwarantować wysoką jakość i terminowość dostaw. 9. Redukowanie wielkości partii produkcyjnej. Zredukowana partia produkcyjna umożliwia osiągnięcie potokowej formy organizacji produkcji, co prowadzi do minimalizacji zapasów produkcji w toku. Jednocześnie należy dążyć do redukcji zapasów zabezpieczających przez przewidywanie przyczyn powstawania przestojów, które są kompensowane tymi zapasami. 3. Komputerowo zintegrowane wytwarzanie Komputerowo Zintegrowane Wytwarzanie (Computer Integrated Manufacturing - CIM) obejmuje wszystkie aspekty wytwarzania wspomaganego przez komputer, systemy wspomagania logistyki i technologii produkcji. Komputerowo zintegrowane wytwarzanie charakteryzuje się m.in.: procesowym zintegrowaniem narzędzi CAx (CAD, CAM, CAPP itp..) opartych na modelach i bazie przedsiębiorstwa; możliwością elastycznego reagowania na potrzeby rynku, wprowadzaniem zmian oraz programem modernizacji produktów i procesów wytwórczych; koniecznością wykorzystania rozbudowanej infrastruktury technicznej przedsiębiorstwa. Komputerowe wspomaganie wytwarzania, CAM (ang. Computer Aided Manufacturing) ma za zadanie integrację fazy projektowania i wytwarzania. Cechą charakterystyczną systemu jest transformacja (przetwarzanie) obiektów (modeli powstałych w wyniku modelowania komputerowego 2D/3D; modeler może, ale nie musi być częścią składową programu CAM) na instrukcje maszynowe (dokładnie: na instrukcje sterujące pozycją narzędzia obróbczego; maszyny sterowane numerycznie NC i CNC), które umożliwiają wytwarzanie detali. Rys. 4. Przepływ informacji w systemie CIM Rys. 5. Planowanie procesów technologicznych w systemie CIM 4. Elastyczne systemy produkcyjne Dzięki szybkiemu postępowi technicznemu powstają nowe możliwości kompleksowej automatyzacji procesów produkcyjnych, obejmujących cały obszar produkcji - począwszy od projektowania wyrobu przez programowanie procesu technologicznego, obróbkę i montaż, gotowego wyrobu odbiorcy. Wdrażanie elastycznych systemów produkcyjnych, opartych na zastosowaniu nowoczesnych, sterowanych numerycznie urządzeń, komputerów, robotów, systemów wspomagających prace projektowo- konstrukcyjne, jest naczelną zasadą przedsięwzięć, mających na celu unowocześnienie technologicznej bazy w przedsiębiorstwie, a przede wszystkim usprawnienie organizacji produkcji. Pojęcie elastyczności kojarzy się z łatwością adaptacji procesów lub systemów gospodarczych do pożądanych warunków lub zmian, zachodzących w otoczeniu. Jednak elastyczność jest pojęciem bardziej złożonym i nie może być odnoszona jedynie do urządzeń lub form realizacji procesów technologicznych. Elastyczność jest więc przede wszystkim cechą systemów gospodarczych, decydującą o możliwościach ich adaptacji do zmieniających się wymogów funkcjonowania otoczenia. Obok produktywności oraz jakości i niezawodności, elastyczność jest główną składową konkurencyjności systemów gospodarczych. Rozwój elastycznych systemów produkcyjnych i rozwiązań pochodnych (elastyczne systemy montażowe, elastyczne systemy selekcji i kompletacji, automatyczne magazyny) rozpoczął się w latach 80. ubiegłego wieku. Przyczyną zainteresowania tą wysoko zaawansowaną technicznie i wymagającą wtedy dużych nakładów na etapie inwestycji formą jednostki produkcyjnej była odczuwana przez przemysł przodujących w skali światowej krajów presja kosztów, powiązana z różnicowaniem się potrzeb klientów. Różnicujące się zapotrzebowania klientów prowadziły do dużych i szybko następujących zmian w asortymencie montowanych wyrobów, wytwarzanych części czy kompletowanych wysyłek. W tradycyjnie zorganizowanych jednostkach produkcyjnych prowadziło to do konieczności odchodzenia od wytwarzania w partiach ekonomicznych częstszych, niż przewidywały to harmonogramy przezbrojeń, spadku efektywnego obciążenia (wzrost udziału czasu przygotowawczo - zakończeniowego tpz). Wszystko to prowadziło do wzrostu kosztów wytwarzania. Częste przezbrojenia powodowały też wzrost kosztów robocizny, wynikający z konieczności wzrostu kwalifikacji bezpośredniej obsługi maszyn i urządzeń (a co za tym idzie - wzrostu wynagrodzeń) oraz kosztów szkolenia pracowników. W odpowiedzi na narastające problemy przemysł zaczął poszukiwania obniżki kosztów wytwarzania, zwiększenia możliwości produkcyjnych oraz zwiększenia konkurencyjności. Warunkiem utrzymania się przedsiębiorstwa na rynku jest zdolność szybkiego reagowania na nowe potrzeby, czyli skracanie cykli wdrażania nowych wyrobów oraz szybkie uruchamianie i realizowanie zleceń produkcyjnych przy jednoczesnym zapewnieniu odpowiedniej jakości wyrobów i zachowaniu niskiej ceny. Nieodzowne staje się zatem tworzenie systemów produkcyjnych, opartych na rozwiązaniach zapewniających wysoką efektywność funkcjonowania przedsiębiorstwa i spełniających jednocześnie wszystkie wymogi związane z oczekiwaniami rynku. Istnieje wiele przesłanek przemawiających za stosowaniem w określonych warunkach ESP, a korzyści związane ze stosowaniem ich są następujące: wzrost stopnia wykorzystania środków trwałych, zmniejszenie kosztów robocizny bezpośredniej, zmniejszenie zapasów robót w toku oraz cykli produkcyjnych, szybkie reagowanie na zmienne zadania produkcyjne, odporność na zakłócenia wewnętrzne, wzrost jakości produkowanych wyrobów, wzrost wydajności, i łatwość rozbudowy systemu. Rys. 6. Widok przykładowego elastycznego systemu produkcyjnego Rys. 7. Przykładowe rozwiązanie elastycznego systemu produkcyjnego Rys. 8. Schemat funkcjonalny przykładowego elastycznego systemu produkcyjnego BIBLIOGRAFIA Z. Banaszak, L. Jampolski, Komputerowo wspomagane modelowanie ESP, WNT, 1991 Z. Banaszak, W. Muszyński, Systemy elastycznej automatyzacji dyskretnych procesów produkcyjnych, Wyd. Politechniki Wrocławskiej, 1991 J. Plichta, S. Plichta, Komputerowo zintegrowane wytwarzanie, Wyd. Politechniki Koszalińskiej, 1999 Zautomatyzowane Zautomatyzowane Systemy Systemy Wytwórcze Wytwórcze Wybrane Wybrane metody metody modelowania modelowania systemów systemów ii procesów procesów produkcyjnych. produkcyjnych. Planowanie Planowanie produkcji. produkcji. Szeregowanie Szeregowanie zadań. zadań. Piotr PiotrSkrzypczyński Skrzypczyński 1. Organizacyjne przygotowanie produkcji Planowanie zaopatrzenia i zapasów materiałowych Zakres planowania zapasów materiałowych obejmuje: bilansowanie potrzeb materiałowych normowanie zapasów i zużycia planowanie i realizację zaopatrzenia sterowanie przepływem materiałów Zadanie sterowania zapasami odnosi się do sytuacji, w której zaopatrzenie nastepuje w stałych odcinkach czasu t, w partiach artykułów po n sztuk. W modelu przyjmuje się, że znany jest horyzont sterowania tp, ogólna liczba sztuk artykułu zamawianego w tym okresie Na oraz liczba partii dostaw r. Przy założeniu, że funkcja określająca sposób zużycia zapasow ma charakter liniowy, koszt magazynowania określony jest jako: Koszty realizacji dostaw opisane są jako: Model zadania sterowania zapasami określa funkcja kosztu calkowitego: Optymalną wielkość partii określa prawo Wilsona: Okres dostaw dany jest jako: Minimum funkcji kosztów określa zależność: 2. Planowanie produkcji Planowanie produkcji jest programem działan dotyczacych głównie podejmowaniu decyzji w zakresie wykorzystywania zasobów produkcyjnych i materiałowych w celu realizacji zleceń produkcyjnych. Podstawowym celem planowania produkcji powinno byc spełnienie wymagan klienta w zwiazku z zamówionymi zleceniami produkcyjnymi: wielkoscia i terminem dostawy. Od strony producenta istotne jest racjonalne wykorzystanie zdolnosci produkcyjnych i minimalizacji zapasów. W efekcie chodzi o to, żeby sprecyzowac moment rozpoczecia i zakonczenia zadan oraz ustaleniu, kiedy i z wykorzystaniem, jakich zasobów produkcyjnych ma ono byc wykonywane. W planowaniu produkcji pojawiaja sie dwa podstawowe pojecia takie jak: planowanie zadań w czasie - harmonogramowanie oraz bilansowanie obciażen, polegajace na koordynacji możliwosci produkcyjnych urzadzeń i pracowników realizujacych produkcje. Proces planowania produkcji jest uzależniony od wielu czynników: struktury wyrobów (wyroby proste lub złożone), realizacji zlecen produkcyjnych przebiegu produkcji (produkcja stacjonarna, w gniazdach, liniach produkcyjnych), ilości zamówień (produkcja jednostkowa, seryjna, masowa). Etap planowania produkcji rozpoczyna przyjeciem zlecen produkcyjnych, dla, których ustala sie, które zasoby i w jakim stopniu beda wykorzystywane do ich wykonywania. Jest to planowanie zlecen produkcyjnych w postaci planu produkcji. W etapie tym planuje sie, które urzadzenia produkcyjne beda wykorzystane do wykonania zadania, jakie i ile srodków transportowych trzeba bedzie użyc, aby zapewnic płynna prace urzadzen, ile miejsca zarezerwowac na złożenie zakupionych materiałów, gdzie złożyc wyroby gotowe, ile osób będzie pracowało przy wykonaniu zadania i ile potrzeba bedzie czasu na wykonanie zadania. Jednostka planowania w tym etapie jest najczesciej okres jednego tygodnia. Kolejnym etapem jest planowanie operacyjne, które jest dokładnym planowaniem czasowym wykonania zadan składajacych sie na zlecenia produkcyjne. W ten sposób jest tworzony harmonogram produkcyjny, bedacy szczegółowym planem obciażen zasobów produkcyjnych. Precyzowany jest czas rozpoczecia i zakonczenia poszczególnych operacji oraz czynnosci zwiazanych z bezposrednim przygotowaniem produkcji (pobranie materiałów i narzedzi, zarezerwowanie miejsca przy maszynie, zarezerwowanie odpowiedniej ilosci palet lub pojemników, itp.). W czasie realizacji procesów wytwórczych według planów operacyjnych, konieczna jest ich kontrola, co do bez zakłóceniowego ich przebiegu. W przypadku wystapienia zakłócenia np. awaria urzadzenia produkcyjnego konieczna jest korekta planów operacyjnych, aby możliwa była dalsza realizacja procesów wytwarzania. Działania te wchodza w zakres sterowania produkcja. Planowanie operacyjne polega przede wszystkim na zbilansowaniu zadan planowanych w postaci zlecen produkcyjnych z możliwosciami produkcyjnymi w oparciu o: okreslone zapotrzebowanie na zdolnosci produkcyjne obliczenie funduszu czasu poszczególnych komórek produkcyjnych, ustalaniu kolejności zadań produkcyjnych ustaleniu potrzeb materiałowych, oprzyrzadowania, narzedzi. Ekonomiczna wielkość partii obróbkowej W przypadku okreslania ekonomicznej wielkosci partii produkcyjnej bierze sie pod uwage: ilosc wyrobów do wykonania, koszty jednostkowe wykonania jednej sztuki, koszty przezbrajania obrabiarki, oprocentowanie wartości zamrożonych środków obrotowych, itp. Ekonomiczna wielkość partii produkcyjnej można obliczyc z wzoru: Koszty obróbki stanowia wielkosc kosztów zwiazanych tylko z wykonaniem operacji technologicznych danego procesu technologicznego dla partii wyrobów. Wielkość partii produkcyjnej powinna być wielokrotnoscią zlecenia produkcyjnego. Ustalenie wielkosci partii obróbkowej jest zagadnieniem, w którym należy uwzglednic wymagania ekonomiczne oraz organizacyjne, które wystepuja w warunkach realnych. Zwiazane jest to także ze specyfika indywidualna systemu wytwarzania. Dlatego przy wyznaczaniu wielkosci partii zachodzi koniecznosc uwzglednienia wielu czynników, które wymagaja odmiennych decyzji, co do zwiekszenia lub zmniejszenia tej wielkosci. Zwiekszenie partii obróbkowej powoduje [Brzezinski]: zmniejszenie nakładów na ustawianie przygotowanie wytwarzania w przeliczeniu na jednostke wyrobu, wykorzystanie w wiekszym stopniu zdolnosci produkcyjnych poprzez zmniejszenie czasu przezbrajania, zwiekszenie wydajnosci, uproszczenie organizacji i zarzadzania produkcja, zwłaszcza planowania operacyjnego, wydłużenie cyklu wytwarzania, zwiększenie zapasów produkcji w toku, powierzchni magazynowych, wzrost zamrożenia środków obrotowych, zmniejszenie elastycznosci procesu wytwarzania Scheduling Operational planning allows us to determine what tasks are to be performed, in which time and with what machine or means of production. The following information is required to develop a load schedule for production sites: program of production: number of pieces in the order, size of machining and transport batches, structure of the technological process: sequence of technological operations, production resources used, operation times, structure of the manufacturing process: technological process, auxiliary operations Scheduling involves: accepting the order of placing production orders on the schedule, placing technological operations on a schedule relative to each other resulting from the technological route of a given production order The order of placing production orders on the schedule is determined on the basis of the priorities. Priorities are set for customers on production orders, but also on criteria for optimizing the production schedule, eg minimum unit cost of the product, minimum order execution time, etc. Typowe sformulowanie zadania harmonogramowania (zagadnienia kolejnościowego) ma nastepujacą postac: w danej komórce produkcyjnej składajacej się z m stanowisk roboczych realizowany jest proces produkcyjny n róznych wyrobow. Poszczegolne wyroby sa przesylane miedzy stanowiskami w tej samej kolejności. Znane sa czasy jednostkowe wykonania poszczegolnych operacji obróbki kazdego wyrobu na poszczegolnych obrabiarkach. Należy wyznaczyc kolejność wykonania wyrobów, dla której sumaryczny czas cyklu produkcyjnego jest minimalny. Zazwyczaj, czasy wykonania operacji obróbkowych przedstawia macierz czasów jednostkowych operacji T=[tij] o wymiarach m x n. Jedną z powszechnie wykorzystywanych technik tworzenia harmonogramów w systemie wytwarzania jest harmonogram Gantta. Harmonogram (diagram) Gantta sporzadzany jest w układzie współrzednych, gdzie os x jest osia czasu, natomiast na osi y usytuowane sa zasoby systemu wytwarzania. Os czasu jest podzielona na jednakowe okresy czasu. W takim układzie istnieje możliwosc przydzielania (przy wykorzystaniu form graficznych) i kontroli wykonywanych zadan (operacji) do danego zasobu. Operacje najczesciej oznaczane sa w postaci prostokatów, których długośc odpowiada czasowi realizacji danego zadania. Diagramy Gantta dla systemu produkcyjnego składającego się z 3 obrabiarek, w którym realizowana jest produkcja 2 różnych wyrobów, obrabianych najpierw na maszynie 1, a następnie na maszynie 2, dla czasów jednostkowych takich jak podane w przykładowej macierzy T przedstawia Rys. 1. Rys. 1. Przykładowe diagramy Gantta dla dwóch różnych harmonogramów Liczba wszystkich możliwych wariantow kolejności wykonania n wyrobow w rozważanym zadaniu wynosi n! (liczba permutacji). Z tego powodu stosowanie diagramu gantta do określenia kolejności metoda przeglądu zupelnego jest nieefektywne. Zadanie kolejnościowe ma charakter NP.-trudny, a do jego rozwiązania uzywa się często metod heurystycznych (o charakterze przybliżonym). Metoda Gupty Do najbardziej znanych metod przybliżonych należy metoda Gupty, w ktorej dla każdego wyrobu (zadania) obliczane sa pewne wskaźniki: Obliczone w ten sposób wskaźniki ustawione w ciągu niemalejącym wyznaczają poszukiwana kolejność wykonywania zadań. Jako przykład zostosowania metody Gupty rozwazony zostanie system zlozony z 4 obrabiarek, w którym wytwarzane sa 4 wyroby, a kryterium optymalności jest czas wykonania wszystkich wyrobów: Czasy jednostkowe operacji dane są macierzą: Wskaźniki wyznaczone metoda Gupty przyjmuja następujace wartości: f1 = 0.1 f2 = 0.33 f3 = -0.2 f4 = 0.33 Możliwe są dwa równoważne rozwiązania, optymalne ze względu na przyjete 3 - 1 - kryterium: 3-1-4-2 3-1-2-4 W obu przypadkach Cmax = 32. BIBLIOGRAFIA Z. Banaszak, W. Muszyński, Systemy elastycznej automatyzacji dyskretnych procesów produkcyjnych, Wyd. Politechniki Wrocławskiej, 1991 K. Żywicki, Planowanie procesów wytwarzania, Politechnika Poznańska, 2005 H. Vollmuth, Controlling od A do Z, PLACET, 2000. Zautomatyzowane Zautomatyzowane Systemy Systemy Wytwórcze Wytwórcze Systemy Systemy masowej masowej obsługi obsługi Piotr PiotrSkrzypczyński Skrzypczyński 1. Systemy masowej obsługi Teoria masowej obsługi, zwana także teorią kolejek, zajmuje się budową modeli matematycznych, które można wykorzystać w racjonalnym zarządzaniu dowolnymi systemami, zwanymi systemami masowej obsługi. Przykładami takich systemów są: sklepy, porty lotnicze, podsystem użytkowania samochodów przedsiębiorstwa transportowe, oraz system wytwarzania złożone z obrabiarek lub innych wydzielonych stanowisk produkcyjnych (gniazd produkcyjnych itp.). Centralnym problemem związanym z praktycznym wykorzystaniem metod teorii masowej obsługi jest problem wyznaczenia optymalnych decyzji dotyczących liczby stanowisk obsługi, intensywności obsługi, czasu obsługi itp. Możemy rozróżnić systemy obsługi o przeliczalnej liczbie stanów (o przeliczalnej pojemności) oraz systemy z możliwością istnienia nieograniczonej kolejki. Względy praktyczne sugerują, iż dla większości rzeczywistych sytuacji kolejek, przydatny jest model z wystarczająco dużą, ale skończoną kolejką. Systemy kolejkowe możemy również podzielić na jedno lub wielokanałowe (w zależności od liczby aparatów obsługi), pojedyncze (zgłoszenia i obsługa pojedyncza) lub grupowe. Podstawowe pojęcia obsługa – czynność pozwalająca zaspokoić określone potrzeby zgłoszenie (zadanie) – obiekt/klient/ oczekujący na obsługę, kolejka – zbiór zgłoszeń oczekujących na obsługę zgodnie z ustalonymi regułami dyscyplina obsługi - zbiór reguł, wg. których zgłoszenia tworzą kolejkę i są obsługiwane Założenia Zakłada się, że zgłoszenia napływają w sposób przypadkowy, nieregularny. Taki proces nazywamy procesem losowym lub stochastycznym. Proces ten określa prawdopodobieństwo tego, że w określonym przedziale czasu pojawia się w układzie określona liczba zgłoszeń. Założenia konkretnego modelu określają typ rozkładu prawdopodobieństwa zmiennych losowych (rozkład deterministyczny – równe odstępy czasu), rozkład wykładniczy, rozkład Erlanga, dowolny rozkład; zależność lub niezależność zmiennych losowych czasu czekania na zgłoszenie i czasu obsługi; skończona lub nieskończona wartość liczby stanowisk obsługi, długości poczekalni; obowiązująca w systemie dyscyplina obsługi. Rozróżnia się systemy masowej obsługi: z oczekiwaniem bez oczekiwania W systemach masowej obsługi z oczekiwaniem zgłoszenie (zadanie) oczekuje w kolejce na obsługę, natomiast w systemie bez oczekiwania, wszystkie stanowiska obsługi są zajęte i zadanie wychodzi z systemu nie obsłużone (strata zadania). Jeżeli średni czas obsługi w systemie jest większy niż średni odstęp czasu miedzy napływającymi zgłoszeniami, to długość kolejki może rosnąć w nieskończoność - system nie jest w stanie równowagi. Gdy system kolejkowy zmierza do stanu równowagi to prawdopodobieństwo tego, iż kolejka ma określoną długość, jest stałe w każdej jednostce czasu. Natomiast gdy system jest niestabilny, to prawdopodobieństwo długiej kolejki rośnie (układ nie może nadrobić czasu w którym był chwilowo niewykorzystany). Model matematyczny funkcjonowania systemu masowej obsługi opiera się na teorii procesów stochastycznych. W modelu tym występują zmienne losowe: czas upływający między wejściem do systemu dwóch kolejnych zgłoszeń czas obsługi jednego zgłoszenia przez stanowisko obsługi liczba stanowisk liczebność miejsc w kolejce zgłoszeń oczekujących na obsługę W zależności od dyscypliny obsługi systemy kolejkowe można podzielić na: FIFO (first in first out), czyli kolejność obsługi według przybycia; SIRO (selection in random order) czyli kolejność obsługi losowa; LIFO (last in first out), czyli ostatnie zgłoszenie jest najpierw obsłużone; z priorytetem dla niektórych zadań; bezwzględny priorytet obsługi zadania oznacza, że zostaje przerwane aktualnie wykonywana obsługa zadania, a na jego miejsce wchodzi zadanie (klient) z priorytetem. Rys. 2. Różne typy modeli kolejkowych System kolejkowy opisany jest 3 lub 4 parametrami z zastosowaniem tak zwanej symboliki Kendalla: 1|2|3|4 napływ zadań | czas obsługi | liczba stanowisk | długość kolejki 1 - typ napływu zadań M = Markowowski (rozkład Poissona) czas przybycia D = Deterministyczny czas przybycia 2 – rozkład czasu obsługi M = Markowowski (wykładniczy) czas obsługi G = Dowolny rozkład czasu obsługi D = Deterministyczny czas obsługi (jednopunktowy) 3 - liczba kanałów (stanowisk) obsługi 4 - dopuszczalna długość kolejki jeżeli kolejka może być nieskończona, to parametr ten bywa pomijana w zapisie Przykład - system M|M|3 : 3 stanowiska obsługi, strumień wejściowy o rozkładzie Poissona, czas obsługi wykładniczy. Parametry wejściowe systemu kolejkowego λ - średnia liczba klientów przypadająca na jednostkę czasu, ma rozkład Poissona µ - średnia liczba klientów obsłużonych w jednostce czasu, ma rozkład wykładniczy n - liczba równoległych kanałów obsługi Można wyznaczyć ρ - parametr intensywności ruchu - stosunek liczby klientów przybywających do liczby klientów obsłużonych w jednostce czasu. Rozpatrywane są tylko sytuacje w których klienci obsługiwani są według kolejności przybywania do punktu świadczącego usługę, zatem wszyscy klienci są traktowani na równi. Typowe charakterystyki systemu wyznaczane z modeli masowej obsługi procent czasu zajętości wszystkich stanowisk obsługi prawdopodobieństwo, że system nie jest pusty średnia liczba klientów oczekujących średnia liczba klientów oczekujących i obsługiwanych średni czas oczekiwania średni czas oczekiwania i obsługi prawdopodobieństwo, że przybywający klient oczekuje prawdopodobieństwo, że w systemie jest n klientów Wzory pozwalające wyznaczyć podstawowe parametry najprostszego systemu masowej obsługi typu M|M|1 (n=1 - jeden kanał obsługi). Wzory te są słuszne jedynie przy założeniu o pracy systemu w stanie ustalonym, gdy µ > λ. Wzory pozwalające wyznaczyć podstawowe parametry systemu masowej obsługi typu M|M|n, posiadającego n równoległych kanałów obsługi i nieskończona kolejkę. Wzory te są słuszne jedynie przy założeniu o pracy systemu w stanie ustalonym, gdy nµ > λ. Modele sieci kolejek Istnieją zamknięte i otwarte modele sieci kolejek. W sieciach zamkniętych stała liczba zadań (np.. wózków transportowych) krąży w sieci, w modelach otwartych zadania mogą napływać z zewnątrz i opuszczać system (model systemu wytwarzania). Ze względu na skomplikowane zależności probabilistyczno-strukturalne modelowanie sieci kolejek jest trudne. Proste się mogą zostać zdekomponowane na odrębne systemy kolejkowe, które mogą być analizowane indywidualnie z użyciem podanych wcześniej wzorów. Rys. 3 przedstawia dekompozycje prostego systemu wytwarzania na odrębne modele masowej obsługi (tzw. model Jacksona). Rys. 3. Elastyczny system produkcyjny (z lewej) i prawdopodobieństwo przepływów (z prawej) Modele sieci kolejek Istnieją zamknięte i otwarte modele sieci kolejek. W sieciach zamkniętych stała liczba zadań (np.. wózków transportowych) krąży w sieci, w modelach otwartych zadania mogą napływać z zewnątrz i opuszczać system (model systemu wytwarzania). Ze względu na skomplikowane zależności probabilistyczno-strukturalne modelowanie sieci kolejek jest trudne. Proste się mogą zostać zdekomponowane na odrębne systemy kolejkowe, które mogą być analizowane indywidualnie z użyciem podanych wcześniej wzorów. Rys. 3 przedstawia dekompozycje prostego systemu wytwarzania na odrębne modele masowej obsługi (tzw. model Jacksona). Rys. 4. Model systemu w postaci otwartej sieci kolejek BIBLIOGRAFIA Z. Banaszak, W. Muszyński, Systemy elastycznej automatyzacji dyskretnych procesów produkcyjnych, Wyd. Politechniki Wrocławskiej, 1991 K. Żywicki, Planowanie procesów wytwarzania, Politechnika Poznańska, 2005 H. Vollmuth, Controlling od A do Z, PLACET, 2000.  Zautomatyzowane Zautomatyzowane Systemy Systemy Wytwórcze Wytwórcze Wybrane Wybrane metody metody optymalizacji optymalizacji dyskretnej dyskretnej Piotr PiotrSkrzypczyński Skrzypczyński 1. Wstęp DEFINICJA: Algorytm to skończony, uporządkowany zbiór jasno zdefiniowanych czynności koniecznych do wykonania pewnej czynności (słowo pochodzi od nazwiska perskiego matematyka żyjącego w IX wieku) DEFINICJA: Graf G jest określany jako para G(V,E) gdzie V jest zbiorem wierzchołków a E zbiorem krawędzi. DEFINICJA: Złożoność obliczeniowa. Praktyczne znaczenie zlożoności obliczeniowej - złożoność obliczeniowa a czas obliczeń dla 106 operacji na sekundę. 2. Grafy Intuicyjnie, graf to zbiór wierzchołków połączonych krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków. Grafy dzielimy na: Skierowane / Nieskierowane Etykietowane / Nieetykietowane Grafem skierowanym (digrafem) nazywamy parę uporządkowaną G=(V, E) gdzie - V to zbiór wierzchołków, - E to zbiór uporządkowanych par wierzchołków ze zbioru V, zwanych krawędziami; E. { (u,v) : u,v. V } Przez n oznaczamy liczbę wierzchołków Przez m oznaczamy liczbę krawędzi Rys. 1. Przykład grafu skierowanego [Internet] Grafem nieskierowanym (grafem) nazywamy strukturę G=(V, E) gdzie V to zbiór wierzchołków, E to zbiór dwuelementowych podzbiorów/multizbiorów zbioru V zwanych krawędziami; E. { {u,v} : u,v. V i u. v}. { {u,u} : u. V } Sąsiad: Dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimi. Stopień wierzchołka to liczba jego sąsiadów. Droga (ścieżka) droga w grafie skierowanym stanowi listę wierzchołków, (n1, n2,..., nk) taka, że występuje krawędź łącząca każdy wierzchołek z następnym, to znaczy (ni ,ni+1) dla i=1,2,....,k. Długość drogi wynosi k-1, co stanowi liczbę krawędzi należących do tej samej drogi. Droga prosta droga wyznaczona tak, że żadna krawędź na trasie nie powtarza się Rys. 2. Przykład grafu Długość drogi to ilość krawędzi/wierzchołków nieskierowanego [Internet] tworzących daną drogę/ścieżkę. Graf spójny to graf, w którym istnieje ścieżka od każdego z jego wierzchołków do dowolnego innego nazywamy grafem spójnym. Graf regularny - to graf, w którym każdy wierzchołek ma taki sam stopień. Cykl w grafie skierowanym jest drogą o długości 1 lub więcej, która zaczyna się i kończy w tym samym wierzchołku. Długość cyklu jest długością drogi. Jeśli cykle nie występują to, graf określa się mianem acyklicznego (acyclic). Drzewo jest to graf spójny bez cykli. Równoważnie: drzewo o n wierzchołkach to graf spójny o dokładnie n - 1 krawędziach. Drzewo rozpinające - drzewo rozpinające dla danego grafu jest to drzewo zawierające wszystkie wierzchołki tego grafu. Graf ważony - graf ważony to graf, w którym każdej krawędzi przypisana jest pewna waga, np. długość krawędzi, czas lub koszt jej przebycia. Do krawędzi może być przypisana więcej niż jedna waga (np. koszt jednostkowy i odległość). Graf pełny to taki graf, w którym każdy wierzchołek jest sąsiadem każdego innego (graf w którym istnieją połączenia typu “każdy z każdym”. Graf pełny o n wierzchołkach oznacza się przez Kn. Posiada on n * (n-1)/2 krawędzi - tyle, ile par różnych wierzchołków. Graf planarny to graf, który można narysować na płaszczyźnie w taki sposób, że żadne dwie krawędzie się nie przecinają Macierz sąsiedztwa Budujemy tablicę o rozmiarach V*V, gdzie V to liczba wierzchołków. Następnie wypełniamy ją: Zerami - jeśli dwa wierzchołki nie są połączone krawędzią. Wagami łuków - jeśli dwa wierzchołki są połączone Macierze sąsiedztwa są preferowanym sposobem reprezentacji grafów wówczas, gdy grafy są gęste (dense), to znaczy, kiedy liczba krawędzi jest bliska maksymalnej możliwej ich liczby. Dla grafu skierowanego o n wierzchołkach maksymalna liczba krawędzi wynosi n2. Rys. 3. Graf i jego macierz sąsiedztwa [Internet] Rys. 4. Macierze sąsiedztwa - przykład tworzenia Lista incydencji Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Złożoność pamięciowa: O(V+E) Jeśli graf jest rzadki (sparse) to reprezentacja oparta na listach sąsiedztwa może pozwolić zaoszczędzić pamięć Rys. 5. Reprezentacja grafu w postaci listy [Internet] 3. Przeszukiwanie grafów Przeszukiwanie wszerz (breadth-first search) Algorytm przeszukiwania grafu używany do przechodzenia lub przeszukiwania grafu lub drzewa. Algorytm zaczyna od korzenia i odwiedza wszystkie połączone z nim węzły. Następnie odwiedza węzły połączone z tymi węzłami i tak dalej, aż do odnalezienia celu. funkcja przeszukiwanie_wszerz (Start, Cel) { dodaj_do_kolejki(Kolejka, Start) dopóki nie_pusta(Kolejka) { Wierzchołek:= pobierz_z_kolejki(Kolejka) jeżeli Wierzchołek = Cel { zwróć Wierzchołek } dla każdego Syna w Wierzchołek { jeżeli nie_odwiedzony(Syn) { zapamiętaj_że_odwiedzony(Syn) dodaj_do_kolejki(Kolejka, Syn) } } } } Rys. 6. Ilustracja zasady breadth-first [Internet] Przeszukiwanie w głąb (depth-first search) Algorytm przeszukiwania grafu używany do przechodzenia lub przeszukiwania drzewa lub grafu. Przeszukiwanie zaczyna się od korzenia i porusza się w dół do samego końca gałęzi, po czym wraca się o jeden poziom i próbuje kolejne gałęzie itd. Zastosowanie: znajdowanie cyklów w grafie; DFS ma znaczenie, jako że jest pośrednio wykorzystywany w wielu innych algorytmach def dfs(v, visited = None, preorder_process = None, postorder_process = None): if visited is None: visited = set() visited.add(v) preorder_process(v) for neighbor in v.neighbors: if neighbor not in visited: dfs(neighbor, visited, preorder_process, Rys. 7. Ilustracja zasady postorder_process) depth-first [Internet] postorder_process(v) { N - liczba wierzcholkow D[1..N],F[1..N] - tablice numeracji pre-order i post-order P[1..N] - tablica poprzednikow (tzn. do wierzch. i-tego przeszlismy z wierzch. p[i]) } procedure Visit(v: Integer); {proc. rekurencyjnego odwiedzania wierzch.} begin D[v]:=time; {przydzielenie numerka w numeracji pre-order} Inc(time); for i:=Successor(v) do {petla po nastepnikach wierzch. v} if D[i]=-1 then {jesli wierzch. i jest bialy to...} begin P[i]:=v; {zaznaczamy, ze to z wierzch. v przechozimy do i} Visit(i); {przechodzimy rekurencyjnie do wierzch. i} end {opcjonalnie ponizsze 3 linijki jezeli potrzebne jest nam sprawdzanie cykli} else if F[i]=-1 then {jesli wierzch. i jest szary to...} Cycle_Found; {stwierdzenie, ze w grafie jest cykl} F[v]:=time; {przydzielenie numerka w numeracji post-order} Inc(time); end; procedure DFS; begin for i:=1 to N do begin D[i]:=-1;F[i]:=-1; {oznaczamy wszystkie wierzcholki jako biale} {Uwaga! wierzch. biale maja obie wartosci rowne -1; czarne - obie rozne od -1; szare - D rozne od -1, F rowne -1} end; time:=1; {zmienna potrzebna do numeracji} for i:=1 to N do if D[i]=-1 then {jesli wierzch. i jest bialy to...} begin P[i]:=-1; {zaznaczamy, ze wierzch. i jest jednym z wierzch. startowych} Visit(i); {przechodzimy do wierzch. i} end; end;  4. Najkrótsze drogi w grafie Algorytm Dijkstry (Edsger Dijkstra, 1959) Algorytm służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi. function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity // Unknown distance function from source to v 4 previous[v] := undefined // Previous node in optimal path from source 5 dist[source] := 0 // Distance from source to source 6 Q := the set of all nodes in Graph // All nodes in the graph are unoptimized - thus are in Q 7 while Q is not empty: // The main loop 8 u := vertex in Q with smallest dist[] 9 remove u from Q 10 for each neighbor v of u: // where v has not yet been removed from Q. 11 alt := dist[u] + dist_between(u, v) // dist[u] is never infinity since we initialized dist[source] := 0 12 if alt < dist[v] // Relax (u,v,a) 13 dist[v] := alt 14 previous[v] := u 15 return previous[]  Algorytm Bellmana-Forda (1958) Algorytm dla dowolnych wag łuków (metoda poprawiania cech) procedure BellmanFord(list vertices, list edges, vertex source) // Step 1: Initialize graph for each vertex v in vertices: if v is source then v.distance := 0 else v.distance := infinity v.predecessor := null // Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge uv in edges: // uv is the edge from u to v u := uv.source v := uv.destination if v.distance > u.distance + uv.weight: v.distance := u.distance + uv.weight v.predecessor := u // Step 3: check for negative-weight cycles for each edge uv in edges: u := uv.source v := uv.destination if v.distance > u.distance + uv.weight: error "Graph contains a negative-weight cycle" Algorytm Floyda-Warshalla (1962) Algorytm Floyda-Warshalla korzysta z tego, że jeśli najkrótsza ścieżka pomiędzy wierzchołkami v1 i v2 prowadzi przez wierzchołek u, to jest ona połączeniem najkrótszych ścieżek pomiędzy wierzchołkami v1 i u oraz u i v2. procedura Floyd-Warshall(G,w) dla każdego wierzchołka v1 w V[G] wykonaj dla każdego wierzchołka v2 w V[G] wykonaj d[v1][v2] = nieskończone poprzednik[v1][v2] = niezdefiniowane d[v1][v1] = 0 dla każdej krawędzi (v1,v2) w E[G] d[v1][v2] = w(v1,v2) poprzednik[v1][v2] = v1 dla każdego wierzchołka u w V[G] wykonaj dla każdego wierzchołka v1 w V[G] wykonaj dla każdego wierzchołka v2 w V[G] wykonaj jeżeli d[v1][v2] > d[v1][u] + d[u][v2] to d[v1][v2] = d[v1][u] + d[u][v2] poprzednik[v1][v2] = poprzednik[u][v2] 5. Zastosowania w automatyzacji Projekt przestrzeni produkcyjnej Etapy działania: Rozmieszczenie przestrzenne stanowisk. Dobór rodzaju i ilości środków transportowych. Dobór rodzaju magazynów. Ustalenie całkowitej niezbędnej powierzchni. Problem rozmieszczenia Rozmieszczenie stanowisk polega na przyporządkowaniu miejsc lokalizacji w taki sposób, aby spełnić określone warunki. Rozmieszczenie stanowisk wiąże się z: projektowaniem rozwiązań teoretycznych (schematy rozmieszczania stanowisk), projektowaniem szczegółowym (plan rozmieszczenia). Schemat rozmieszczenia Teoretyczny model szczegółowego planu rozmieszczenia. To ogólna koncepcja przestrzennego rozmieszczenia stanowisk, czyli: wzajemne usytuowanie stanowisk, ogólny kształt powierzchni, układ dróg transportowych. Praktyczne możliwe rozmieszczenia Dla gniazd przedmiotowych: o swobodnym dostępie funkcjonalne (modułowe) komórkowe Dla linii produkcyjnych: w liniach wielorzędowych kołowe segmentowe Powiązania transportowe mogą mieć charakter: trwały (sztywne powiązania) – w liniach jednoprzedmiotowych i systemac elastycznych, nietrwały (luźne powiązania) – w gniazdach przedmiotowych, liniach wieloprzedmiotowych niezautomatyzowanych jak i pomiędzy gniazdami technologicznymi. Rys. 8. Przykładowe rozmieszczenie stanowisk w hali produkcyjnej [Internet] BIBLIOGRAFIA Z. Banaszak, L. Jampolski, Komputerowo wspomagane modelowanie ESP, WNT, 1991 M. Sysło, N. Deo, J. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, PWN, 1998 Zautomatyzowane Zautomatyzowane Systemy Systemy Wytwórcze Wytwórcze Sieci Sieci Petriego Petriego Piotr PiotrSkrzypczyński Skrzypczyński 1 Definicje podstawowe Sieć Petriego jest czwórką C = ( P, T, I, O ), w której P = { p1 , p2 ,... , pn } jest skończonym zbiorem miejsc, T = { t1 , t2 ,... , tm } jest skończonym zbiorem tranzycji, I : T → P* jest funkcją wejściową, a O : P → T* jest funkcją wyjściową. Zbiory miejsc i tranzycji są rozłączne P ∩T = F. Wartością funkcji I ( tj ) jest kolekcja miejsc wejściowych tranzycji tj. Wyrażenie # ( pi , I ( tj ) ) oznacza liczbę wystąpień miejsca pi w kolekcji I ( tj ). Wartością funkcji O ( tj ) jest kolekcja miejsc wyjściowych tranzycji tj. Wyrażenie # ( pi , O ( tj ) ) oznacza liczbę wystąpień miejsca pi w kolekcji O ( tj ). Graficzną reprezentacją sieci jest graf dwudzielny, którego węzłami są miejsca, rysowane jako okręgi, i tranzycje, rysowane jako odcinki. Węzły grafu są połączone skierowanymi łukami w taki sposób, że żadne dwa miejsca i żadne dwie tranzycje nie są połączone bezpośrednio. Graf zawiera # ( pi , I ( tj ) ) łuków od miejsca pi do tranzycji tj oraz # ( pi , O ( tj ) ) łuków od tranzycji tj do miejsca pi. Rys. 1 Reprezentacja graficzna miejsc i przejść Miejsca sieci mogą zawierać znaczniki, zaznaczane graficznie kropkami. Rozkład znaczników we wszystkich wyznacza znakowanie sieci, zdefiniowane jako funkcja: m : P → N, ze zbioru miejsc w zbiór liczb naturalnych z zerem. Równoważnie, znakowanie można traktować jako wektor m = ( m ( p1 ), m ( p2 ),... , m ( pn ) ). W tym ujęciu zbiór wszystkich możliwych znakowań sieci jest równy Nn. Znakowana sieć Petriego jest parą Z = ( C, m0 ), w której C jest siecią Petriego, a m0 : P → N jest znakowaniem początkowym. Znakowanie sieci może ulec zmianie w wyniku odpalenia tranzycji. Warunkiem odpalenia jest wzbudzenie tranzycji, wyrażające się obecnością odpowiedniej liczby znaczników we wszystkich jej miejscach wejściowych. Odpalenie usuwa z każdego miejsca tyle znaczników, ile łuków prowadzi od tego miejsca do tranzycji, i deponuje w każdym miejscu tyle znaczników, ile łuków prowadzi od tranzycji do tego miejsca. Tranzycja tj jest wzbudzona (enabled) w znakowaniu m, jeśli: (" piÎ∈P ) [ # ( pi , I ( tj ) ) ≤m ( pi ) ] Odpalenie (firing) tranzycji tj wzbudzonej w znakowaniu m powoduje powstanie nowego znakowania m' określonego przez warunek: (" pi∈P ) [ m' ( pi ) = m ( pi ) - # ( pi , I ( tj ) ) + # ( pi , O ( tj ) ) ] Odpalenie serii tranzycji, wzbudzonych w kolejno powstających znakowaniach poczynając od znakowania początkowego, jest nazywane wykonaniem znakowanej sieci ( C, µ0 ). Wykonanie sieci produkuje ciąg kolejnych znakowań ( µ0 , µ1 ,... µk ,... ) oraz ciąg tranzycji ( tj0 , tj1 ,... tjk ,... ), taki że tranzycja tjk jest wzbudzona w znakowaniu µk. W ten sposób znakowana sieć Petriego tworzy maszynę abstrakcyjną o przestrzeni stanów Nn i funkcji przejścia d : Nn × T →Nn określonej następująco: 1. Wartość funkcji d ( m , tj ) jest określona wtedy i tylko wtedy gdy # ( pi , I ( tj ) ) ≤ m ( pi ) — warunek wzbudzenia. 2. Jeśli wartość funkcji d ( m , tj ) jest określona, to d ( m , tj ) = m' , gdzie: m' ( pi ) = m ( pi ) - # ( pi , I ( tj ) ) + # ( pi , O ( tj ) ) dla każdego pi Î∈ P — definicja odpalenia. Sekwencja znakowań ( m0 , m1 ,... mk ,... ) oraz sekwencja tranzycji ( tj0 , tj1 ,... tjk ,... ) powstające podczas wykonanie sieci spełniają warunek: mk+1 = d (mk , tjk ). Rys. 2 Sieć przed (a) i po (b) odpaleniu tranzycji Zbiór znakowań osiągalnych (reachability set) jest to najmniejszy zbiór R ( C, m0 ), taki że: 1. m0∈ R ( C, m0 ) 2. Jeśli ml∈ R ( C, m0 ) oraz istnieje tranzycja tj Î T taka, że mk = d (ml , tj ) to mkÎ R ( C, m0 ) Rys. 3 Sieć Petriego (a) i jej graf znakowań osiągalnych (b) W informatyce sieci Petriego wykorzystuje się do modelowania synchronizacji i komunikacji procesów współbieżnych. W takim zastosowaniu miejsca sieci interpretuje się zazwyczaj jako warunki (lub stany) programu, a tranzycje jako akcje, np. instrukcje lub funkcje. Struktura sieci odwzorowuje wtedy strukturę programów, a ruch znaczników w sieci modeluje postępujące wykonanie procesów. Zastosowanie sieci Petriego nie jest jednak ograniczone do tej jednej dziedziny. Abstrakcyjna definicja sieci jest w pełni ogólna i może być wykorzystana do modelowania procesów zachodzących w innych dziedzinach. (a) Sieć Petriego jest uznanym modelem przepływu sterowania w systemach współbieżnych. Podstawowe konstrukcje sieci pozwalają łatwo modelować podstawowe konstrukcje sterujące: sekwencyjne wykonanie operacji, alternatywę (z niedeterministycznym wyborem drogi), rozszczepienie akcji na równoległe ścieżki wykonania. (b) Odpalenie tranzycji jest akcją atomową, tzn. modeluje zdarzenie proste. Sieć Petriego umożliwia jednak również modelowanie zdarzeń złożonych, charakteryzowanych przez moment startu, moment zakończenia oraz okres trwania, podczas którego mogą zachodzić inne zdarzenia. Zajście zdarzenia może być uzależnione od zajścia zdarzeń wcześniejszych. (c) Pojedynczy znacznik rezydujący w miejscu z kilkoma łukami wyjściowymi prowadzącymi do różnych tranzycji może wzbudzić wszystkie tranzycje wyjściowe, jednak odpalić będzie mogła tylko jedna z nich. Korzystając z tego można modelować konflikty procesów w dostępie do rzadkich zasobów systemu: W podobny sposób można modelować inne uzależnienia wynikające z synchronizacji procesów, takie jak np. przekazywanie danych przez kolejki wiadomości lub komunikację przez spotkanie. (d) Modelowanie złożonych problemów prowadzi do powstania bardzo dużych sieci, niemożliwych do przedstawienia graficznego. Opanowanie złożoności rysunku jest możliwe dzięki hierarchicznej reprezentacji sieci, w której całe podsieci widoczne na diagramach niższego poziomu są zastępowane pojedynczymi miejscami lub pojedynczymi tranzycjami na rysunkach wyższego poziomu, pokazujących problem na wyższym poziomie abstrakcji. (e) Najpopularniejszymi modelami przepływu sterowania są automaty skończone i sieci działań. Semantyka tych modeli obejmuje jednak tylko systemy sekwencyjne. Semantyka sieci Petriego wychodzi poza systemy sekwencyjne i umożliwia modelowanie synchronizacji systemów równoległych. Dla każdego automatu lub sieci działań można skonstruować równoważny im model sieci Petriego. (f) Sieci Petriego stosuje się również do modelowania innych systemów, niż systemy komputerowe. Przykładami mogą być uzależnienia proceduralne w systemach prawnych lub zależności między fazami procesu technologicznego, a dostępnością maszyn na liniach produkcyjnych. 2 Właściwości sieci Zachowanie znakowanej sieci Petriego zależy od jej budowy i od znakowania początkowego. W różnych zastosowaniach sieci znaczenie mogą mieć różne aspekty jej działania. Wyróżnia się pewien zestaw właściwości, które można przekonująco interpretować w dziedzinach, z których wywodzą się modelowane systemy. Bezpieczeństwo (safeness) Miejsce pi∈ P jest bezpieczne, jeśli: (∀ µk∈ R ( C, µ0 ) ) [ µk ( pi ) ≤ 1 ] Sieć ( C, µ0 ) jest bezpieczna, jeśli wszystkie jej miejsca są bezpieczne. W dowolnym znakowaniu osiągalnym miejsca sieci bezpiecznej mogą zawierać co najwyżej jeden znacznik. Miejsca sieci bezpiecznej modelują więc warunki boolowskie, które mogą być albo spełnione (znacznik obecny), albo nie (brak znacznika). Zachowanie sieci bezpiecznej może być łatwo modelowane w układach sprzętowych, w których każdemu miejscu odpowiada jeden przerzutnik. Ograniczoność (boundedness) Miejsce pi∈ P jest q-ograniczone, jeśli (∀ µk∈ R ( C, µ0 ) ) [ µk ( pi ) ≤ q ] Sieć ( C, µ0 ) jest ograniczona, jeśli wszystkie jej miejsca są q-ograniczone dla q. W dowolnym znakowaniu osiągalnym miejsca sieci ograniczonej mogą zawierać co najwyżej skończoną liczbę znaczników. Zbiór wszystkich możliwych znakowań sieci ograniczonej jest więc skończony, co gwarantuje pełną analizowalność sieci. Zachowawczość (conservation) Sieć ( C, µ0 ) jest ściśle zachowawcza, jeśli ( ∀µk∈ R ( C, µ0 ) ) [ Σ( i≤ n ) µk ( pi ) = Σ( i≤ n) µ0 ( pi ) ] Sieć ( C, µ0 ) jest zachowawcza, jeśli istnieje taki dodatni wektor w = ( w1,... , wn ), że: (∀ µk∈ R ( C, µ0 ) ) [ Σ( i≤ n ) wi × µk ( pi ) =Σ( i≤ n ) wi × µ0 ( pi ) ] Sieć jest ściśle zachowawcza, jeśli liczba znaczników we wszystkich znakowaniach osiągalnych jest stała. Sięc jest zachowawcza, jeśli podczas wykonania znaczniki mogą rozszczepiać się i łączyć ponownie, powracając do tej samej liczby. Zachowawczość jest nieodzowną właściwością sieci modelującej konflikty zasobowe występujące podczas wykonania programów. Liczba znaczników w niektórych miejscach sieci modeluje tu liczbę dostępnych jednostek zasobowych systemu, która nie ulega zmianie w wyniku wykonania operacji przydzielenia lub zwolnienia zasobu. Żywotność (liveness) Tranzycja tj∈ T jest żywa, jeśli (∀ µk∈ R ( C, µ0 ) ) (∃ µ ∈ R ( C, µk ) ) [ ( µ , t ) ∈ Dom ( δ ) ] Sieć ( C, µ0 ) jest żywa, jeśli każda jej tranzycja jest żywa. Tranzycja jest żywa, jeśli z dowolnego znakowania osiągalnego sieci można dojść do takiego znakowania, w którym ta tranzycja będzie mogła odpalić. Sieć jest żywa, jeśli dla każdej tranzycji można z każdego znakowania osiągalnego dojść do takiego znakowania, w którym ta tranzycja będzie mogła odpalić. Zakleszczenie (deadlock) Sieć ( C, µ0 ) ma zakleszczenie, jeśli ( ∃ µ ∈ R ( C, µ0 ) ) (∀ t ∈ T ) ( ( µ , t ) ∉ Dom ( δ)) Sieć jest wolna od zakleszczeń, jeśli: (∀ µ ∈ R ( C, µ0 ) ) (∃ t ∈ T ) ( ( µ , t ) ∈ Dom ( δ)) Zakleszczenie oznacza niemożliwość odpalenia jakiejkolwiek tranzycji. W odniesieniu do oprogramowania właściwość ta oznacza zawieszenie się wszystkich procesów programu. Osiągalność znakowania (reachability) (a) Problem osiągalności: “Czy możliwe jest osiągnięcie wskazanego znakowania µk, tzn. czy µk∈ R ( C, µ0 ) ?” (b) Problem pokrycia: “Czy dla danego znakowania µk istnieje µl∈ R ( C, µ0 ) takie, że µl ≥ µk ?” (c) Osiągalność znakowania częściowego: “Czy dla danego znakowania µx określonego na Px ⊂ P istnieje µl∈ R ( C, µ0 ) takie, że µx = µl | Px ?” 3 Analiza sieci Podstawową metodą analizy sieci Petriego jest budowa i analiza drzewa osiągalności. Inne metody, w tym przede wszystkim równania macierzowe i analiza niezmienników, mają mniejsze znaczenie. Drzewo znakowań osiągalnych (reachability tree) Drzewo osiągalności jest grafem skierowanym, reprezentującym w skończony sposób wszystkie wykonania sieci (być może nieskończone). Węzłami drzewa są znakowania osiągalne, a łukami są odpalenia tranzycji. Korzeniem drzewa jest znakowanie początkowe, a jego liśćmi są znakowania końcowe lub znakowania powtórzone. Konstrukcja drzewa rozpoczyna się od znakowania początkowego i polega na obliczaniu kolejnych znakowań sieci, przez odpalanie wszystkich wzbudzonych w danym znakowaniu tranzycji. Ograniczenie rozmiarów drzewa zapewnia wprowadzenie specjalnego symbolu ω , oznaczającego możliwość gromadzenia się w miejscu sieci dowolnie dużej liczby znaczników. Jeśli w którejkolwiek gałęzi drzewa µ0... µk... µl... wystąpi znakowanie większe od poprzedniego, tzn. takie w którym: (∀ p∈ P ) ( µl ( p ) ≥ µk ( p ) ) & (∃ pi∈ P ) ( µl ( pi ) > µk ( pi ) ) to przyjmuje się: µl ( pi ) = ω. Właściwości symbolu ω : ω+a=ω ω−a=ω a µy ( p ) , to µz ( p ) = ω — w każdym innym przypadku µz ( p ) = δ ( µx , t )( p ) Znakowanie µx staje się teraz znakowaniem wewnętrznym, a znakowanie µz granicznym. Zastosowanie drzewa znakowan osiagalnych Drzewo osiągalności jest skończoną reprezentacją nieskończonego zbioru osiągalności, nie może więc zawierać całej informacji o tym zbiorze. Dlatego nie wszystkie właściwości i problemy badawcze dotyczące sieci Petriego można rozstrzygnąć w oparciu o analizę drzewa. Bezpieczeństwo i ograniczoność Sieć jest ograniczona, jeśli w drzewie osiągalności nie występuje symbol ω. Wystąpienie symbolu ω wskazuje na możliwość nieograniczonej kumulacji znaczników, przy czym pozycja symbolu wskazuje miejsce, które jest nieograniczone. Zachowawczość Mając zadany wektor w można obliczyć sumy ważone wszystkich znakowań drzewa i sprawdzić, czy są one równe. Jeśli na którejś pozycji znakowania występuje symbol ω , to sieć może być zachowawcza tylko wtedy, gdy odpowiadająca mu składowa wektora w ma wartość 0 (ściśle biorąc, definicja zachowawczości wymaga wi > 0 dla każdego i ). Nie znając wektora w można dla każdego węzła j, j = 1.. k , drzewa osiągalności ułożyć równanie: Σ( i ≤ n ) wi × µ j ( pi ) = s. Otrzymując w rezultacie układ k równań liniowych i n nierówności z n+1 niewiadomymi: Σ ( i ≤ n ) wi × µ j ( pi ) = s j = 1.. k wi > 0 i = 1.. n Sieć jest zachowawcza, jeśli ten układ ma rozwiązanie. 4 Opis macierzowy sieci Sieć Petriego można reprezentować w postaci dwóch macierzy: D−, D+, których kolumny 1...n odpowiadają miejscom, a wiersze 1...m tranzycjom. Komórki macierzy D− reprezentują funkcję wejściową I, a komórki macierzy D+ reprezentują funkcję wyjściową O, tzn.: D− ( j, i ) = # ( pi, I ( tj ) ) D+ ( j, i ) = # ( pi, O ( tj ) ) Tranzycję reprezentuje jednostkowy m-wektor wierszowy e( j ). Znakowanie sieci jest n-wektorem wierszowym µ. Warunek wzbudzenia tranzycji tj w znakowaniu µ ma postać: µ ≥ e( j ) × D− Wynik odpalenia tranzycji tj w znakowaniu µ opisuje funkcja przejścia δ : δ ( µ , tj ) = µ − e( j ) × D− + e( j ) × D+ = µ + e( j ) × (D+ − D− ) = µ + e( j ) × D gdzie D = D+ − D−. Wynik odpalenia sekwencji tranzycji σ = ( tj1 , tj2 ,..., tjk ): δ ( µ , σ ) = µ + e( j1 ) ⋅ D + e( j2 ) ⋅ D +... + e( jk ) ⋅ D = = µ + ( e( j1 ) + e( j2 ) +... + e( jk ) ) × D = µ + f ( σ ) × D gdzie: f ( σ )j oznacza liczbę odpaleń tranzycj tj (Parikh mapping). Macierzowa reprezentacja sieci Petriego jest wygodna w obliczeniach komputerowych. Umożliwia łatwe badanie zachowawczości sieci oraz pozwala sformułować warunek konieczny (ale nie dostateczny) osiągalności znakowania. Zachowawczość Sieć jest zachowawcza jeśli: ( ∃ w ) ( ∀ µ ∈ R ( C, µ0 ) ) ( µ0 × wT = µ × wT ). Skoro µ ∈ R ( C, µ0 ) , to istnieje sekwencja odpaleń σ taka, że: µ = µ0 + f ( σ ) × D. Podstawiając wartość µ do poprzedniego równania otrzymujemy: µ0 × wT = µ × wT = ( µ0 + f ( σ ) × D ) ⋅ wT = µ0 × wT + f ( σ ) × D × wT Odejmując stronami wyrażenie µ0 × wT dochodzimy do równania f ( σ ) × D × wT = 0 , które musi być spełnione dla każdego f ( σ ) Ostatecznie otrzymujemy układ równań: D × wT = 0 , który ma rozwiązanie w wtedy i tylko wtedy, gdy sieć jest zachowawcza. Osiągalność Jeżeli µ ∈ R ( C, µ0 ) to istnieje sekwencja odpaleń σ taka, że f ( σ ) = x jest rozwiązaniem równania µ = µ0 + x × D. Zatem jeżeli znakowanie µ jest osiągalne, to równanie µ = µ0 + x × D ma rozwiązanie. 5 KOLOROWANE SIECI PETRIEGO. Klasyczne sieci Petriego są modelem przepływu sterowania, pozbawionym możliwości opisu przetwarzania danych i wpływu wyników tego przetwarzania na przebieg procesu obliczeniowego. Kolorowane sieci Petriego rozszerzają zakres modelu wprowadzając do niego wartości, przypisane do krążących w sieci znaczników, oraz funkcje sterujące przepływem tych znaczników i obliczające nowe wartości. Kolorowana sieć Petriego (Coloured Petri Net) jest grafem złożonym z miejsc, tranzycji i łuków, w którym poruszają się znaczniki przenoszące wartości określonego typu. W każdym miejscu sieci może znajdować się wiele różnych znaczników, których typ musi być jednak zgodny z typem tego miejsca. Wzbudzenie tranzycji w bieżącym znakowaniu sieci zależy zarówno od obecności znaczników w miejscach wejściowych tranzycji, jak i od wartości przypisanych do tych znaczników. Odpalenie tranzycji powoduje usunięcie pewnej liczby znaczników z miejsc wejściowych tranzycji i utworzenie pewnej liczby nowych znaczników w jej miejscach wyjściowych. Zgodnie z tradycyjną terminologią kolorowanych sieci Petriego typ danych nazywa się paletą kolorów, a aktualna wartość przypisana do znacznika — kolorem. Znaczniki różnych kolorów, zgromadzone w pewnym miejscu sieci, tworzą kolekcję znaczników zapisywaną w postaci wyrażenia: n1'a1 + n2'a2 +... , w którym symbole a1 , a2 oznaczają kolory, a symbole n1 , n2 liczby znaczników w poszczególnych kolorach. Kolorowana sieć Petriego jest uporządkowaną dziewiątką CPN = ( Σ , P, T, A, N, C, G, E, µ0 ), w której: Σ jest skończonym zbiorem palet kolorów (typów danych); P jest skończonym zbiorem miejsc; T jest skończonym zbiorem tranzycji, P ∩ T = Φ ; A jest skończonym zbiorem łuków, A ∩ P = Φ , A ∩ T = Φ ; N: A → ( P × T ) ∪ ( T × P ) jest funkcją określającą miejsce łuków w sieci; C: P → Σ jest funkcją przypisującą miejscom palety kolorów; G: T → expressions, jest funkcją przypisującą tranzycjom dozory; E: A → expressions ( E ( a )∈ C ( p ( a ) )* ) jest funkcja przypisującą łukom wyrażenia; µ0: P → expressions ( µ0 ( p )∈ C ( p )* ) jest znakowaniem początkowym. Znakowanie kolorowanej sieci Petriego jest funkcją µ : P → Σ* , przypisującą każdemu miejscu kolekcję rezydujących w tym miejscu znaczników (∀ p∈ P ) [ µ ( p )∈ C ( p )* ] Tranzycja t z wiązaniem zmiennych b jest wzbudzona w znakowaniu µ, jeśli: (∀ p∈ P ) [ E ( p, t ) ( b ) ≤ µ ( p ) ] Odpalenie tranzycji t z wiązaniem zmiennych b wzbudzonej w znakowaniu µ powoduje powstanie nowego znakowania µ' określonego przez warunek: (∀ p∈ P ) [ µ' ( p ) = µ ( p ) − E ( p, t ) ( b ) + E ( t, p ) ( b ) ] Krok odpalenia (step) jest funkcją częściową Y : T → B ( T )* przypisującą tranzycjom kolekcje dopuszczalnych wiązań zmiennych tych tranzycji (∀ t∈ T ) ( Y ( t )∈ B ( t )* ). Przypisana tranzycji t kolekcja wiązań zmiennych Y ( t ) wyznacza wiele takich kolekcji znaczników, których obecność w miejscach wejściowych umożliwia wielokrotne odpalenie tej tranzycji. Krok Y określa kolekcje znaczników, które rozmieszczone w miejscach sieci umożliwiają wielokrotne odpalenie tranzycji należących do dziedziny funkcji Y. Przyjmując oznaczenie: b∈ Y( t ) ⇔ ( t, b )∈ Y można zapisać warunek wzbudzenie kroku Y w znakowaniu µ : (∀ p∈ P ) [ ∑( (t,b)∈ Y ) E ( p, t ) ( b ) ≤ µ ( p ) ] Wynikiem odpalenia kroku Y wzbudzonego w znakowaniu µ jest nowe znakowanie µ' określone jako: µ' ( p ) = µ ( p ) − ∑( (t,b)∈ Y ) E( p, t ) ( b ) + ∑( (t,b)∈ Y ) E( t, p ) ( b ) Wykonanie sekwencji kroków Y1 , Y2 ,... , Yk... prowadzi do powstania sekwencji znakowań osiągalnych: µ0 [Y1> µ1 [Y2> µ2... µk -1 [Yk> µk... Analiza i weryfikacja modelu Każdą sieć kolorowaną można przekształcić w równoważną jej sieć Petriego, którą z kolei można analizować za pomocą standardowych metod analizy sieci. Stwierdzenie to, ważne z teoretycznego punktu widzenia, ma jednak niewielką przydatność praktyczną, gdyż sieć Petriego równoważna sieci kolorowanej jest na ogół olbrzymia. (Podobne znaczenie ma twierdzenie, że każdy problem z zakresu arytmetyki liczb całkowitych można wyrazić w języku maszyny Turinga). Realne możliwości formalnej analizy sieci kolorowanych są, niestety, ograniczone. Rozszerzenia wprowadzone do pierwotnego modelu sieci Petriego zwiększają wprawdzie siłę wyrazu tego modelu, ale ograniczają możliwości jego analizy. Nie udało się skonstruować ani odpowiednika drzewa osiągalności sieci kolorowanej, ani reprezentacji macierzowej. Jedynymi narzędziami analizy pozostała metoda niezmienników oraz analiza grafu osiągalności, który jednak w ogólnym przypadku może być nieograniczony. Niezmienniki sieci kolorowanej buduje się zliczając (ważąc) znaczniki różnych kolorów. Niezmienniki: (1) P( µ (B) + µ (C) + µ (D) + µ (E) ) = 2 — procesy typu p (2) Q( µ (A) + µ (B) + µ (C) + µ (D) + µ (E) = 3 — procesy typu q (3) E( µ (R) ) + Q( µ (B) + µ (C) ) = 1 — zasób R (4) E( µ (S) ) + Q( µ (B) ) + 2 ⋅ PQ( µ (C) + µ (D) + µ (E) ) = 3 — zasób S (5) E( µ (T) ) + P( µ (D) ) + PQ( µ (E) ) + P( µ (E) ) = 2 — zasób T 5 Przykład modelu sieciowego prostego procesu Dane jest zrobotyzowane gniazdo realizujące proces pakowania butelek. W procesie technologicznym wyróżnia się operacje składowania butelek napływających z podajnika Tr1 w magazynie S, transportu realizowanego przy pomocy robota R i wkładania butelek do pojemnika ustawionego na palecie V. Model sieciowy tego procesu składa się z miejsc P1 i P2 modelujących odpowiednio magazyn S i pojemnik na butelki, oraz z przejść t1, t2, i t3, modelujących zdarzenia odpowiadające operacjom technologicznym. Rys. 4 Zrobotyzowane gniazdo pakowania butelek  Wartości funkcji K(P1) =3 i K(P2)=4 charakteryzują pojemności magazynu S oraz pojemnika na butelki. Kolejne znakowania osiągalne z serowego znakowania początkowego M0=(0,0) można wyznaczyć w następujący sposób: Strukturę drzewa znakowań osiągalnych dla tego modelu przedstawia Rys. 5. Rys. 5 Graf znakowań osiągalnych BIBLIOGRAFIA Banaszak Z., Jampolski L., Komputerowo wspomagane modelowanie ESP, WNT, 1991 Ben-Ari M.: Podstawy programowania współbieżnego. WNT, Warszawa 1989. Iszkowski W., Maniecki M.: Programowanie współbieżne. WNT, Warszawa 1982. Reisig W.: Sieci Petriego (tłum. z j. angielskiego). WNT, Warszawa 1988. Starke P. H.: Sieci Petri. Podstawy, zastosowania, teoria (tłum. z j. niemieckiego). PWN, Warszawa 1987. Suraj Z., Komarek B.: GRAF. System graficznej konstrukcji i analizy sieci Petriego. Akademicka Oficyna Wydawnicza PLJ, Warszawa 1994. Weiss Z., Gruźlewski T.: Programowanie współbieżne i rozproszone w przykładach i zadaniach. WNT, Warszawa 1993. Zautomatyzowane Zautomatyzowane Systemy Systemy Wytwórcze Wytwórcze Sieci Sieci Petriego Petriego Przykłady Przykłady Piotr PiotrSkrzypczyński Skrzypczyński