UNIVERZITET U BEOGRADU MASˇINSKI FAKULTET Goran M. Lazovic´ PROJEKTOVANJE I ISPITIVANJE STRUKTURA BAZA PODATAKA U UPRAVLJANJU ODRZˇAVANJEM VAZDUHOPLOVNIH SISTEMA doktorska disertacija Beograd, 2012 Mentor: Dr Slobodan Radojevic´, vanredni profesor, Univerzitet u Beogradu, Masˇinski Fakultet Komentor: Dr Slobodan Stupar, redovni profesor, Univerzitet u Beogradu, Masˇinski Fakultet Cˇlanovi komisije: Dr Zlatko Petrovic´, redovni profesor, Univerzitet u Beogradu, Masˇinski Fakultet Dr Ivan Arandelovic´, vanredni profesor, Univerzitet u Beogradu, Masˇinski Fakultet Dr Milan Bozˇic´, vanredni profesor, Univerzitet u Beogradu, Matematicˇki Fakultet Datum odbrane: Projektovanje i ispitivanje struktura baza podataka u upravljanju odrzˇavanjem vazduhoplovnih sistema Rezime Visoki zahtevi koji se postavljaju sistemu za odrzˇavanje vazduhoplova izmedu ostalog zahtevaju temeljnu analizu postojec´e strategije odrzˇavanja i njeno znacˇajno unapredenje. Savremeni sistemi odrzˇavanja obuhvataju i upravljanje odrzˇavanjem, tj. zasnovani su na automatizovanoj podrsˇci odrzˇavanju primenom racˇunara (Computer Integrated Maintenance Management). U osnovi automatizovane podrsˇke odrzˇavanju primenom racˇunara je model podataka. Veoma je vazˇno da je model podataka dovoljno bogat da bi mogao, na relativno lak nacˇin prihvatiti i u sebe ukljucˇiti razlicˇite koncepte realnog sistema zajedno sa svojim atribu- tima i medusobnim vezama. Hijerarhijske strukture podataka (strukture podataka tipa stablo) su posebno interesantne u sistemu odrzˇavanja vazduhoplova i one su predmet istrazˇivanja u ovom radu. Postavlja se sledec´i zahtev. Obezbediti takvu implementaciju hijerarhijske struk- ture koja pruzˇa moguc´nost njene efikasne obrade. Rekurzija koja je u osnovi hijerarhijske strukture podataka odnosno stabla koji je reprezent ovakve strukture podataka, mozˇe biti problem u efikasnom upravljanju sistemom odrzˇavanja vazduhoplova. U radu su date nove karakterizacije stabla, koje daju osnov za nerekurzivne modele hijerarhijske strukture poda- taka. U kontekstu ogranicˇenih resursa u sistemu za odrzˇavanje vazduhoplova posebno su intere- santne optimalne strategije odrzˇavanja. Bitan segment sistema za upravljanje odrzˇavanjem je planiranje odrzˇavanja. Jedan od osnovnih problema izmedu ostalog je neizvesnost dogadaja koji znacˇajno uticˇu na samo planiranje. Recˇ je o dogadajima koji su po svojoj prirodi slucˇajni. Posebno analizira se planiranje odrzˇavanja u slucˇaju kada skup aktivnosti ima hijerarhijsku strukturu i pri tome je trajanje pojedinih aktivnosti iz datog skupa aktivno- sti slucˇajna velicˇina. Pod pretpostavkom da aktivnost na viˇsem nivou hijerarhije ne mozˇe zapocˇeti pre nego sˇto su zavrsˇene sve aktivnosti na nizˇem nivou hijerarhije i da su poznati gubici koji nastaju u slucˇaju da se sa nekim aktivnostima kasni, odnosno da su poznati gu- bici u slucˇaju da su neke aktivnosti preuranjene, potrebno je formirati optimalnu strategiju aktiviranja aktivnosti iz datog skupa. U slucˇaju hijerarhije visine jedan problem se svodi na poznati newsboy problem, ali je u opsˇtem slucˇaju isuviˇse komplikovan. U radu se predlazˇe heuristicˇki pristup kojim se do resˇenja dolazi iterativnom primenom jednostavnog resˇenja problema na dvononiovskoj hijerarhiji. Vazduhoplovi su savremena saobrac´ajna sredstva vrhunske tehnologije sa velikim bro- jem komponenti i kompleksnom strukturom. Pojedine komponente vazduhoplova se koriste na razlicˇit nacˇin, trpe razlicˇita opterec´enja i odrzˇavaju po programu koji je njima najbolje prilagoden. Jedan od nacˇina savladavanja slozˇenosti je takozvana hijerarhijska dekompozi- cija. Slozˇeni koncept se na jednom nivou apstrakcije posmatra kao jedinstvena celina. Na nizˇem nivou apstrakcije se posmatra kao koncept koji se sastoji od delova (komponenti). Uzastopnom primenom opisanog postupka dobija se takozvana hijerarhijska sastavnica. Da- kle jedan od bitnih koncepata u sistemu odrzˇavanja vazduhoplova jeste sastavnica. Poseban problem je obezbediti kvalitetan sadrzˇaj hijerarhijske strukture podataka, odnosno u sistemu za upravljanje odrzˇavanjem vazduhoplova treba obezbediti kvalitetnu sastavnicu. U radu je predlozˇena fleksibilna struktura sastavnica koja u velikoj meri podrzˇava njeno sadrzˇajno rasˇirenje. Kljucˇne recˇi: odrzˇavanje vazduhoplova, hijerarhijska struktura podataka, stablo, newsboy problem, sastavnica Naucˇna oblast: tehnicˇke nauke, masˇinstvo Uzˇa naucˇna oblast: vazduhoplovstvo, racˇunarske nauke UDK: 004.6:629.7(043.3) Design and investigation of database structures in aircraft maintenance management systems Abstract The high demands that are placed to aircraft maintenance systems among other things require thorough analysis of existing maintenance strategy and its significant improvement. Modern maintenance systems include the management of maintenance, i.e. they are based on automated maintenance support by computer - Computer Integrated Maintenance Mana- gement. The basic component in automated maintenance support account is data model. It is important that the data model is rich enough to accept in a relatively easy way a variety of real system concepts together with their attributes and interrelations. Hierarchical data structure ( textit tree type data structure) are of special interest in the aircraft maintenance systems, and they are the subject of this study. This raise the following request. Implement hierarchical data structure which allows efficient processing. Recursion which is essential in implementation of hierarchical data structure, i.e., of the tree, which is typical representative of these data structures, can be a problem in efficient aircraft maintenance management. This study gives a new characterizations of tree, which provide a basis for nonrecursive models of hierarchical data structures. In the context of limited resources in the aircraft maintenance systems, optimal mainte- nance strategies are of special interest. An important segment of the maintenance manage- ment system is maintenance planning. One of the major problems is uncertainty of events which significantly affect maintenance planning. These events are random by its nature. In particular, the planning of maintenance is analyzed in the case when the set of activities has a hierarchical structure and duration, of each activity from a given set of activities, is random value. Assuming that the activity at a higher level of hierarchy can not begin before the completion of all activities at a lower level of hierarchy, and that losses incurred in the case of delayed activities, i.e., losses incurred in the case of premature activity are known, it is necessary to establish optimal activating strategy for each activity from given set of activities. In the case of one level hierarchy, problem is reduced to the well known newsboy problem, but it is too complicated in general. In this study, a heuristic approach is proposed for the solution of general problem that is based on iterative application of the solution of a simple two levels hierarchy problem. Aircrafts are modern high-tech means of transport with a large number of components and complex structure. Components of aircraft are used in different ways, they suffer different loads and are maintained by the programs that are best suited for them. One way to overcome this complexity is so-called hierarchical decomposition. Complex concept at one level of abstraction is seen as unified. At the lower level of abstraction it is seen as a concept that consists of parts (other components). Repeated application of described procedure gives the so-called hierarchical bill of material. So one of the important concepts in the aircraft maintenance systems is bill of material. A particular problem is to provide quality hierarchical data structures to the aircraft maintenance management system, i.e., to provide quality bill of material. This study proposes a flexible structure of the bill of material which greatly supports disseminate its content. Keywords: aircraft maintenance, hierarchical data structure, tree, newsboy problem, bill of material Scientific area: technical sciences, mechanical engineering Scientific subarea: aeronautical engineering, computer science UDC:004.6:629.7(043.3) Sadrzˇaj 1 Uvod 6 2 Hijerarhijske strukture podataka 13 2.1 Uvodna razmatranja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Stablo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1 Rekurzivna definicija stabla . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.2 Nerekurzivna definicija stabla . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Modeli stabla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.1 Model sa listom susedstva . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 Model sa tranzitivnim zatvorenjem . . . . . . . . . . . . . . . . . . . . 22 2.3.3 Efikasnost modela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.4 Model sa izlistanim putanjama . . . . . . . . . . . . . . . . . . . . . . 24 2.3.5 Model sa ugnjezˇdenim skupovima . . . . . . . . . . . . . . . . . . . . . 32 2.3.6 Model sa ugnjezˇdenim intervalima . . . . . . . . . . . . . . . . . . . . 38 3 Planiranje odrzˇavanja vazduhoplova 47 3.1 Uvodna razmatranja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Newsboy model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2.1 Jedna linija sklapanja . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2.2 Viˇsestruka neodredenost . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3 Simultani zahtev I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3.1 Stablo sklapanja sa viˇse nivoa I . . . . . . . . . . . . . . . . . . . . . . 61 3.4 Simultani zahtev II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.4.1 Stablo sklapanja sa viˇse nivoa II . . . . . . . . . . . . . . . . . . . . . 72 4 Sastavnice 78 4.1 Uvodna razmatranja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2 Modularna sastavnica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2.1 Redosled ugradnje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.2.2 Neophodne kolicˇine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.2.3 Osobine modularne sastavnice . . . . . . . . . . . . . . . . . . . . . . . 85 4.3 Hijerarhijska sastavnica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3.1 Osnovni pojmovi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3.2 O broju proizvoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 1 Sadrzˇaj 4.3.3 Generisanje hijerarhijske sastavnice . . . . . . . . . . . . . . . . . . . . 93 5 Sistem odrzˇavanja vazduhoplova 97 5.1 Uvodna razmatranja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.2 Projektovanje algoritma za generisanje druge sastavnice . . . . . . . . . . . . 98 5.2.1 Zahvat ima nadredeni i nema podredeni sklop . . . . . . . . . . . . . . 99 5.2.2 Zahvat ima nadredeni i podredeni sklop i pri tome su to isti sklopovi . 100 5.2.3 Zahvat ima nadredeni i podredeni sklop i to su razlicˇiti sklopovi . . . 101 5.2.4 Zahvat ima podredeni i nema nadredeni sklop . . . . . . . . . . . . . . 102 5.2.5 Algoritam druge hijerarhijske sastavnice . . . . . . . . . . . . . . . . . 102 5.3 Proracˇun vremena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.3.1 Osnovne pretpostavke . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.3.2 Odredivanje maksimalnog vremena . . . . . . . . . . . . . . . . . . . . 106 5.3.3 Odredivanje vremena kompletiranja . . . . . . . . . . . . . . . . . . . 106 5.3.4 Algoritam proracˇuna vremena . . . . . . . . . . . . . . . . . . . . . . . 107 6 Zakljucˇak 115 Prilog A Newsboy problem 121 Prilog B HSII 125 2.1 HSII1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 2.2 HSII2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Prilog C Klasifikacija vremena u tehnologiji 130 2 Slike 2.1 Stablo sa najvazˇnijim elementima . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Implementacija stabla sa slike (2.1) . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Pre-Order obilazak stabla sa slike (2.1) . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Skupovi predaka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 Izlistane putanje-Nizovi predaka . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.6 Indeksiranje cˇvorova stabla . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7 Dewey-jeva decimalna notacija . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.8 Ugnjezˇdeni skupovi-Skupovi potomaka . . . . . . . . . . . . . . . . . . . . . . 36 2.9 Skup potomaka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.10 Selekcija intervala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.11 Binarni model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.12 Binarni model sa levom granicom . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.13 Binarni model insert - D ≤ X . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.14 Binarni model insert - X < H . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.15 Selekcija intervala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.16 Ternarni model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.17 Ternarni model sa levom granicom . . . . . . . . . . . . . . . . . . . . . . . . 44 2.18 Ternarni model - insert X < H . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.19 Ternarni model - insert H < Y < I . . . . . . . . . . . . . . . . . . . . . . . . 46 2.20 Ternarni model - insert I < Z . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1 Jedna linija sklapanja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2 Stablo sklapanja visine 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3 Grupno skladiˇstenje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 Grupno kasˇnjenje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.5 Grupno kasˇnjenje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.6 Grupno skladiˇstenje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.7 Promena trosˇkova kasˇnjenja . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.8 Jedna linija sklapanja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.9 Stablo sklapanja visine 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.10 Grupno skladiˇstenje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.11 Promena trosˇkova skladiˇstenja . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.12 Jedna linija sklapanja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3 Slike 4.1 Sastavnica radijatora hidraulike preuzeta iz proizvodnje. . . . . . . . . . . . . 79 4.2 Modularna sastavnica radijatora datog tabelom (4.1) . . . . . . . . . . . . . . 81 4.3 Modularna sastavnica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.4 Potpuna modularna sastavnica . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.5 Hijerarhijska sastavnica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.6 Hijerarhijska sastavnica novog proizvoda. . . . . . . . . . . . . . . . . . . . . 89 4.7 Modularna sastavnica {〈4, 7, 1, 5〉, 〈4, 6, 2, 5〉}. . . . . . . . . . . . . . . . . . . 90 4.8 Modularna sastavnica {〈4, 9, 1, 5〉, 〈4, 6, 2, 5〉}. . . . . . . . . . . . . . . . . . . 90 4.9 Modularna sastavnica {〈1, 3, 1, 13〉, 〈1, 2, 2, 7〉, 〈1, 4, 3, 11〉}. . . . . . . . . . . . 90 4.10 Modularna sastavnica {〈3, 5, 1, 1〉, 〈3, 6, 2, 1〉}. . . . . . . . . . . . . . . . . . . 91 4.11 Modularna sastavnica {〈2, 4, 1, 1〉, 〈2, 5, 2, 2〉, 〈2, 8, 3, 3〉}. . . . . . . . . . . . . 91 4.12 Modularna sastavnica, hijerarhijske sastavnice sa slike (4.5) . . . . . . . . . . 92 4.13 Modularna sastavnica hijerarhijske sastavnice sa slike (4.6) . . . . . . . . . . 92 4.14 Modularne sastavnica podsklopova . . . . . . . . . . . . . . . . . . . . . . . . 93 5.1 Skup zahvata sa nadredenim sklopom i bez podredenih sklopova . . . . . . . 99 5.2 Redosled zahvata sa nadredenim sklopom i bez podredenih sklopova . . . . . 99 5.3 Skup zahvata sa nadredenim sklopom koji je istovremeno i podredeni sklop . 100 5.4 Skup zahvata sa nadredenim sklopom i podredenim sklopovima . . . . . . . . 101 C.1 Komponentna vremena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 4 Tabele 2.1 Lista susedstva stabla sa slike (2.3) . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Tranzitivno zatvorenje liste susedstva (2.1) . . . . . . . . . . . . . . . . . . . 22 2.3 Uredenje na tranzitivnom zatvorenju (2.2) . . . . . . . . . . . . . . . . . . . . 23 4.1 Spisak delova grejnog tela - radijatora hidraulike. . . . . . . . . . . . . . . . . 79 4.2 Sve modularne sastavnice radijatora . . . . . . . . . . . . . . . . . . . . . . . 94 5.4 Maksimalno vreme operacije . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.5 Vreme kompletiranja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.6 Vreme kompletiranja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.7 GBOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.8 GBOM-nivo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.9 GBOM-nivo 2a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.10 GBOM-nivo 2b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.11 GBOM-nivo 2c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.12 GBOM-nivo 2d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.13 GBOM-nivo 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.14 GBOM-nivo 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.15 GBOM-nivo 1c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.16 GBOM-nivo 1d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.1 Operacije nad sklopom I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.2 Operacije nad sklopom II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.3 Operacije nad sklopom III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5 Glava 1 Uvod Vazduhoplovi su savremena saobrac´ajna sredstva vrhunske tehnologije sa velikim brojem komponenti i kompleksnom strukturom, pa se svi radovi na odrzˇavanju moraju sistemati- zovati. Pod odrzˇavanjem se podrazumevaju sve akcije cˇja je svrha zadrzˇavanje ili povratak elementa sistema u stanje u kojem mozˇe izvoditi predvidenu funkciju. Ove akcije izmedu ostalog ukljucˇuju detekciju otkaza, opravku i zamenu delova koji su doveli do otkaza. Prema [15], od tridesetih godina prosˇlog veka razvoj odrzˇavanja se odvijao u tri faze: I) Prva faza obuhvata period do II Svetskog rata u kome industrija nije bila visoko mehani- zovana, tako da otkazi opreme nisu bili znacˇajni. U toj fazi nije davan poseban prioritet prevenciji otkaza. U isto vreme oprema je bila predimenzionisana, vrlo pouzdana i bila je laka za opravljanje tako da nije bilo potrebe za sistematskim odrzˇavanjem. II) Druga faza je zapocˇela dramaticˇnim promenama u II Svetskom ratu, porastom zahteva za razlicˇitim robama i naglim porastom mehanizacije, odn. sve brojnije i sve slozˇenije masˇine izazivaju sve osˇtrije izrazˇene pojave otkaza. Rada se ideja da se otkazi mogu sprecˇiti prevencijom i javlja se koncept preventivnog odrzˇavanja. U sˇezdesetim se ovaj koncept ogleda u primeni preventivnog odrzˇavanja u fiksnim intervalima - odrzˇavanje po unapred utvrdenom resursu, koji mozˇe biti: − sati rada − predeni kilometri − ciklusi funkcionisanja − motocˇasovi itd. Trosˇkovi odrzˇavanja rastu rapidno u odnosu na ostale eksploatacione trosˇkove, sˇto do- vodi do razvoja sistema planiranja i upravljanja odrzˇavanjem. III) Trec´a faza pocˇinje sredinom sedamdesetih godina i okarakterisana je porastom ocˇekivanja od odrzˇavanja i pojavom novih istrazˇivanja i novih tehnika odrzˇavanja. Dok se u pret- hodnoj fazi, od odrzˇavanja ocˇekivalo da snizi trosˇkove, povec´a raspolozˇivost postrojenja i produzˇi zˇivotni vek opreme, sada se od odrzˇavanja ocˇekuje da, pored ranijih ocˇekivanja, ispuni i sledec´e zahteve: 6 Uvod − povec´anje sigurnosti opreme kako za rukovaoce tom opremom, tako i za okolinu − povec´anje pouzdanosti opreme − povec´anje kvaliteta proizvoda − povec´anje efektivnosti investicija u odrzˇavanje Ovako visoki zahtevi koji se postavljaju sistemu za odrzˇavanje izmedu ostalog zahtevaju temeljnu analizu postojec´e strategije odrzˇavanja i njeno znacˇajno unapredenje. Pre svega razmotrimo postojec´u strategiju odrzˇavanja vazduhoplova. U pocˇetku se pretpostavljalo da su resursi koji su na raspolaganju sistemu odrzˇavanja vazduhoplova neogranicˇeni. U danasˇnje vreme to vec´ nije slucˇaj, ne samo da su resursi ogranicˇeni vec´ su i u pojedinim situacijama ne- dostupni. Sve ovo je uticalo na razvoj strategija odrzˇavanja u kontekstu ogranicˇenih resursa. Od interesa su strategije odrzˇavanja kojima se obezbeduje optimalna pouzdanost sistema uz minimalne trosˇkove. Takve strategije odrzˇavanja zovemo optimalne strategije odrzˇavanja. Sˇto se ticˇe aktivnosti koje se sprovode i vremenskih trenutaka kada se one sprovode [24], postoje dve glavne kategorije u sistemu odrzˇavanja vazduhoplova: − Korektivno odrzˇavanje − Preventivno odrzˇavanje Pod korektivnim odrzˇavanjem (run to failure) se podrazumevaju aktivnosti koje se predu- zimaju jedino u slucˇaju pojave otkaza, a cˇiji je cilj povratak u prvobitno stanje. U ovoj kategoriji odrzˇavanja se polazi od pretpostavke da je efikasnije izvrsˇiti opravku odnosno za- menu nekog elementa tek kada otkazˇe. Dakle strategija odrzˇavanja je ne diraj dok radi. Ocˇigledne prednosti ovakvog pristupa su: − minimalni trosˇkovi odrzˇavanja − maksimalno iskoriˇsc´enje opreme (koristi se dok god funkcioniˇse) Sa druge strane nedostaci su: − nemoguc´nost planiranja odrzˇavanja imajuc´i u vidu neizvesnost trenutka otkaza − pouzdanost sistema je dovedena u pitanje Korektivno odrzˇavanje je i dalje dominantna strategija odrzˇavanja. Preventivno odrzˇavanje ukljucˇuje aktivnosti odrzˇavanja koje se sprovode pre nego sˇto dode do pojave otkaza, odnosno ove aktivnosti imaju zadatak da sprecˇe ili odlozˇe pojavu otkaza. U klasicˇnom preventivnom odrzˇavanju preduzima se preventivna zamena ili opravka na osnovu poznavanja prosecˇnog trajanja opreme. Polazna pretpostavka je da za svaki element si- stema postoji pravi trenutak kada nad njim treba sprovesti odredene aktivnosti preventivnog odrzˇavanja i da c´e se na ovaj nacˇin smanjiti ucˇestalost otkaza. Medutim ispostavilo se da ovakav pristup ne umanjuje uvek ucˇestalost otkaza. Pokazalo se da je ovako koncipirano preventivno odrzˇavanje pogodno samo za elemente sistema kod kojih ucˇestalost otkaza po- seduje izvesnu pravilnost. S obzirom na ovu cˇinjenicu razlikovac´emo dve vrste preventivnog 7 Uvod odrzˇavanja [24]. U prvom slucˇaju, preventivno odrzˇavanje se sprovodi, iskljucˇivo, na osnovu informacija o pouzdanosti, tj. na osnovu raspodele vremena rada do pojave otkaza za posma- trani sistem, odnosno njegov element. U drugom slucˇaju, posmatra se i prati neki pokazatelj, tj. parametar koji reprezentuje stanje posmatranog sistema. Obe ove vrste preventivnog odrzˇavanja mogu da se vezˇu za neki odredeni vremenski period ili za vremenski trenutak koji se ne odreduje unapred, vec´ se tokom rada sistema podesˇava, tj. adaptira konstatovanom sta- nju, odnosno informacijama o izabranim parametrima stanja koji se prikupljaju i analiziraju Sa stanoviˇsta karaktera postupaka odrzˇavanja, preventivno odrzˇavanje mozˇe biti realizovano kao: − osnovno odrzˇavanje − preventivne zamene − odrzˇavanje prema stanju U okvir osnovnog odrzˇavanja spadaju sve aktivnosti opsluzˇivanja, snabdevanja gorivom, ma- zivom, podmazivanje, kao i osnovni pregledi stanja pojedinih elemenata sistema. Preventivna zamena ukljucˇuje aktivnosti zamene ili opravke elemenata i to samo u slucˇaju ako se na taj nacˇin, sasvim izvesno, doprinosi povec´anju pouzdanosti, odnosno ako se time neposredno smanjuje verovatnoc´a pojave otkaza. Ideja kod odrzˇavanja prema stanju jeste preduzimati zamenu u optimalno vreme na osnovu stvarnog stanja opreme. Stvarno stanje se utvrduje dijagnosticˇkim pregledima, a da se prethodno ne mora vrsˇiti rastavljanje po principu otvori i izmeri. Prednosti ovakvog pristupa odrzˇavanju su: − jednostavnije planiranje odrzˇavanja − obezbeduje se vec´a pouzdanost sistema dok su nedostaci: − povec´ani trosˇkovi odrzˇavanja − manja iskoriˇsc´enost opreme (oprema ne mora biti raspolozˇiva u toku pojedinih aktiv- nosti odrzˇavanja) Savremeni sistemi odrzˇavanja obuhvataju i upravljanje odrzˇavanjem, tj. zasnovani su na automatizovanoj podrsˇci odrzˇavanju primenom racˇunara (Computer Integrated Maintenance Management). Dakle recˇ je o sistemu, pa c´emo u analizi sistema odrzˇavanja poc´i od pojma sistema. Sistem se, najopsˇtije definiˇse kao skup objekata (entiteta) i njihovih medjusobnih veza. Informacioni sistem je sistem u kome se veze izmedju objekata i veze sistema sa okolinom ostvaruju razmenom informacija. Osnovu svakog informacionog sistema cˇini baza podataka, koja se mozˇe definisati kao kolekcija medjusobno povezanih podataka koja modelira (reprezentuje) objekte, veze objekata i atribute objekata posmatranog realnog sistema. Na ovaj nacˇin informacioni sistem je model realnog sitema, a postupak projektovanja infor- macionog sistema se svodi na neku vrstu modeliranja realnog sistema. Rezultat faze projek- tovanja informacionog sistema su dva podmodela: 8 Uvod − model podataka − model procesa Model podataka obuhvata reprezentaciju objekata realnog sistema, njihovih atributa i nji- hovih medjusobnih veza. Dakle staticˇke karakteristike realnog sistema se opisuju modelom podataka. Sa druge strane dinamika realnog sistema se opisuje modelom procesa. Ovde c´emo se baviti samo modelom podataka. Model podataka obuhvata reprezentaciju koncepata realnog sistema, njihovih atributa i nji- hovih medjusobnih veza. Veoma je vazˇno da je model podataka dovoljno bogat da bi mogao, na relativno lak nacˇin prihvatiti i u sebe ukljucˇiti razlicˇite koncepte realnog sistema zajedno sa svojim atributima i medusobnim vezama. Ove zavisnosti se, u modelu podataka, mogu predstaviti bilo strukturom podataka, bilo skupom ogranicˇenja na vrednosti podataka. Pored toga, neophodno je definisati i skup operacija modela podataka, da bi se preko njih, u mode- lima procesa, mogla opisati i dinamika realnog sistema. Dakle model podataka ukljucˇuje tri osnovne komponente: 1) struktura podataka 2) ogranicˇenja 3) operacije Kvalitet modela podataka se meri time u kojoj meri su obuhvac´eni koncepti realnog sistema i jednostavnosˇc´u implementacije struktura podataka, ogranicˇenja i operacija na racˇunaru. Strukture podataka se mogu klasifikovati uz pomoc´ viˇse kriterijuma. Jedan od kriterijuma mozˇe biti karakteristika veze (relacije) medu podacima. U odnosu na ovaj kriterijum struk- tura podataka mozˇe biti [Mogin]: − linearna struktura podataka − nelinearna struktura podataka U slucˇaju linearne strukture podataka, skup podataka je linearno ureden. Drugim recˇima skup podataka formira niz, odnosno svaki podatak (sem dva istaknuta, koje zovemo prvi odnosno poslednji podatak) je povezan sa tacˇno dva podatka, koje zovemo prethodni odnosno naredni podatak. Podatak za koga ne postoji prethodni je prvi podatak, a podatak za koga ne postoji naredni je poslednji podatak. Strukture podataka u kojima skup podataka nije linearno ureden zovemo nelinearne strukture podataka. Prema tome koliki je broj podataka koji prethode datom podatku, odnosno koliki je broj podataka koji su naredni u u odnosu na dati podatak, nelinearne strukture podataka dalje mogu biti: − hijerarhijska struktura podataka − mrezˇna struktura podataka 9 Uvod Hijerarhijske strukture podataka ili (strukture tipa stablo) su takve strukture podataka u ko- jima za svaki podatak (sem istaknutog podatka koga zovemo koren hijerarhije) postoji tacˇno jedan podatak koji mu prethodi, pri tome mozˇe postojati nula ili viˇse podataka koji su u odnosu na njega naredni podaci. U slucˇaju hijerarhijske strukture podataka umesto termina prethodni odnosno naredni podatak koiste se termini nadredeni odnosno podredeni poda- tak. Koren hijerarhije nema nadredeni podatak. Nelinearne strukture podataka koje nisu hijerarhijske su mrezˇne strukture podataka. Hijerarhijske strukture podataka su posebno interesantne u sistemu odrzˇavanja vazduhoplova i one c´e biti predmet istrazˇivanja u ovom radu. Vazduhoplov je sistem visoke slozˇenosti, pojedine komponente vazduhoplova koriste na razlicˇit nacˇin, trpe razlicˇita opterec´enja i odrzˇavaju se po programu koji je njima najbolje prilagoden. Jedan od nacˇina savladavanja pomenute slozˇenosti je takozvana hijerarhijska de- kompozicija. Slozˇeni koncept se na jednom nivou apstrakcije posmatra kao jedinstvena celina. Na nizˇem nivou apstrakcije se posmatra kao koncept koji se sastoji od delova (komponenti). Uzastopnom primenom opisanog postupka dobija se takozvana hijerarhijska sastavnica. Da- kle jedan od bitnih koncepata u sistemu odrzˇavanja vazduhoplova jeste sastavnica. U si- stemu odrzˇavanja se koriste termini sklop, podsklop nadsklop koji istovremeno oznacˇavaju i uzajamni odnos u datoj hijerarhiji. Dakle u sistemu za upravljanje odrzˇavanjem imac´emo sastavnice sklopova koje se dobijaju hijerarhijskom dekompozicijom elemenata sistema nad kojima se izvode akcije odrzˇavanja. Koliko je ovaj koncept vazˇan govori i cˇinjenica da su se prve hijerarhijske baze podataka sˇezdesetih godina prosˇlog veka razvijene kako bi se direktno podrzˇale sastavnice u prizvod- nim organizacijama. Dakle model podataka informacionog sistema koji bi bio podrsˇka sistemu odrzˇavanja mora obezbediti efikasnu implementaciju hijerarhijske strukture podataka i ope- racija nad hijerarhijskim strukturama podataka. Obicˇno se hijerarhijske strukture podataka implementiraju rekurzivnim strukturama koje dalje namec´u obradu rekurzivnim procedu- rama, a poznato je da rekurzivna resˇenja mogu znacˇajno degradirati performanse sistema. Problemi vezani za implementaciju hijerarhijskih struktura podataka i neka resˇenja bic´e iz- neta u Glavi 2. U delu planiranja odrzˇavanja, jedan od osnovnih problema izmedu ostalog je neizvesnost dogadaja koji znacˇajno uticˇu na efikasnost odrzˇavanja. Recˇ je o dogadajima koji su po svojoj prirodi slucˇajni. Ovi slucˇajni dogadaji su pored ostalog vezani za: − vremenski trenutak otkaza rezervnog dela − vremenski trenutak zahteva za nekim delom − vreme isporuke, odnosno vreme potrebno za sklapanje (pripremu) rezervnog dela Posebno, podrazumevalo se da je vreme isporuke odnosno vreme potrebno za pripremu re- zervnog dela nula (rezervni deo je neposredno dostupan), a to je pretpostavka neogranicˇenih resursa sˇto je uglavnom redak slucˇaj. Kako mnogo faktora uticˇe na ovo vreme, ono po pra- vilu uvek ima neko slucˇajano odstupanje. Za neke analize vreme isporuke odnosno vreme sklapanja rezervnog dela se mozˇe ignorisati, ali u analizi kompletnog sitema odrzˇavanja ova odstupanja bitno degradiraju performanse sistema. Pod vremenom isporuke (lead time) za dati rezervni deo se podrazumeva: 10 Uvod − vreme koje je potrebno da bi se rezervni deo dopremio iz nekog spoljnjeg izvora − vreme koje je potrebno da bi se rezervni deo sklopio prema utvrdenoj proceduri skla- panja − vreme da bi se poluproizvod obradio do nivoa gotovog rezervnog dela Na ovo vreme uticˇe mnosˇtvo faktora. Neki od faktora su − problemi u transportu − kvar na masˇinama − problemi vezani za kvalitet Ovi faktori su po svojoj prirodi slucˇajne velicˇine, pa je i ovo vreme isporuke po pravilu slu- cajna velicˇina. Jedan od pristupa kojim se mozˇe umanjiti uticaj ovih slucˇajnih velicˇina je skladiˇstenje gotovih rezervnih delova, odnosno odrzˇavanje zaliha gotovih rezervnih delova. U slucˇaju da je ovaj nivo iznad odgovarajuc´eg javic´e se nepotrebni trosˇkovi skladiˇstenja. Sa druge strane ako je nivo zaliha ispod odgovarajuc´eg nivoa javic´e se trosˇkovi kasˇnjenja. Cilj je odrzˇavati nivo zaliha kojim se obezbeduju minimalni trosˇkovi skladiˇstenja sa jedne strane a pri tome se garantuje visok nivo raspolozˇivosti gotovih delova kako bi se minimizovali trosˇkovi kasˇnjenja. Za uspesˇno resˇavanje ovog problema neophodno je razviti odgovarajuc´e matematicˇke modele koji c´e na odgovarajuc´i nacˇin tretirati neizvesnost pojedinih faktora u sistemu odrzˇavanja. Posebno problem odredivanja nivoa zaliha rezervnih delova u kon- tekstu slucˇajnog broja zahteva za rezervnim delovima je problem koji je najviˇse izucˇavan i analiziran. Kako je narucˇivanje i prodaja dnevnih novina ilustrativna metafora za ovaj tip problema, za probleme ovog tipa koristi se termin newsboy problem, a za odgovarajuc´i model se koristi termin newsboy model . Newsboy problemi nisu samo problemi iz oblasti upravljanja zalihama, oni se javljaju u svim situacijama kada treba izvrsˇiti ocenu neke slucˇajne promen- ljive, a ta ocena je rezultat kompromisa izmedu gubitaka u slucˇaju da je vrednost slucˇajne promenljive precenjena i gubitaka koji su posledica potcenjene vrednosti slucˇajne promen- ljive. Posebno ovaj problem se mozˇe iskoristiti u situacijama kada treba odrediti optimalni vremenski trenutak kada treba zapocˇeti neku aktivnost odrzˇavanja. U planiranju odrzˇavanja cˇesta je sledec´a situacija. Neki skup aktivnosti odrzˇavanja ima hijerarhijsku strukturu i pri tome je trajanje svake aktivnosti slucˇajna velicˇina. Pod pretpo- stavkom da aktivnost na viˇsem nivou hijerarhije ne mozˇe zapocˇeti pre nego sˇto su zavrsˇene sve aktivnosti na nizˇem nivou hijerarhije i da su poznati gubici koji nastaju u slucˇaju da se sa nekim aktivnostima kasni, odnosno da su poznati gubici u slucˇaju da su neke aktivnosti preuranjene, potrebno je formirati optimalnu strategiju aktiviranja aktivnosti iz datog skupa. Upravo to c´e biti predmet istrazˇivanja u Glavi 3. Primetili smo da je jedan od bitnih koncepata u sistemu odrzˇavanja vazduhoplova sastav- nica. Sastavnica je najprostije recˇeno, lista komponenti koji su sastavni delovi posmatranog objekta. Pri tome se vodi racˇuna o vezama izmedu sastavnih komponenti. Sastavnica dakle daje strukturu posmatranog objekta, josˇ viˇse sastavnica je opis hijerarhijske strukture tog 11 Uvod objekta. Prema tome da li se sastavnica koristi u projektovanju, proizvodnji ili odrzˇavanju, sastavnica mozˇe biti: − inzˇenjerska sastavnica − proizvodna sastavnica − servisna sastavnica i u tom smislu c´e biti prilagoden sadrzˇaj kojim c´e biti snabdevene. Posebno sastavnice koje c´e se koristiti u sistemu odrzˇavanja c´e izmedu ostalog ukljucˇivati i sledec´e podatke: − kolicˇina pojedinih podsklopova koja je neophodna za sklapanje finalnog sklopa − vremena neophodna za ugradnju pojedinih podsklopova u procesu sklapanja finalnog sklopa − redosled ugradnje pojedinih podsklopova u procesu sklapanja finalnog sklopa Kvalitetan sistem za upravljanje odrzˇavanjem vazduhoplova mora obezbediti sadrzˇajno kva- litetne sastavnice i to c´e biti predmet istrazˇivanja u Glavama 4 i 5. 12 Glava 2 Hijerarhijske strukture podataka 2.1 Uvodna razmatranja Pod strukturom podataka podrazumeva se skup medusobno povezanih podataka. Strukture podataka se mogu klasifikovati na osnovu viˇse kriterijuma. Jedan od kriterijuma mozˇe biti ka- rakteristika veze (relacije) medu podacima. U odnosu na ovaj kriterijum struktura podataka mozˇe biti [14]: − linearna struktura podataka − nelinearna struktura podataka U slucˇaju linearne strukture podataka, skup podataka je linearno ureden. Drugim recˇima skup podataka formira niz, odnosno svaki podatak (sem dva istaknuta, koje zovemo prvi odnosno poslednji podatak) je povezan sa tacˇno dva podatka, koje zovemo prethodni odnosno naredni podatak. Podatak za koga ne postoji prethodni je prvi podatak, a podatak za koga ne postoji naredni je poslednji podatak. Strukture podataka u kojima skup podataka nije linearno ureden zovemo nelinearne strukture podataka. Prema tome koliki je broj podataka koji prethode datom podatku, odnosno koliki je broj podataka koji su naredni u u odnosu na dati, podatak nelinearne strukture podataka dalje mogu biti: − hijerarhijska struktura podataka − mrezˇna struktura podataka Hijerarhijske strukture podataka ili (strukture podataka tipa stablo) su takve strukture po- dataka u kojima za svaki podatak (sem istaknutog podatka koga zovemo koren hijerarhije) postoji tacˇno jedan podatak koji mu prethodi, pri tome mozˇe postojati nula ili viˇse podataka koji su u odnosu na njega naredni podaci. U slucˇaju hijerarhijske strukture podataka umesto termina prethodni odnosno naredni podatak koiste se termini nadredeni odnosno podredeni podatak. Koren hijerarhije nema nadredeni podatak. Nelinearne strukture podataka koje nisu hijerarhijske su mrezˇne strukture podataka. U daljem tekstu cˇemo se detaljnije baviti hijerarhijskom strukturom podataka odnosno strukturom podataka tipa stablo. Kao sˇto sam naziv kazˇe u osnovi hijerarhijske strukture podataka je stablo. 13 Hijerarhijske strukture podataka Uvodna razmatranja Engleski matematicˇar Kejli je 1857. godine uveo pojam stabla [27]. Koncept stabla je koriˇsc´en i ranije, ali Kejli je bio prvi koji je iskoristio ovaj pojam u pisanom radu. Skoro u isto vreme (oko 1859.) otkrivene su strukturne formule hemijskih jedinjenja. Kejli je nasˇao vezu izmedu ova dva pojma (povezao je stabla i strukturne formule alkana - jedinjenja formule CnH2n+2) i u radu O matematicˇkoj teoriji izomera iz 1874. godine je postavio kamen temeljac naucˇne discipline Hemijske teorije grafova. Kejli je pokusˇao da pronade broj izomera In alkana CnH2n+2, nije uspeo u tome, ali je dao nekoliko vazˇnih rezultata vezanih za prebrojavanje stabala. Sa druge strane Fizicˇar Kirhof je resˇavajuc´i problem izracˇunavanja jacˇina elektricˇnih struja u granama nekog elektricˇnog kola, dosˇao do znacˇajnih rezultata vezanih za stabla. Sˇto se ticˇe racˇunarskih nauka, stablo takode ima veoma znacˇajnu ulogu, izmedu ostalog koristi se na sledec´i nacˇin: − algoritmi pretrage koriste stabla (binarno stablo pretrage) za uredivanje podataka − kompajleri koriste stabla (stablo izraza) za reprezentaciju aritmeticˇkih izraza − algoritmi za kompresiju podataka koriste stabla (stablo kodiranja) − operativni sistemi koriste hijerarhijsku strukturu datotecˇnog sistema U ovom radu stablo c´emo koristiti za reprezentaciju hijerarhijske strukture podataka. Iz ocˇiglednih razloga (ogranicˇeni resursi) bavic´emo se samo konacˇnim stablima. Postavlja se sledec´i zahtev. Obezbediti takvu implementaciju stabla koja pruzˇa moguc´nost efikasne obrade hijerarhijske strukture podataka. Najcˇesˇc´e se hijerarhijske strukture podataka implementi- raju rekurzivnim strukturama koje dalje namec´u rekurzivnu implementaciju operacija nad ovim strukturama podataka. Rekurzivna resˇenja su sa jedne strane jednostavna i efektna, ali sa druge strane mogu znacˇajno degradirati performanse sistema. U potrazi za alternativnim resˇenjima bic´e neophodna detaljnija analiza samog pojma stabla. Ako se stablo uvede rekur- zivnom definicijom sˇto je najcˇesˇc´i slucˇaj u racˇunarskim naukama, onda se prirodno namec´u rekurzivna resˇenja kako implementacije tako i procedura za njihovu obradu. U teoriji skupova se stablo uvodi kao klasa parcijalno uredenih skupova. Ako zanemarimo sˇta su elementi tih skupova, problem se svodi na problem implementacije binarne relacije (parcijalnog uredenja), a ovo se standardno resˇava takozvanom matricom susedstva. Za neka nova resˇenja problema implementacije stabla, neophodne su neke nove karakterizacije konacˇnog stabla. Dalje se iz izvedenih karakterizacija konacˇnog stabla mogu izvuc´i modeli implementacije stabla (hijerar- hijske strukture podataka) [5] [7] − model sa listom susedstva − model sa izlistanim putanjama − model sa ugnjezˇdenim skupovima i njihovi varijeteti: − model sa tranzitivnim zatvorenjem − Dewey-jeva decimalna notacija − model sa ugnjezˇdenim intervalima 14 Hijerarhijske strukture podataka Stablo 2.2 Stablo 2.2.1 Rekurzivna definicija stabla Najcˇesˇc´e koriˇsc´ena definicija stabla je [11]: Definicija 2.2.1. Stablo T je neprazan skup cˇvorova T takav da vazˇi: a) postoji tacˇno jedan istaknuti cˇvor u T koga zovemo koren stabla T i oznacˇavamo sa root (T ); b) preostali cˇvorovi su elementi disjunktnih skupova T1, T2, . . . , Tm, m ≥ 0 i svaki od ovih skupova je stablo.  Primer stabla sa najvazˇnijim elementima dat je na slici (2.1). A B E F J G C D H K L I Koren stabla u cˇvoru A Podstablo sa korenom u cˇvoru B Preci cˇvora H Cˇvor grane H Potomci cˇvora H 1 Nivo cˇvora 2 List I 3 4 Slika 2.1: Stablo sa najvazˇnijim elementima Stabla T1, T2, . . . , Tm zovemo podstablima korena stabla T . Iz definicije (2.2.1) sledi da je svaki cˇvor koren nekog podstabla polaznog stabla T . Broj podstabala nekog cˇvora zovemo stepen cˇvora. Cˇvor stepena nula zovemo terminalni cˇvor ili list , inacˇe je neterminalni cˇvor ili cˇvor grane. Nivo cˇvora u stablu T se definiˇse na sledec´i nacˇin: 15 Hijerarhijske strukture podataka Stablo Definicija 2.2.2. Neka je T stablo, tada: a) root (T ) ima nivo jedan; b) cˇvor koji nije koren stabla T ima nivo koji je za jedan vec´i od nivoa koga ima u podstablu Tj , j ∈ {1, 2, . . . ,m} u kome se nalazi.  Visina stabla je maksimalni nivo na kome se neki cˇvor nalazi. Ako postoji uredenje podsta- bala T1, T2, . . . , Tm, onda kazˇemo da je stablo T uredeno . Za korene podstabala T1, T2, . . . , Tm kazˇemo da su potomci korena stabla T , odnosno koren stabla T je predak korena njegovih pod- stabala T1, T2, . . . , Tm. Svaki cˇvor ima najviˇse jednog pretka, a nula ili viˇse potomaka. Stablo T je binarno stablo, ako je svaki cˇvor koren najviˇse dva podstabla koje zovemo levo, odnosno desno podstablo i oznacˇavamo sa left(T ), right(T ) respektivno. Sˇuma je skup (obicˇno ureden skup) skup disjunktnih stabala. Svaka sˇuma stabala se na prirodan nacˇin mozˇe reprezentovati binarnim stablom [11]. Definicija 2.2.3. Neka je F = (T1, T2, . . . , Tn) sˇuma stabala i neka su T11, T12, . . . , T1m podstabla korena krajnjeg levog podstabla T1. Binarno stablo B(F) odredeno sa: − ako je n = 0, B = ∅ − ako je n > 0, · root(B(F)) = root(T1) · left(B(F)) = B(T11, T12, . . . , T1m) · right(B(F)) = B(T2, T3, . . . , Tn) je binarno stablo koje odgovara sˇumi stabala F  Susˇtina navedene reprezentacije (2.2): A • / B C D • • / • • / E F G H I / • • • / / • • / / J K L / / / • / / Slika 2.2: Implementacija stabla sa slike (2.1) 16 Hijerarhijske strukture podataka Stablo je sledec´a: − koren levog podstabla je krajnji levi potomak - first child − koren desnog podstabla je sledec´i potomak nadredenog cˇvora - next sibling. Rekurzivna definicija (2.2.1) prirodno namec´e kako implementaciju rekurzivnim strukturama (2.1): Algoritam 2.1 Rekurzivna struktura podataka typedef type_of_data_in_the_node info_t; struct node { info_t info; struct node* first_child; struct node* next_sibling; }; typedef node *nodep; tako i obradu rekurzivnim procedurama. Procedure za obilazˇenje cˇvorova stabla u odgova- rajuc´em redosledu su posebno znacˇajne. Kako se radi o obradi rekurzivne strukture podataka, odgovarajuc´a rekurzivna resˇenja su jednostavna i efektna. Jedna od standardnih procedura za pre-order obilazˇenje stabla i njena rekurzivna verzija je sledec´eg oblika (2.2): Algoritam 2.2 Rekurzivna obrada preorder(nodep rt) { nodep temp output(Info(rt)) temp = firstChild(rt) while(temp is not NULL) { preorder(temp) temp = nextSibling(temp) } } U pre-order obilasku stabla [11], prvo se obilazi cˇvor, a zatim njegovi potomci od krajnjeg levog do krajnjeg desnog. U slucˇaju stabla sa slike (2.1), rezultat pre-order obilaska je (2.3). Rekurzivnost strukture podataka i procedura za njihovu obradu ne moraju biti direktno podrzˇani modelom podataka u kome se ove strukture i pripadajuc´e procedure implementiraju. 17 Hijerarhijske strukture podataka Stablo A B E F J G C D H K L I ABEFJGCDHKLI Slika 2.3: Pre-Order obilazak stabla sa slike (2.1) Nivo ozbiljnosti ovog ogranicˇenja, josˇ je vec´i ako se zna da rekurzivna resˇenja mogu znacˇajno degradirati performanse sistema. Sva ova ogranicˇenja opravdavaju istrazˇivanja modela koja proisticˇu iz nerekurzivnih karakterizacija stabla. 2.2.2 Nerekurzivna definicija stabla Stablo je skup cˇvorova na kome je definisana binarna relacija predak. Kako je relacija predak relacija poretka, poc´i c´emo od parcijalno uredenih skupova [13]. Definicija 2.2.4. Neka je ≤ relacija poretka na skupu P. Ureden par (P,≤) zovemo parcijalno ureden skup.  Standardni primeri parcijalno uredenih skupova su: − (P (T ) ,⊆) gde je T proizvoljan skup, P (T ) partitivni skup skupa T i ⊆ relacija podskup. Josˇ viˇse proizvoljna kolekcija X podskupova skupa T je parcijalno ureden skup ako se uredi relacijom podskup (nadskup) − proizvoljan skup recˇi nad datom azbukom A koji sadrzˇi praznu recˇ, je parcijalno ureden skup ako se uredi relacijom prefiks (sufiks, infiks) Uredenje ≤ na skupu P je linearno ili totalno uredenje ako pored uslova koji definiˇsu uredenje ispunjava i uslov linearnosti: p, q ∈ P ⇒ p ≤ q ∨ q ≤ p (2.1) 18 Hijerarhijske strukture podataka Stablo U tom slucˇaju par (P,≤) se naziva linearno ureden skup, totalno ureden skup ili lanac. To znacˇi da je parcijalno ureden skup linearno ureden ako su svaka dva njegova elementa uporediva. Neka je (P,≤) parcijalno ureden skup, tada: − za element p ∈ P kazˇemo da je minimalan ako je: (¬∃q ∈ P ) q 6= p ∧ q ≤ p (2.2) odnosno p je minimalan ako u P ne postoji strogo manji element od njega. Slicˇno se uvodi maksimalni element parcijalno uredenog skupa. − za element p ∈ P kazˇemo da je najmanji ako vazˇi: q ∈ P ⇒ p ≤ q (2.3) odnosno p je najmanji element u P ako je manji od svakog drugog elementa iz P . Slicˇno se uvodi najvec´i element parcijalno uredenog skupa. Ukoliko parcijalno ureden skup (P,≤) ima najmanji element tada je on jedinstven. Uredeni skup mozˇe imati viˇse minimalnih elemenata i tada ne mozˇe imati najmanji element. Za parcijalno ureden skup (P,≤) kazˇemo da je dobro ureden ako je linearno ureden i svaki njegov neprazan podskup ima najmanji elemenat. Ocˇigledno je svaki konacˇan linearno ureden skup dobro ureden. Sada mozˇemo dati sledec´u definiciju stabla [13]: Definicija 2.2.5. Stablo T je parcijalno uredenje (T,≤) koje ima najmanji element i pri tome je: (∀x ∈ T ) ↑ (x) = {y ∈ T |y ≤ x} (2.4) skup ↑ (x) dobro ureden relacijom ≤.  Od interesa su nam konacˇna stabla, odnosno konacˇni parcijalno uredeni skupovi T , sa naj- manjim elementom takvim da je za svako x ∈ T , ↑ (x) linearno ureden skup odnosno lanac. Najmanji element stabla je koren, a maksimalne elemente zovemo listovima. Visina stabla je odredena najduzˇim lancem: H = max x∈T {| ↑ (x)|} (2.5) 19 Hijerarhijske strukture podataka Modeli stabla 2.3 Modeli stabla 2.3.1 Model sa listom susedstva Kako svaki cˇvor stabla sem korena ima jedinstvenog direktnog pretka (mozˇemo rec´i da je koren predak samom sebi) onda na skupu cˇvorova stabla postoji preslikavanje (direktni predak) sa tacˇno jednom fiksnom tacˇkom. Ova osobina namec´e prvu karakterizaciju stabla i data je sledec´om teoremom: Teorema 2.3.1. Konacˇan skup T na kome je definisana funkcija f : T → T sa osobinama: a) postoji tacˇno jedna fiksna tacˇka r funkcije f , (∃1r ∈ T ) f (r) = r (2.6) b) za svako n ∈ N (¬∃x ∈ T )x 6= r ∧ fn (x) = x (2.7) je konacˇno stablo. Dokaz. Definiˇsimo relaciju ≤ na T na sledec´i nacˇin: (x, y ∈ T ) y ≤ x⇔ (∃k ∈ N0) y = fk (x) (2.8) pri cˇemu je f0 = IT identicˇko preslikavanje skupa T . Ocˇigledno je ≤ relacija poretka. Neka je n ∈ N, oznacˇimo sa: Fn (x) = { fk(x)|k ∈ N0 ∧ k < n } (2.9) Kako je T konacˇan skup svakom x ∈ T mozˇemo pridruzˇiti: nx = min {n ∈ N|fn(x) ∈ Fn (x)} (2.10) Mora biti fnx (x) = r, jer u suprotnom fnx (x) = u ∈ Fnx (x)⇒ fnx (x) = fk(x) (2.11) za neko k < nx, odnosno fnx−k (u) = fnx−k ( fk (x) ) = fk (x) = u (2.12) sˇto je kontradikcija sa pretpostavkom o funkciji f , dakle fnx(x) = r odnosno r je najmanji element. Ocˇigledno je: ↑ (x) = {y ∈ T |y ≤ x} = { fk (x) |k < nx } = Fnx (x) (2.13) linearno ureden skup pri tome konacˇan, dakle dobro ureden skup.  20 Hijerarhijske strukture podataka Modeli stabla Neka je (T,≤) konacˇno stablo sa korenom r, funkcija (direktni predak) f iz navedene karak- terizacije konacˇnog stabla je: f(x) = r , x = rmax {y|y x} , x 6= r (2.14) Iz navedene karakterizacije stabla izvodi se i najcˇesˇc´e koriˇsc´eni model [5]. Za svaki cˇvor x belezˇi se njegov jedinstveni direktni predak y = f(x), odnosno belezˇe se grane stabla. Kako je koren stabla predak samom sebi, odnosno jedini cˇvor koji nema drugog pretka, sem samog sebe, odgovarajuc´a grana se obicˇno izostavlja iz modela. Ovo je takozvani model sa listom susedstva (adjacency list model) (2.1). Tabela 2.1: Lista susedstva stabla sa slike (2.3) cˇvor roditelj B A C A D A E B F B G B H D I D J F K H L H Ocˇigledno je da se u ovom modelu mogu efikasno: − dodavati novi cˇvorovi - funkcija direktni predak je rasˇirenje postojec´e funkcije − brisati cˇvorovi - funkcija direktni predak je suzˇenje postojec´e funkcije Nedostatak ovog modela je neefikasno generisanje podstabla sa korenom u datom cˇvoru. Ne- efikasnost je posledica cˇinjenice da se odnos predak/potomak ne mozˇe neposredno ustanoviti u opsˇtem slucˇaju. Neposredno se mozˇe ustanoviti odnos izmedu cˇvora i njegovih direktnih potomaka. U opsˇtem slucˇaju ovaj odnos se proverava na sledec´i nacˇin: − cˇvor je potomak datog cˇvora ako je: · njegov direktni potomak, ili je · potomak njegovog direktnog potomka; − cˇvor je predak datog cˇvora ako je: · njegov direktni predak, ili je · predak njegovog direktnog pretka. 21 Hijerarhijske strukture podataka Modeli stabla i zato se ovaj model naziva rekurzivni model . Kako se odnos neposredno proverava samo ako su cˇvorovi na uzastopnim nivoima stabla, odnos izmedu cˇvorova koji nisu na uzastopnim nivoima se proverava izracˇunavanjem fk, k = 1, 2, . . .. 2.3.2 Model sa tranzitivnim zatvorenjem Jedno poboljˇsanje modela sa listom susedstva se sastoji u sledec´em [Celko]. Umesto funkcije direktni predak belezˇi se njeno refleksivno i tranzitivno zatvorenje. Problem tranzitivnog zatvorenja je poseban problem koji se ovde nec´e detaljno obradivati. Na ovaj nacˇin se iz funkcije direktni f predak reprodukuje kompletna relacija poretka ≤: ≤= ∪ k∈N0 fk (2.15) gde je: ≤= {(y, x)|(x, y ∈ T )y ≤ x} (2.16) fk = { (y, x)|(x, y ∈ T )y = fk(x) } (2.17) U ovom modelu za svaki cˇvor x belezˇe se svi njegovi prethodnici y = fk (x) , k = 1, 2, ..., odnosno belezˇi se niz grana od cˇvora do korena. Ovo je takozvani model sa tranzitivnim zatvorenjem (transitive closure model) (2.2). Tabela 2.2: Tranzitivno zatvorenje liste susedstva (2.1) cˇvor predak A A G A K A B A G B K D B B G G K H C A H A K K C C H D L A D A H H L D D D I A L H E A I D L L E B I I E E J A F A J B F B J F F F J J Na ovaj nacˇin se efikasno mozˇe testirati odnos izmedu bilo koja dva cˇvora. Ako se sa svakim zapisom (y, x) gde je y ≤ x odnosno y = fk (x) za neko k ∈ N, belezˇi i k, koje predstavlja nivo cˇvora1 x u podstablu sa korenom u cˇvoru y, odnosno duzˇina jedinstvene putanje od cˇvora x do cˇvora y, neposredno je dostupan i lanac prethodnika cˇvora x (2.3). 1Preciznije nivo cˇvora je k + 1 22 Hijerarhijske strukture podataka Modeli stabla Tabela 2.3: Uredenje na tranzitivnom zatvorenju (2.2) cˇvor predak nivo A A 1 G A 3 K A 4 B A 2 G B 2 K D 3 B B 1 G G 1 K H 2 C A 2 H A 3 K K 1 C C 1 H D 2 L A 4 D A 2 H H 1 L D 3 D D 1 I A 3 L H 2 E A 3 I D 2 L L 1 E B 2 I I 1 E E 1 J A 4 F A 3 J B 3 F B 2 J F 2 F F 1 J J 1 Nedostatak ovog modela je sˇto za razliku od modela sa listom susedstva kojim se stablo sa n cˇvorova reprezentuje sa n − 1 zapisa, broj zapisa u ovom modelu je reda n · h gde je h prosecˇan nivo cˇvora u stablu. Pored ovog nedostatka ocˇigledni su problemi: − dodavanja novog cˇvora − brisanja postojec´eg cˇvora 2.3.3 Efikasnost modela Razmotrimo sada (neformalno) pitanje efikasnosti modela implementacije stabla, pri cˇemu c´emo efikasnost modela meriti efikasnosˇc´u standardnih procedura za njihovu obradu. Efika- snost ispitivanja odnosa, odnosno izracˇunavanja vrednosti izraza y ≤ x na cˇvorovima stabla (T,≤) je svakako posebno vazˇna. U modelu sa listom susedstva testiranje odnosa izmedu cˇvorova se u opsˇtem slucˇaju svodi na rekurzivnu proveru postojanja niza zapisa: (y, u1), (u1, u2), . . . (un−1, un), (un, x) sˇto je ocˇigledno neefikasno. U modelu sa tranzitivnim zatvorenjem testiranje odnosa izmedu cˇvorova se svodi na efikasniju proveru postojanja odgovarajuc´eg zapisa (y, x), ali je nedosta- tak sˇto broj zapisa mozˇe ic´i do reda n2 u slucˇaju da je stablo sa n cˇvorova lanac (prostor pretrage mozˇe biti znacˇajno veliki). Problem efikasnog izracˇunavanja vrednosti izraza y ≤ x na cˇvorovima stabla (T,≤) se mozˇe resˇiti na sledec´i nacˇin. Uocˇi se neki parcijalno ureden skup X, takav da se odnos izmedu njegovih elemenata mozˇe efikasno utvrditi. Elemente skupa X c´emo zvati obelezˇja. Zatim se konstruiˇse izomorfizam ϕ skupa cˇvorova T datog stabla na skup ϕ (T ) ⊆ X. Na ovaj nacˇin se slozˇena provera odnosa dva cˇvora x, y ∈ T svodi na efikasnu proveru odnosa dva obelezˇja: ϕ (x) , ϕ (y) ∈ f (T ) ⊆ X 23 Hijerarhijske strukture podataka Modeli stabla U modelima koji slede nec´e biti potrebno da se belezˇe grane, niti putanje od cˇvora do korena stabla kao sˇto je to bio slucˇaj u prethodna dva modela, vec´ c´e se samo belezˇiti obelezˇja cˇvorova stabla. Na ovaj nacˇin c´e se u modelima koji slede efikasno: − dodavati novi cˇvorovi − brisati postojec´i cˇvorovi Dakle stablo c´e uvek biti reprezentovano sa brojem zapisa koji je jednak broju cˇvorova stabla. Posebno, svakom cˇvoru x ∈ T mozˇemo pridruzˇiti obelezˇje koje je skup njegovih predaka ↑ (x) i umesto stabla (T,≤) posmatrac´emo strukturu (↑ T,≤↑) gde je: ↑ T = {↑ (x)|x ∈ T} , (2.18) i pri tome je ≤↑ pogodno izabrana relacija na ↑ T tako da su (T,≤) i (↑ T,≤↑) izomorfne strukture. U tom slucˇaju, odnos izmedu cˇvorova x, y ∈ T mozˇemo efikasno testirati na pridruzˇenim obelezˇjima ↑ (x), ↑ (y) jer vazˇi: y ≤ x⇔↑ (y) ≤↑↑ (x) (2.19) Slicˇno, svakom cˇvoru x ∈ T mozˇemo pridruzˇiti obelezˇje koje je skup njegovih potomaka ↓ (x) i umesto stabla (T,≤) mozˇemo posmatrati strukturu (↓ T,≤↓) gde je: ↓ T = {↓ (x)|x ∈ T} (2.20) i pri tome je ≤↓ pogodno izabrana relacija na ↓ T tako da su (T,≤) i (↓ T,≤↓) izomorfne strukture. U tom slucˇaju, odnos izmedu cˇvorova x, y ∈ T mozˇemo testirati na pridruzˇenim obelezˇjima ↓ (x), ↓ (y) jer vazˇi: y ≤ x⇔↓ (y) ≤↓↓ (x) (2.21) Za efikasnu implementaciju predlozˇene metodologije neophodne su nam pogodnije karakteri- zacije stabla. 2.3.4 Model sa izlistanim putanjama Za karakterizaciju konacˇnog stabla koja sledi, neophodne su sledec´e definicije. Definicija 2.3.1. Neka je T konacˇan skup i neka je C kolekcija podskupova od T . C je ⊆-hijerarhija na skupu T ako vazˇi: a) T = ⋃ {C|C ∈ C} = ⋃ C b) U, V ∈ C ⇒ U ∩ V ∈ C c) U, V,W ∈ C ∧ U, V ⊆W ⇒ U ⊆ V ∨ V ⊆ U  24 Hijerarhijske strukture podataka Modeli stabla Definicija 2.3.2. ⊆-hijerarhija C na skupu T je T⊆-hijerarhija na skupu T ako vazˇi: a) za sve x, y ∈ T , x 6= y, postoji U ∈ C tako da tacˇno jedan od x, y pripada U b) unija kolekcije elementa hijerarhije C je elemenat hijerarhije C akko je jednaka nekom cˇlanu kolekcije  Definicija 2.3.3. ⊆-hijerarhija C na skupu T je povezana ⊆-hijerarhija na skupu T ako vazˇi: − postoji istaknuti element r ∈ T takav da vazˇi U ∈ C ⇒ r ∈ U .  Sada mozˇemo dati sledec´u karakterizaciju konacˇnog stabla. Teorema 2.3.2. Povezana T⊆-hijerarhija C na konacˇnom skupu T je konacˇno stablo. Dokaz. Neka je C povezana T⊆-hijerarhija na konacˇnom skupu T . Primetimo da {r} mora biti elemenat povezane T⊆-hijerarhije C, gde je r istaknuti element skupa T . Neka to nije slucˇaj i neka je U ∈ C skup sa najmanjim brojem elemenata (ili jedan od njih). Kako je C povezana ⊆-hijerarhija mora biti r ∈ U , odnosno U = {r, x1, x2, . . . , xk} , k ≥ 1. C je T⊆-hijerarhija i r 6= x1 pa postoji V ∈ C takav da tacˇno jedan od r, x1 pripada V , to svakako mora biti r jer je C povezana ⊆-hijerarhija dakle x1 /∈ V . Uocˇimo skup U ∩ V ∈ C koji je pravi podskup skupa U , sˇto je suprotno pretpostavci o skupu U . Dakle {r} ∈ C. Sada mozˇemo definisati funkciju (relaciju) direktni predak f : C → C na sledec´i nacˇin: f(U) = {r} U = {r}⋃ CU U 6= {r} (2.22) gde je CU = {V ∈ C|V U}. Neka je U 6= {r} elemenat povezane T⊆-hijerarhije C na skupu T , pokazac´emo da mora biti f(U) ( U . Kolekcija CU je neprazna jer {r} ∈ CU , dalje kako su svi elementi kolekcije CU podskupovi od U ∈ C i pri tome je C konacˇna ⊆-hijerarhija, postoji V0 ∈ CU takav da za svako V ∈ CU vazˇi Vi ⊆ V0, odnosno postoji V0 ∈ CU tako da vazˇi V0 = ⋃ CU = f(U). Kako V0 ∈ CU zakljucˇujemo f(U) = V0 ( U . Josˇ viˇse, neka je U 6= {r} elemenat povezane T⊆-hijerarhije C na skupu T tada vazˇi: fk(U) ( U za sve k ∈ N . Iz prethodnog mozˇemo zakljucˇiti da funkcija f ima tacˇno jednu fiksnu tacˇku {r} i pri tome fk k = 2, 3, . . . nema drugih fiksnih tacˇaka sem tacˇke {r}, pa je na osnovu teoreme (2.3.1) povezana T⊆-hijerarhija na konacˇnom skupu T stablo.  Funkcija f iz prethodne teoreme, definisana na povezanoj T⊆-hijerarhiji C na konacˇnom skupu T , ima sledec´u osobinu. Neka su U, V ∈ C i k ∈ N0, tada vazˇi: V = fk(U)⇔ V ⊆ U (2.23) 25 Hijerarhijske strukture podataka Modeli stabla odnosno relacija podskup ⊆ na C je refleksivno i tranzitivno zatvorenje ovako definisane funkcije (relacije) direktni predak f . ⊆= ∪ k∈N0 fk (2.24) gde je: ⊆= {(V,U)|(U, V ∈ C)V ⊆ U} (2.25) fk = { (V,U)|(V,U ∈ C)V = fk(U) } (2.26) Drugim recˇima povezana T⊆-hijerarhija na konacˇnom skupu T je stablo ako se uredi relacijom podskup. Neka je (T,≤) konacˇno stablo, pokazˇimo da se mozˇe konstruisati povezana T⊆-hijerarhija C na skupu T . Pre svega primetimo da c´e u ovoj karakterizaciji svakom cˇvoru x ∈ T odgovarati skup njegovih predaka, odnosno skup cˇvorova kojima je on potomak. U tom smislu definiˇsimo preslikavanje ↑: T → P (A) na sledec´i nacˇin: ↑ (x) = {z ∈ T |z ≤ x} (2.27) gde je P (A) partitivni skup skupa cˇvorova T . Sada nije tesˇko pokazati sledec´i stav. Teorema 2.3.3. Neka je (T,≤) konacˇno stablo. Kolekcija C = {↑ (x)|x ∈ T} =↑ T (2.28) je povezana T⊆-hijerarhija na skupu T . Dokaz. Dokazˇimo prvo da je C ⊆-hijerarhija. Primetimo x ∈↑ (x) za sve x ∈ T pa je T = ⋃ {↑ (x)|x ∈ T} = ⋃ C. Neka su U, V ∈ C, tada je U =↑ (x), V =↑ (y), za neke x, y ∈ T . Kako je U ∩ V ⊆ U =↑ (x) i pri tome je ↑ (x) konacˇan linearno ureden skup pa postoji z ∈ U ∩V takav da je on najvec´i element skupa U ∩V , odnosno vazˇi U ∩V =↑ (z) ∈ C. Neka su dalje U, V,W ∈ C i neka vazˇi U, V ⊆ W tada je U =↑ (x), V =↑ (y),W =↑ (z), za neke x, y, z ∈ T . Kako vazˇi x ∈ U =↑ (x), y ∈ V =↑ (y) i U =↑ (x), V =↑ (y) ⊆ W =↑ (z) bic´e x, y ∈W =↑ (z) pri tom je ↑ (z) linearno ureden skup pa vazˇi bar jedan od uslova: − y ≤ x odnosno V =↑ (y) ⊆ U =↑ (x), − x ≤ y odnosno U =↑ (x) ⊆ V =↑ (y) odnosno vazˇi U ⊆ V ∨ V ⊆ U . Dakle C = {↑ (x)|x ∈ T} je ⊆-hijerarhija. Pokazˇimo dalje da je C povezana ⊆-hijerarhija. Neka je r koren stabla T , u tom slucˇaju za svaki cˇvor x ∈ T vazˇi r ≤ x odnosno r ∈↑ (x) za sve x ∈ T . Kako je C = {↑ (x)|x ∈ T} sledi da je C povezana ⊆-hijerarhija. Dokazˇimo josˇ da je C T⊆-hijerarhija. Neka su x, y ∈ T i x 6= y, jasno x ∈↑ (x), odnosno y ∈↑ (y). Neka je y ∈↑ (x), u protivnom ako y /∈↑ (x) skup U =↑ (x) razdvaja cˇvorove 26 Hijerarhijske strukture podataka Modeli stabla x, y. U tom slucˇaju x /∈↑ (y) jer bi u suprotnom bilo x = y, pa skup U =↑ (y) razdvaja c´vorove x, y. Dakle svaka dva razlicˇita cˇvora stabla T se mogu razdvojiti nekim skupom U iz kolekcije C. Ostalo je da se dokazˇe da je unija kolekcije elemenata ⊆-hijerarhije C elemenat ⊆-hijerarhije C samo ako je jednaka nekom elementu kolekcije. Neka je {C1, C2, . . . , Ck} kolekcija elemenata ⊆-hijerarhije C i k ∈ N , tada je Ci =↑ (xi) za neke xi ∈ T i = 1, 2, . . . , k. Pretpostavimo ⋃ Ci = ⋃ ↑ (xi) ∈ C, odnosno neka postoji cˇvor x ∈ T takav da je ⋃Ci = ⋃ ↑ (xi) =↑ (x) ∈ C. Dokazˇimo da je ↑ (x) =↑ (xi) za neko i ∈ {1, 2, . . . , k}. Kako xi ∈↑ (xi) sledi xi ∈ ⋃ ↑ (xi) =↑ (x), odnosno xi ≤ x za sve i = 1, 2, . . . , k. Sa druge strane je x ∈↑ (x) = ⋃ ↑ (xi) odnosno x ∈↑ (xi) za neko i ∈ {1, 2, . . . , k}, pa je x ≤ xi za neko i ∈ {1, 2, . . . , k}, kako je pri tome xi ≤ x zakljucˇujemo da je x = xi odnosno ↑ (x) =↑ (xi) za neko i ∈ {1, 2, . . . , k} sˇto je i trebalo dokazati.  Vazˇi i obrat, ako je C povezana T⊆-hijerarhija na konacˇnom skupu T tada se skup T mozˇe urediti nekom relacijom ≤ tako da je (T,≤) stablo i svaki element kolekcije C je skup predaka nekog cˇvora stabla T . Pre svega pokazˇimo da povezana T⊆-hijerarhija na konacˇnom skupu T ima isti broj elemenata kao i konacˇan skup T . Teorema 2.3.4. Neka je C povezana T⊆-hijerarhija na konacˇnom skupu T , tada postoji bijekcija ↑: T → C Dokaz. Problem je odrediti cˇvor x ∈ T koji odgovara elementu C ∈ C. Kako je T =⋃ {C|C ∈ C} = ⋃ C, za svaki cˇvor x ∈ T postoji U ∈ C tako da vazˇi x ∈ U , odnosno svaki cˇvor je elemenat bar jednog podskupa skupa cˇvorova T iz kolekcije C. Neka je x ∈ T oznacˇimo sa Cx kolekciju elemenata povezane T⊆-hijerarhije C koji sadrzˇe cˇvor x: Cx = {U ∈ C|x ∈ U} (2.29) Na osnovu prethodnog razmatranja Cx je neprazna kolekcija za sve x ∈ T . Sada mozˇemo formirati skupove: ∩x = ⋂ {U ∈ C|x ∈ U} = ⋂ Cx (2.30) Ocˇigledno x ∈ ∩x za sve x ∈ T . Kako je C ⊆-hijerarhija presek elemenata kolekcije C je element kolekcije C, odnosno {∩x|x ∈ T} ⊆ C. Dakle za x ∈ T , ∩x je najmanji elemenat kolekcije C koji sadrzˇi x, odnosno za x ∈ T i U ∈ C vazˇi: x ∈ U ⇒ ∩x ⊆ U (2.31) Pokazˇimo da je ovim povezana T⊆-hijerarhija C iscrpljena, odnosno C = {∩x|x ∈ T}. Pretpo- stavimo suprotno, neka postoji C ∈ C i za svako x ∈ T , C 6= ∩x. Neka je C = {x1, x2, . . . , xk} ⊆ T i k ∈ N . Kako je xi ∈ C mora biti ∩xi ⊆ C za sve i = 1, 2, . . . , k odnosno ⋃∩xi ⊆ C. Sa druge strane za svako xi ∈ C vazˇi xi ∈ ∩xi pa vazˇi C ⊆ ⋃∩xi, dakle ⋃∩xi = C. Kako je C T⊆-hijerarhija i pri tome je ⋃∩xi = C ∈ C mora biti ⋃∩xi = C = ∩xi za neko i ∈ {1, 2, . . . , k} sˇto je suprotno pretpostavci, dakle C = {∩x|x ∈ T}. 27 Hijerarhijske strukture podataka Modeli stabla Pokazˇimo josˇ da u C = {∩x|x ∈ T} nema istih, odnosno da razlicˇitim cˇvorovima x, y ∈ T odgovaraju razlicˇiti ∩x,∩y ∈ C. Neka su x, y ∈ T i neka je x 6= y, pretpostavimo ∩x = ∩y ∈ C. Kako x, y ∈ ∩x = ∩y i C je T⊆-hijerarhija, postoji C ∈ C tako da tacˇno jedan od x i y pripada C. Neka x ∈ C i y /∈ C. U ovom slucˇaju iz x ∈ C sledi ∩x ⊆ C pa i y ∈ C sˇto je nemoguc´e, dakle ∩x 6= ∩y. Konacˇno preslikavanje ↑: T → C definisano sa ↑ (x) = ∩x je dobro definisano i pri tome je bijekcija.  Teorema 2.3.5. Neka je C povezana T⊆-hijerarhija na konacˇnom skupu T , tada postoji uredenje ≤ skupa T tako da je (T,≤) stablo i svaki element kolekcije C je skup predaka nekog cˇvora stabla T u odnosu na tako uvedeno uredenje ≤. Dokaz. Preslikavanje ↑: T → C definisano sa: ↑ (x) = ∩x = ⋂ {U ∈ C|x ∈ U} = ⋂ Cx (2.32) je bijekcija na osnovu prethodnog stava. Uredimo skup T na sledec´i nacˇin: y ≤ x⇔ ∩y ⊆ ∩x (2.33) Na ovaj nacˇin ↑ je izomorfizam struktura (T,≤) i (C,⊆), pa je struktura (T,≤) stablo, jer je to slucˇaj sa strukturom (C,⊆). Dokazˇimo sada da je pri ovakvom uredenju cˇvorova stabla T , svaki elemenat povezane T⊆-hijerarhije C skup predaka nekog cˇvora x stabla T . Dovoljno je dokazati da za x ∈ T vazˇi {y ∈ T |y ≤ x} = ∩x. Neka je y ∈ {y ∈ T |y ≤ x}, odnosno neka je y ≤ x. S obzirom kako je uvedeno uredenje ≤ bic´e ∩y ⊆ ∩x. Kako je y ∈ ∩y mora biti y ∈ ∩x. Dakle {y ∈ T |y ≤ x} ⊆ ∩x. Dokazˇimo i obrat ∩x ⊆ {y ∈ T |y ≤ x}. Pretpostavimo da je y ∈ ∩x tada je ∩x ∈ Cy pa mora biti ∩y ⊆ ∩x odnosno s obzirom na definiciju relacije ≤ vazˇi y ≤ x odnosno y ∈ {y ∈ T |y ≤ x}. Dakle ↑ (x) = ∩x = {y ∈ T |y ≤ x}, sˇto je i trebalo dokazati.  Iz navedenog zakljucˇujemo da nema razlike izmedu konacˇnog stabla (T,≤) i povezane T⊆- hijerarhije C na skupu T , odnosno to su izomorfne strukture. Dakle umesto stabla (T,≤) mozˇemo posmatrati povezanu T⊆-hijerarhiju C na skupu T , pri tome se odnos izmedu cˇvorova stabla (T,≤) preslikava na odnos izmedu elemenata kolekcije C na sledec´i nacˇin: y ≤ x⇔↑ (y) ⊆↑ (x) (2.34) gde su x, y ∈ T , ↑ (x), ↑ (y) ∈ C odgovarajuc´i elementi struktura (T,≤) i (C,⊆). U ovom modelu cˇvor x ∈ T se reprezentuje skupom cˇvorova ↑ (x) kojima je on potomak, odnosno skupom predaka (2.4). 28 Hijerarhijske strukture podataka Modeli stabla A {A} B {A,B} E {A,B,E} F {A,B, F} J {A,B, F, J} G {A,B,G} C {A,C} D {A,D} H {A,D,H} K {A,D,H,K} L {A,D,H,L} I {A,D, I} Slika 2.4: Skupovi predaka Dakle za obelezˇje cˇvora x ∈ T uzimamo skup njegovih predaka ↑ (x). Kako je skup predaka dobro ureden, obelezˇje cˇvora x c´e biti niz cˇvorova na jedinstvenoj putanji od korena r stabla T do cˇvora x: <↑ (x) > = < r, c1, c2, . . . , ck, x > = {{r}, {r, c1}, . . . {r, c1, . . . , ck, x}} gde su c1, c2, . . . , ck ∈ T cˇvorovi na jedinstvenoj putanji od korena stabla r do cˇvora x. Nije tesˇko pokazati da vazˇi: <↑ (y) >⊆<↑ (x) >⇔<↑ (y) > ≤p <↑ (x) > (2.35) gde je ≤p relacija prefiks na skupu nizova {<↑ (x) > |x ∈ T}. Ovo je takozvani model sa izlistanim putanjama (path enumeration model) (2.5). 29 Hijerarhijske strukture podataka Modeli stabla A < A > B < A,B > E < A,B,E > F < A,B, F > J < A,B, F, J > G< A,B,G > C < A,C > D < A,D > H < A,D,H > K < A,D,H,K > L < A,D,H,L > I < A,D, I > Slika 2.5: Izlistane putanje-Nizovi predaka Predlozˇeni model stabla se dalje mozˇe uprostiti ako svaki cˇvor indeksiramo vrednostima iz skupa prirodnih brojeva N . Ovo indeksiranje cˇvorova se mozˇe izvrsˇiti na sledec´i nacˇin: 1) Koren stabla ima indeks 1 2) Potomci indeksiranog cˇvora se indeksiraju vrednostima 1, 2, . . . ,m; m ∈ N Pri tome se pogodnim indeksiranjem potomaka mozˇe postic´i zˇeljeno uredenje stabla, kao na slici (2.6). A 1 B 1 E 1 F 2 J 1 G 3 C 2 D 3 H 1 K 1 L 2 I 2 Slika 2.6: Indeksiranje cˇvorova stabla 30 Hijerarhijske strukture podataka Modeli stabla Sada svakom cˇvoru stabla x ∈ T , mozˇemo na jednoznacˇan nacˇin pridruzˇiti niz < pathx >=< 1, i1, i2, . . . , ik > cˇiji su elementi indeksi cˇvorova na jedinstvenoj putanji od korena stabla do datog cˇvora x. Ovo pridruzˇivanje se mozˇe izrsˇiti na sledec´i nacˇin: 1) Korenu r stabla T se pridruzˇuje niz indeksa < pathr >=< 1 > duzˇine 1 2) Neka je cˇvoru x pridruzˇen niz indeksa < pathx >. Potomku cˇvora x se indeksom i ∈ {1, 2, . . . ,m}, pridruzˇuje se niz < pathx, i >. Oznacˇimo sa T ∗ skup nizova indeksa pridruzˇenih cˇvorovima stabla T : T ∗ = {x∗|x ∈ T} = {< pathx > |x ∈ T} Neka su x, y ∈ T , ocˇigledno vazˇi: y ≤ x⇔ y∗ ≤p x∗ (2.36) gde je ≤p relacija prefiks na skupu nizova indeksa T ∗, odnosno (T,≤) i (T ∗,≤p) su izomorfne strukture. Ako za obelezˇje cˇvora umesto niza indeksa < pathx >=< 1, i1, i2, . . . , ik >, uzmemo odgova- rajuc´u recˇ pathx = 1.i1. . . . .ik nad azbukom A = {0, 1, . . . , 9, .} relacija ≤p postaje relacija prefiks na skupu recˇi nad azbukom A (2.7). A 1 B 1.1 E 1.1.1 F 1.1.2 J 1.1.2.1 G 1.1.3 C 1.2 D 1.3 H 1.3.1 K 1.3.1.1 L 1.3.1.2 I 1.3.2 Slika 2.7: Dewey-jeva decimalna notacija Ovo je takozvana Dewey-jeva decimalna notacija [11]. Primetimo da se u ovom modelu za zadani cˇvor mozˇe neposredno zakljucˇiti koji su njegovi preci. Na primer preci cˇvora sa obelezˇjem 1.3.1.2 su cˇvorovi sa obelezˇjima redom 1.3.1, 1.3 i 1. 31 Hijerarhijske strukture podataka Modeli stabla 2.3.5 Model sa ugnjezˇdenim skupovima U prethodnoj karakterizaciji stabla cˇvoru stabla je odgovarao skup njegovih prethodnika. Kolekcija skupova prethodnika se ureduje relacijom podskup ⊆. U karakterizaciji koja sledi, cˇvoru stabla c´e odgovarati skup potomaka, a odgovarajuc´a kolekcija skupova potomaka se ureduje relacijom nadskup ⊇. Pre svega uvedimo sledec´e definicije. Definicija 2.3.4. Neka je T konacˇan skup i neka je C kolekcija podskupova od T . C je ⊇-hijerarhija na skupu T ako vazˇi: a) T ∈ C b) za sve U, V ∈ C i U 6= V vazˇi tacˇno jedan od uslova U ⊂ V ∨ V ⊂ U ∨ U ∩ V = ∅.  Definicija 2.3.5. ⊇-hijerarhija C na skupu T je T⊇-hijerarhija na skupu T ako vazˇi: a) za sve x, y ∈ T , x 6= y, postoji U ∈ C tako da tacˇno jedan od x, y pripada U b) unija kolekcije elementa hijerarhije C je elemenat hijerarhije C akko je jednaka nekom cˇlanu kolekcije  Definicija 2.3.6. ⊇-hijerarhija C na skupu T je povezana ⊇-hijerarhija na skupu T ako vazˇi: − postoji element r ∈ T takav da je jedini element U hijerarhije C takav da r ∈ U , polazni skup T .  Sada mozˇemo dati sledec´u karakterizaciju konacˇnog stabla. Teorema 2.3.6. Povezana T⊇-hijerarhija C na konacˇnom skupu T je konacˇno stablo. Dokaz. Neka je C povezana T⊇-hijerarhija na konacˇnom skupu T . Primetimo da prazan skup ∅ ne mozˇe biti elemenat ⊇-hijerarhije C, jer u protivnom ∅, T ∈ C i ∅ 6= T 3 r i pri tome vazˇi ∅ ⊂ T ∧ ∅ ∩ T = ∅, pa C ne mozˇe biti ⊇-hijerarhija. Definiˇsimo funkciju (relaciju) direktni predak f : C → C na sledec´i nacˇin: f(U) = T U = T⋂ CU U 6= T (2.37) gde je CU = {V ∈ C|U V }. Neka je U 6= T elemenat povezane T⊇-hijerarhije C na skupu T , pokazac´emo da mora biti U ( f(U). Kolekcija CU je neprazna jer T ∈ CU , dalje kako svi elementi kolekcije CU imaju neprazan presek i pri tome je C konacˇna ⊇-hijerarhija, postoji V0 ∈ CU takav da za svako V ∈ CU vazˇi V0 ⊆ V , odnosno postoji V0 ∈ CU takvo da vazˇi V0 = ⋂ CU = f(U). Kako 32 Hijerarhijske strukture podataka Modeli stabla V0 ∈ CU zakljucˇujemo U ( V0 = f(U). Josˇ viˇse, neka je U 6= T elemenat povezane T⊇- hijerarhije C na skupu T tada vazˇi U ( fk(U) za sve k ∈ N . Iz prethodnog mozˇemo zakljucˇiti da funkcija f ima tacˇno jednu fiksnu tacˇku T i pri tome fk k = 2, 3, . . . nema drugih fiksnih tacˇaka sem tacˇke T , pa je povezana T⊇-hijerarhija na konacˇnom skupu T stablo.  Funkcija f iz prethodne teoreme, na povezanoj T⊇-hijerarhiji C na konacˇnom skupu T , ima sledec´u osobinu. Neka su U, V ∈ C, tada vazˇi: i k ∈ N0 V = fk(U)⇔ V ⊇ U (2.38) odnosno relacija nadskup ⊇ na C je refleksivno i tranzitivno zatvorenje ovako definisane funkcije (relacije) direktni predak f . ⊇= ∪ k∈N0 fk (2.39) gde je: ⊇= {(V,U)|(U, V ∈ C)V ⊇ U} (2.40) fk = { (V,U)|(V,U ∈ C)V = fk(U) } (2.41) Drugim recˇima povezana T⊇-hijerarhija na konacˇnom skupu T je stablo ako se uredi relacijom nadskup. Neka je (T,≤) konacˇno stablo, pokazˇimo da se mozˇe konstruisati povezana T⊇-hijerarhija C na skupu T . Pre svega primetimo da u ovoj karakterizaciji svakom cˇvoru x ∈ T odgovara skup njegovih potomaka, odnosno skup cˇvorova kojima je on predak. U tom smislu definiˇsimo preslikavanje ↓: T → P (A) na sledec´i nacˇin: ↓ (x) = {z ∈ T |x ≤ z} (2.42) gde je P (A) partitivni skup skupa cˇvorova T . Sada nije tesˇko pokazati sledec´i stav. Teorema 2.3.7. Neka je (T,≤) konacˇno stablo. Kolekcija C = {↓ (x)|x ∈ T} =↓ T , je povezana T⊇-hijerarhija na skupu T . Dokaz. Primetimo x ∈↓ (x) za sve x ∈ T . Pokazˇimo prvo da je C ⊇-hijerarhija na T . Neka je r koren stabla T , ocˇigledno ↓ (r) = T ∈ C. Neka su U, V ∈ C i U 6= V , tada je U =↓ (x), V =↓ (y), za neke x, y ∈ T . Mora biti x 6= y, jer bi u suprotnom vazˇilo ↓ (x) =↓ (y) odnosno U = V sˇto je suprotno pretpostavci U 6= V . Neka je U =↓ (x) ∩ V =↓ (y) 6= ∅, odnosno neka postoji z ∈ T tako da z ∈ U =↓ (x) ∧ z ∈ V =↓ (y), odnosno cˇvorovi x, y su preci cˇvora z, dakle x, y ∈↑ (z). (T,≤) je stablo pa je skup predaka ↑ (z) dobro ureden pa vazˇi tacˇno jedan od uslova: − y x odnosno V =↓ (y) ) U =↓ (x) 33 Hijerarhijske strukture podataka Modeli stabla − x y odnosno U =↓ (x) ) V =↓ (y) odnosno vazˇi tacˇno jedan od uslova U ∩ V = ∅ ∨ U ⊂ V ∨ V ⊂ U . Dakle C = {↑ (x)|x ∈ T} je ⊇-hijerarhija. Ocˇigledno da je to povezana ⊇-hijerarhija jer koren r stabla T je potomak jedino sebe samog, odnosno vazˇi r ∈↓ (x)⇔ r ∈↓ (r) = T . Dokazˇimo josˇ da je C T⊇-hijerarhija. Neka su x, y ∈ T i x 6= y, jasno x ∈↓ (x), odnosno y ∈↓ (y). Neka je y ∈↓ (x), u protivnom ako y /∈↓ (x) skup U =↓ (x) razdvaja cˇvorove x, y. U tom slucˇaju x /∈↓ (y) jer bi u suprotnom bilo x = y, pa skup U =↓ (y) razdvaja c´vorove x, y. Dakle svaka dva razlicˇita cˇvora stabla T se mogu razdvojiti nekim skupom U iz kolekcije C. Dokazˇimo josˇ da je unija kolekcije elemenata ⊇-hijerarhije C elemenat hijerarhije C samo ako je jednaka nekom elementu kolekcije. Neka je {C1, C2, . . . , Ck} kolekcija elemenata ⊇-hijerarhije C i k ∈ N , tada je Ci =↓ (xi) za neke xi ∈ T i = 1, 2, . . . , k. Pretpostavimo ⋃ Ci = ⋃ ↓ (xi) ∈ C, odnosno neka postoji cˇvor x ∈ T takav da je ⋃Ci = ⋃ ↓ (xi) =↓ (x) ∈ C. Dokazˇimo da je ↓ (x) =↓ (xi) za neko i ∈ {1, 2, . . . , k}. Iz xi ∈↓ (xi) sledi xi ∈ ⋃ ↓ (xi) =↓ (x), odnosno x ≤ xi za sve i = 1, 2, . . . , k. Sa druge strane je x ∈↓ (x) = ⋃ ↓ (xi) odnosno x ∈↓ (xi) za neko i ∈ {1, 2, . . . , k}, pa je xi ≤ x za neko i ∈ {1, 2, . . . , k}, kako je pri tome x ≤ xi zakljucˇujemo da je x = xi odnosno ↓ (x) =↓ (xi) za neko i ∈ {1, 2, . . . , k} sˇto je i trebalo dokazati.  Vazˇi i obrat, ako je C povezana T⊇-hijerarhija na konacˇnom skupu T tada se skup T mozˇe urediti nekom relacijom≤ tako da je (T,≤) stablo i svaki element kolekcije C je skup potomaka nekog cˇvora stabla T . Pre svega pokazˇimo da povezana T⊇-hijerarhija na konacˇnom skupu T ima isti broj elemenata kao i konacˇan skup T . Teorema 2.3.8. Neka je C povezana T⊇-hijerarhija na konacˇnom skupu T , tada postoji bijekcija ↓: T → C Dokaz. Problem je odrediti cˇvor x ∈ T koji odgovara elementu C ∈ C. Kako je C povezana ⊇-hijerarhija, postoji istaknuti element r ∈ T , koji c´emo pridruzˇiti elementu T ∈ C. Neka je x ∈ T i x 6= r proizvoljan cˇvor. Kako je C T⊇-hijerarhija postoji U ∈ C tako da tacˇno jedan od x i r pripada U , ocˇigledno je da je jedina moguc´nost da x ∈ U . Dakle za svaki cˇvor x ∈ T postoji U ∈ C tako da vazˇi x ∈ U , odnosno svaki cˇvor je elemenat bar jednog podskupa skupa cˇvorova T iz kolekcije C. Neka je x ∈ T oznacˇimo sa Cx kolekciju elemenata povezane T⊇-hijerarhije C koji sadrzˇe cˇvor x: Cx = {U ∈ C|x ∈ U} (2.43) Na osnovu prethodnog razmatranja Cx je neprazna kolekcija za sve x ∈ T . Sada mozˇemo formirati skupove: ∩x = ⋂ {U ∈ C|x ∈ U} = ⋂ Cx (2.44) Ocˇigledno x ∈ ∩x. Kako skupovi iz kolekcije Cx = {U ∈ C|x ∈ U} imaju neprazan presek i pri tome je C konacˇna ⊇-hijerarhija postoji U0 ∈ Cx tako da je ∩x = ⋂ Cx = U0 ∈ C. Dakle 34 Hijerarhijske strukture podataka Modeli stabla za sve x ∈ T ∩x je elemenat kolekcije C, odnosno {∩x|x ∈ T} ⊆ C. Posebno ∩x je najmanji elemenat kolekcije C koji sadrzˇi x, odnosno za x ∈ T i U ∈ C vazˇi: x ∈ U ⇒ ∩x ⊆ U (2.45) Pokazˇimo da je ovim povezana T⊇-hijerarhija C iscrpljena, odnosno C = {∩x|x ∈ T}. Pretpo- stavimo suprotno, neka postoji C ∈ C i za svako x ∈ T , C 6= ∩x. Neka je C = {x1, x2, . . . , xk} ⊆ T i k ∈ N . Kako je xi ∈ C mora biti ∩xi ⊆ C za sve i = 1, 2, . . . , k odnosno ⋃∩xi ⊆ C. Sa druge strane za svako xi ∈ C vazˇi xi ∈ ∩xi pa vazˇi C ⊆ ⋃∩xi, dakle ⋃∩xi = C. Kako je C T⊇-hijerarhija i pri tome je ⋃∩xi = C ∈ C mora biti ⋃∩xi = C = ∩xi za neko i ∈ {1, 2, . . . , k} sˇto je suprotno pretpostavci, dakle C = {∩x|x ∈ T}. Pokazˇimo josˇ da u C = {Cx|x ∈ T} nema istih, odnosno da razlicˇitim cˇvorovima x, y ∈ T odgovaraju razlicˇiti ∩x,∩y ∈ C. Neka su x, y ∈ T i neka je x 6= y, pretpostavimo ∩x = ∩y ∈ C. Kako x, y ∈ ∩x = ∩y i C je T⊇-hijerarhija, postoji C ∈ C tako da tacˇno jedan od x i y pripada C. Neka x ∈ C i y /∈ C. U ovom slucˇaju iz x ∈ C sledi ∩x ⊆ C pa i y ∈ C sˇto je suprotno pretpostavci, dakle ∩x 6= ∩y. Dakle preslikavanje ↓: T → C definisano sa ↓ (x) = ∩x je dobro definisano i pri tome je bijekcija.  Teorema 2.3.9. Neka je C povezana T⊇-hijerarhija na konacˇnom skupu T , tada postoji uredenje ≤ skupa T tako da je (T,≤) stablo i svaki element kolekcije C je skup potomaka nekog cˇvora stabla T u odnosu na tako uvedeno uredenje ≤. Dokaz. Preslikavanje ↓: T → C definisano sa: ↓ (x) = ∩x = ⋂ {U ∈ C|x ∈ U} = ⋂ Cx (2.46) je bijekcija na osnovu prethodnog stava. Uredimo skup T na sledec´i nacˇin: y ≤ x⇔ ∩y ⊇ ∩x (2.47) Na ovaj nacˇin ↓ je izomorfizam struktura (T,≤) i (C,⊇), pa je struktura (T,≤) stablo, jer je to slucˇaj sa strukturom (C,⊇). Dokazˇimo sada da je pri ovakvom uredenju cˇvorova stabla T , svaki elemenat povezane T⊇-hijerarhije C skup potomaka nekog cˇvora x stabla T . Dovoljno je dokazati da za x ∈ T vazˇi {y ∈ T |x ≤ y} = ∩x. Neka je y ∈ {y ∈ T |x ≤ y}, odnosno neka je x ≤ y. S obzirom kako je uvedeno uredenje ≤ bic´e ∩x ⊇ ∩y. Kako je y ∈ ∩y mora biti y ∈ ∩x. Dakle ↓ (x) ⊆ ∩x. Dokazˇimo i obrat ∩x ⊆ {y ∈ T |x ≤ y}. Pretpostavimo da je y ∈ ∩x, tada je ∩x ∈ Cy pa mora biti ∩y ⊆ ∩x odnosno s obzirom na definiciju relacije ≤ vazˇi x ≤ y dakle y ∈ {y ∈ T |x ≤ y}. Dakle ↓ (x) = ∩x = {y ∈ T |x ≤ y}, sˇto je i trebalo dokazati.  Iz navedenog zakljucˇujemo da nema razlike izmedu konacˇnog stabla (T,≤) i povezane T⊇- hijerarhije C na skupu T , odnosno to su izomorfne strukture. Dakle umesto stabla (T,≤) 35 Hijerarhijske strukture podataka Modeli stabla mozˇemo posmatrati povezanu T⊇-hijerarhiju C na skupu T , pri tome se odnos izmedu cˇvorova stabla (T,≤) preslikava na odnos izmedu elemenata kolekcije C na sledec´i nacˇin: y ≤ x⇔↓ (y) ⊇↓ (x) (2.48) gde su x, y ∈ T , ↓ (x), ↓ (y) ∈ C odgovarajuc´i elementi struktura (T,≤) i (C,⊇). U ovom modelu cˇvor x ∈ T se reprezentuje skupom cˇvorova ↓ (x) kojima je on predak, odnosno cˇvorovima podstabla kojima je on koren. Ovo je takozvani model sa ugnjezˇdenim skupovima (nested sets model) (2.8). A {A,B,C,D,E, F,G,H, I, J,K,L} B {B,E, F,G, J} E {E} F {F, J} J {J} G {G} C {C} D {D,H, I,K,L} H {H,K,L} K {K} L {L} I {I} Slika 2.8: Ugnjezˇdeni skupovi-Skupovi potomaka Dakle za obelezˇje cˇvora x ∈ T uzimamo skup njegovih potomaka ↓ (x). Cilj je opisati skup ↓ (x) u kompaktnoj formi. Za razliku od modela sa izlistanim putanjama, obelezˇje cˇvora u ovom slucˇaju skup potomaka, nije u opsˇtem slucˇaju dobro ureden. Kompaktnu formu skupa potomaka mozˇemo obezbediti ako na pogodan nacˇin indeksiramo cˇvorove stabla, a to se mozˇe postic´i ako su cˇvorovi svakog podstabla indeksirani uzastopnim prirodnim brojevima. U tom slucˇaju je obelezˇje cˇvora skup indeksa njegovih potomaka: ↓ (x) = {i, i+ 1, . . . , i+ k} (2.49) Kako se radi o uzastopnim indeksima, skup ↓ (x) c´e biti interval prirodnih brojeva [i, i+k], pri cˇemu je i indeks samog cˇvora x, i+k je indeks njegovog poslednjeg indeksiranog potomaka, a k je broj njegovih potomaka. Dakle obelezˇje cˇvora x ∈ T je ureden par (leftx, rightx) koji cˇine leva i, odnosno desna i + k granica intervala prirodnih brojeva. Ovakvom reprezentacijom stabla neposredno se proverava da li je dati cˇvor x predak cˇvora y na sledec´i nacˇin: 36 Hijerarhijske strukture podataka Modeli stabla y ≤ x ⇔ ↓ (y) ⊇↓ (x) ⇔ [lefty, righty] ⊇ [leftx, rightx] ⇔ lefty ≤ leftx ∧ rightx ≤ righty iskoristimo li osobinu ⊇-hijerarhije na T , imac´emo: y ≤ x⇔ lefty ≤ leftx ≤ righty (2.50) ili simetricˇno: y ≤ x⇔ lefty ≤ rightx ≤ righty (2.51) Postavlja se pitanje kako resˇiti problem indeksiranja cˇvorova stabla koje bi imalo navedenu osobinu. Primetimo sledec´e, prvo se indeksira cˇvor, a zatim njegovi potomci. Ako zanemarimo indeksiranje, onda se problem resˇava tako sˇto prvo obilazimo cˇvor, a zatim njegove potomke [5]. Ovo je tacˇno pre-order obilazak stabla (2.2). Dakle cˇvorovima stabla se mogu pridruzˇiti obelezˇja, odnosno leva i desna granica tako sˇto se stablo obilazi na pre-order nacin. Prvo se obilazi cˇvor pa njegova podstabla i to od krajnjeg levog do krajnjeg desnog podstabla. Vrednosti za granice (indeksi cˇvorova) su uzastopni prirodni brojevi 1, 2, . . .. Leva granica (indeks samog cˇvora) se formira u prvom prolazu kroz cˇvor i njena vrednost je sledec´a vrednost indeksa. Desna granica (indeks poslednjeg indeksiranog potomka) se formira pri povratku u cˇvor i njena vrednost je tekuc´a vrednost indeksa (poslednji iskoriˇsc´eni indeks) (2.9). A1 12 B2 6 E3 3 F4 5 J5 5 G6 6 C7 7 D8 12 H9 11 K10 10 L11 11 I12 12 Slika 2.9: Skup potomaka Za razliku od modela sa izlistanim putanjama, u ovom modelu se za zadati cˇvor ne mozˇe 37 Hijerarhijske strukture podataka Modeli stabla neposredno zakljucˇiti koji su njegovi preci, ali se sa druge strane mozˇe neposredno odrediti broj potomaka datog cˇvora. 2.3.6 Model sa ugnjezˇdenim intervalima U modelu sa ugnjezˇdenim skupovima svakom cˇvoru se pridruzˇuje obelezˇje koje je skup nje- govih potomaka. Pogodnom numeracijom cˇvorova stabla, to mozˇe biti interval prirodnih brojeva. Osnovni problem je nemoguc´nost efikasnog umetanja novih cˇvorova jer interval pri- rodnih brojeva nije dovoljno gust, pa se svakako mora vrsˇiti ponovna numeracija cˇvorova da bi se napravio prostor za novi cˇvor. Ako umesto intervala prirodnih brojeva uzmemo interval racionalnih (realnih) brojeva problem umetanja cˇvorova c´e biti resˇen. U zavisnosti od toga koji se podinterval intervala pridruzˇenog nadredenom cˇvoru dodeljuje podredenom cˇvoru dobic´emo razlicˇite tipove modela sa ugnjezˇdenim intervalima. Binarni model sa ugnjezˇdenim intervalima Jedan tip modela sa ugnjezˇdenim intervalima mozˇe biti sledec´i [7]. Pridruzˇimo korenu stabla neki interval, bez gubitka opsˇtosti to mozˇe biti interval (0, 1) i to je na pocˇetku slobodni interval korena. Dalje se svakom potomku pridruzˇuje leva polovina slobodnog intervala. Na primer, prvom potomku korena se pridruzˇuje interval ( 0, 1 2 ) i nakon ovog pridruzˇivanja slobodan interval korena je interval ( 1 2 , 1 ) . Sledec´em potomku se na isti nacˇin pridruzˇuje leva polovina novog slobodnog intervala ( 1 2 , 1 ) , a to je interval ( 1 2 , 1 2 + 1 22 ) = ( 1 2 , 3 4 ) (2.10): A0 1 B C D0 1 2 3 4 7 8 E F G H0 1 4 3 8 7 16 3 4 13 16 27 32 Slika 2.10: Selekcija intervala Uopsˇte neka je cˇvoru stabla pridruzˇen interal (l, r), to je na pocˇetku i slobodan interval tog cˇvora. Potomku cˇvora se dodeljuje leva polovina njegovog slobodnog intervala, odnosno interval (l, l + r 2 ). Novi slobodni interval uocˇenog cˇvora je desna polovina polaznog intervala (l, r), odnosno interval ( l + r 2 , r). Ovo je takozvani binarni model sa ugnjezˇdenim intervalima 38 Hijerarhijske strukture podataka Modeli stabla (2.11): A (0, 1) B ( 0, 1 2 ) E ( 0, 1 4 ) F ( 1 4 , 3 8 ) J ( 1 4 , 5 16 ) G ( 3 8 , 7 16 ) C ( 1 2 , 3 4 ) D ( 3 4 , 7 8 ) H ( 3 4 , 13 16 ) K ( 3 4 , 25 32 ) L ( 25 32 , 51 64 ) I ( 13 16 , 27 32 ) Slika 2.11: Binarni model Problem kod ovog modela je sˇto obelezˇja (imenioci granica intervala) eksponencijalno rastu. Ovo se mozˇe resˇiti na sledec´i nacin. Primetimo da je duzˇina intervala koji se pridruzˇuje cˇvoru drveta jednaka 1 2k k ∈ N , ako iskoristimo binarni zapis leve odnosno desne granice intervala, intervali koji se pridruzˇuju cˇvorovima drveta (sem korena kome je pridruzˇen interval (0, 1) su sledec´eg oblika: (0.a1a2 . . . ak−1, 0.a1a2 . . . ak−11), ai ∈ {0, 1} (2.52) Ocˇigledno je interval pridruzˇen cˇvoru u potpunosti odreden svojom desnom granicom. Dakle dovoljno je za obelezˇje cˇvora uzeti desnu granicu pridruzˇenog intervala. Obelezˇje korena c´e biti 1, a ostalih cˇvorova zapis oblika 0.a1a2. . . ak−11. Zapis desne granice pridruzˇenog intervala dalje mozemo shvatiti kao recˇ nad binarnom azbukom A2 = {0, 1} koja se zavrsˇava slovom 1. Ocˇigledno mozˇemo izbaciti zavrsˇno slovo 1 i dobic´emo skup obelezˇja koji cˇine prazna recˇ (obelezˇje korena) i recˇi binarne azbuke koje pocˇinju slovom 0 (obelezˇja cˇvorova koji nisu koren), ovo su prakticˇno zapisi levih granica pridruzˇenih intervala (2.12). 39 Hijerarhijske strukture podataka Modeli stabla A B 0 E 00 F 001 J 0010 G 0011 C 01 D 011 H 0110 K 01100 L 011001 I 01101 Slika 2.12: Binarni model sa levom granicom Primetimo da obelezˇje cˇvora pri sledec´oj interpretaciji: · 0 - spusti se na nivo ispod krajnjom levom granom · 1 - predi na sledec´i cˇvor na istom nivou. predstavlja putanju od korena do datog cˇvora. Na primer, cˇvoru L je pridruzˇen interval( 25 32 , 51 64 ) , zapis desne granice je sledec´a recˇ 0110011 nad binarnom azbukom A2: 51 64 = 0 20 + 1 21 + 1 22 + 0 23 + 0 24 + 1 25 + 1 26 Ako izbacimo zavrsˇno slovo 1 dobic´emo obelezˇje (binarni zapis leve granice) 011001 cˇvora L koje se dalje interpretira na sledec´i nacˇin: · 0 - spusti se na nivo ispod krajnjom levom granom (cˇvor B) · 1 - predi na sledec´i cˇvor na istom nivou (cˇvor C) · 1 - predi na sledec´i cˇvor na istom nivou (cˇvor D) · 0 - spusti se na nivo ispod krajnjom levom granom (cˇvor H) · 0 - spusti se na nivo ispod krajnjom levom granom (cˇvor K) · 1 - predi na sledec´i cˇvor na istom nivou (cˇvor L) Primetimo sledec´e, duzˇina poodrecˇi koja pocˇinje slovom 0 (prelazak na nizˇi nivo) do sledec´eg slova 0 predstavlja indeks cˇvora na tekuc´em nivou u modelu sa izlistanim putanjama. Dakle, ako izvrsˇimo opisanu transformaciju obelezˇja cˇvora, dobic´emo: · 011 - trec´i cˇvor na prvom nivou (1.3) 40 Hijerarhijske strukture podataka Modeli stabla · 0 - prvi cˇvor na drugom nivou (1.3.1) · 01 - drugi cˇvor na trec´em nivou (1.3.1.2) sˇto je obelezˇje cˇvora u modelu sa izlistanim putanjama, odnosno Dewey-jeva decimalna no- tacija. Slicˇno kao u modelu sa izlistanim putanjama i u ovom modelu je problem sˇto se ne mozˇe efikasno umetati cˇvor, odnosno novi cˇvor se na isti nacˇin kao i u modelu sa izlistanim putanjama dodaje uvek na kraj postojec´eg niza potomaka na datom nivou. Na primer, novi potomak X cˇvora D ide na kraj postojec´e liste potomaka H, I (2.13) A B 0 E 00 F 001 J 0010 G 0011 C 01 D 011 H 0110 K 01100 L 011001 I 01101 X 011011 Slika 2.13: Binarni model insert - D ≤ X Problem umetanja cˇvorova je posledica toga sˇto susedni potomci imaju zajednicˇku granicu tako da se novi cˇvor ne mozˇe efikasno umetati, a da se pri tome postigne zˇeljeno uredenje potomaka. Ovo se izmedu ostalog mozˇe resˇiti na neki od sledec´a dva nacˇina: 1) preoznacˇavanjem odgoarajuc´ih cˇvorova stabla. Na primer, dodajmo cˇvor X koji c´e biti potomak cˇvora D, tako da se postigne sledec´e uredenje X < H < I potomaka cˇvora D. Cˇvorovi u podstablima sa korenom u H i I c´e biti preoznacˇeni, odnosno dobic´e nova obelezˇja (2.14) 41 Hijerarhijske strukture podataka Modeli stabla A B 0 E 00 F 001 J 0010 G 0011 C 01 D 011 X 0110 H 01101 K 011010 L 0110101 I 011011 Slika 2.14: Binarni model insert - X < H 2) samo pridruzˇivanje podintervala se vrsˇi tako da uvek ostaje slobodan levi odnosno desni podinterval, pa je uvek moguc´e umetati cˇvor levo ili desno od postojec´eg, odnosno moguc´e je postic´i zˇeljeno uredenje potomaka. Ovo se mozˇe postic´i ako se sakom novom cˇvoru dodeljuje neki srednji deo slobodnog intervala nadredenog cˇvora. Ocˇigledno je prvo resˇenje neefikasno jer se u proseku zahteva azˇuriranje obelezˇja na polovini cˇvorova stabla. Razmotric´emo dakle drugo resˇenje problema umetanja cˇvorova. Ternarni model sa ugnjezˇdenim intervalima Ovaj tip modela sa ugjnezˇdenim intervalima mozˇemo definisati na sledec´i nacin. Slicˇno kao sˇto je to uradeno u prethodnom modelu, korenu stabla se pridruzˇuje interval (0, 1) i to je na pocˇetku jedini slobodni interval korena. Dalje se svakom potomku datog cˇvora pridruzˇuje srednja trec´ina nekog njegovog slobodnog intervala. Na primer, prvom potomku korena pri- druzˇujemo interval ( 2 · 0 + 1 3 , 0 + 2 · 1 3 ) = ( 1 3 , 2 3 ) , Drugi potomak korena mozˇemo smestiti levo od prvog potomka i tada biramo podinterval levog slobodnog intervala ( 0, 1 3 ) ili ga mozˇemo smestiti desno kada biramo podinterval desnog slobodnog intervala ( 2 3 , 1 ) (2.15). 42 Hijerarhijske strukture podataka Modeli stabla A0 1 B C 1 3 2 3 7 9 8 9 25 27 26 27 E 4 9 5 9 16 27 17 27 22 27 Slika 2.15: Selekcija intervala Uopsˇte neka je cˇvoru stabla pridruzˇen interal (l, r), to je na pocˇetku i jedini slobodni interval tog cˇvora. Potomku cˇvora se pridruzˇuje podinterval nekog njegovog slobodnog intervala i to na sledec´i nacˇin. Bira se slobodni interval datog cˇvora, neka je to interval (l, r). Potomku datog cˇvora se dodeljuje interval ((2l + r)/3, (l + 2r)/3), odnosno srednja trec´ina izabranog slobodnog intervala. Na ovaj nacˇin ostaju dva slobodna intervala: − levi podinterval: (l, (2l + r)/3) − desni podinterval: ((l + 2r)/3, r) za nove potomke datog cˇvora. Ocˇigledno se umetanje cˇvorova mozˇe izvesti tako da se postigne zˇeljeno uredenje potomaka, nezavisno od redosleda smesˇtanja cˇvorova. Ovo je takozvani ternarni model sa ugnjezˇdenim intervalima (2.16). A (0, 1) B ( 1 3 , 2 3 ) E ( 4 9 , 5 9 ) F ( 16 27 , 17 27 ) J ( 49 81 , 50 81 ) G ( 52 81 , 53 81 ) C ( 7 9 , 8 9 ) D ( 25 27 , 26 27 ) H ( 76 81 , 77 81 ) K ( 229 243 , 230 243 ) L ( 691 729 , 692 729 ) I ( 232 243 , 233 243 ) Slika 2.16: Ternarni model 43 Hijerarhijske strukture podataka Modeli stabla Slicˇno kao i u prethodnom modelu, problem je sˇto obelezˇja (imenioci granica intervala) ekspo- nencijalno rastu. Po ugledu na resˇenje u slucˇaju binarnog modela sa ugnjezˇdenim intervalima, ovde c´emo koristiti ternarni zapis granica intervala. Primetimo da su uzimajuc´i u obzir nacˇin formiranja podintervala, leva odnosno desna granica jedinstvene. Isto tako, duzˇina intervala koji se pridruzˇuje nekom cˇvoru stabla jednaka je 1 3k k ∈ N . Nije tesˇko pokazati da je ternarni zapis intervala koji se pridruzˇuju cˇvorovima stabla sledec´eg oblika: (0.a1a2 . . . ak−11, 0.a1a2 . . . ak−12), ai ∈ {0, 1, 2} (2.53) Ocˇigledno je interval jedinstveno odreden svojom levom (desnom) granicom. Dakle dovoljno je za obelezˇje cˇvora uzeti samo na primer, levu granicu i to njen ternarni zapis. Obelezˇje korena c´e biti 0, a ostalih cˇvorova zapis oblika 0.a1a2 . . . ak−11. Slicˇno kao sˇto je to uradeno u prethodnom modelu, zapis leve granice intervala mozemo shvatiti kao recˇ nad ternarnom azbukom A3 = {0, 1, 2} koja pocˇinje slovom 0, a ako je duzˇine vec´e od 1 onda se mora zavrsˇavati slovom 1. Ocˇigledno mozˇemo izbaciti pocˇetno slovo 0 i dobic´emo skup obelezˇja koji cˇine prazna recˇ (obelezˇje korena) i recˇi ternarne azbuke koje se zavrsˇavaju slovom 1 (obelezˇja cˇvorova koji nisu koren). Slova u recˇi koja je obelezˇje cˇvora opisuju izbor intervala koji se pridruzˇuje datom cˇvoru i to na sledec´i nacˇin: · 0 - tekuc´i interval je levi podinterval tekuc´eg intervala · 1 - izbor srednjeg podintervala tekuc´eg intervala (ide se na sledec´i nivo) · 2 - tekuc´i interval je desni podinterval tekuc´eg intervala polazec´i od intervala (0, 1) koji je pridruzˇen korenu stabla (2.17). A B 1 E 11 F 121 J 1211 G 1221 C 21 D 221 H 2211 K 22111 L 221121 I 22121 Slika 2.17: Ternarni model sa levom granicom 44 Hijerarhijske strukture podataka Modeli stabla Nije tesˇko pokazati da za cˇvorove stabla x i y sa obelezˇjima leftx i lefty u ovom modelu vazˇi: x ≤ y ⇔ leftx ≤p lefty (2.54) gde je ≤p relacija prefiks na uocˇenom skupu obelezˇja. Na primer, cˇvoru L je pridruzˇen interval( 691 729 , 692 729 ) , pa je zapis leve granice bez vodec´e 0: 691 729 = 2 31 + 2 32 + 1 33 + 1 34 + 2 35 + 1 36 recˇ 221121 nad ternarnom azbukom A3 i to je obelezˇje cˇvora L. Prethodnici cˇvora L su cˇvorovi sa obelezˇjem koje je prefiks obelezˇja cˇvora L i zavrsˇavaju se slovom 1: · 2211 - cˇvor H · 221 - cˇvor D · ε - cˇvor A (koren stabla) gde je ε prazna recˇ. U ovom modelu se za razliku od binarnog modela sa ugnjezˇdenim intervalima, odnosno modela sa izlistanim putanjama mozˇe efikasno umetati cˇvor, a da se pri tome postigne zˇeljeno uredenje potomaka datog cˇvora. Na primer, dodajmo cˇvorove X, Y , Z koji su potomci cˇvora D tako da se postigne sledec´e uredenje X < H < Y < I < Z potomaka cˇvora D. Odgovarajuc´a obelezˇja su: X - 221+01 na cˇvoru D biramo levi podinterval 0 (cˇvoru H je pridruzˇen srednji podinterval), a zatim se spusˇtamo na sledec´i nivo 1 (2.18) A B 1 E 11 F 121 J 1211 G 1221 C 21 D 221 X 22101 H 2211 K 22111 L 221121 I 22121 Slika 2.18: Ternarni model - insert X < H 45 Hijerarhijske strukture podataka Modeli stabla Y - 221+201 na cˇvoru D biramo desni podinterval 2 (cˇvoru H je pridruzˇen srednji podin- terval), sredina desnog podintervala je cˇvor I zato dalje biramo levi podinterval 0 i na kraju se spusˇtamo na sledec´i nivo 1 (2.19) A B 1 E 11 F 121 J 1211 G 1221 C 21 D 221 H 2211 K 22111 L 221121 Y 221201 I 22121 Slika 2.19: Ternarni model - insert H < Y < I Z - 221+221 na cˇvoru D biramo desni podinterval 2 (cˇvoru H je pridruzˇen srednji podinter- val), sredina desnog podintervala je cˇvor I zato dalje biramo desni podinterval 2 i na kraju se spusˇtamo na sledec´i nivo 1 (2.20) A B 1 E 11 F 121 J 1211 G 1221 C 21 D 221 H 2211 K 22111 L 221121 I 22121 Z 221221 Slika 2.20: Ternarni model - insert I < Z 46 Glava 3 Planiranje odrzˇavanja vazduhoplova 3.1 Uvodna razmatranja U delu planiranja odrzˇavanja, jedan od osnovnih problema izmedu ostalog je neizvesnost dogadaja koji znacˇajno uticˇu na efikasnost odrzˇavanja. Recˇ je o dogadajima koji su po svojoj prirodi slucˇajni. Ovi slucˇajni dogadaji su pored ostalog vezani za: − vremenski trenutak otkaza rezervnog dela − vremenski trenutak zahteva za nekim delom − vreme isporuke, odnosno vreme potrebno za sklapanje (pripremu) rezervnog dela Posebno, podrazumevalo se da je vreme isporuke odnosno vreme potrebno za pripremu re- zervnog dela nula (rezervni deo je neposredno dostupan), a to je pretpostavka neogranicˇenih resursa sˇto je uglavnom redak slucˇaj. Kako mnogo faktora uticˇe na ovo vreme, ono po pra- vilu uvek ima neko slucˇajano odstupanje. Za neke analize vreme isporuke odnosno vreme sklapanja rezervnog dela se mozˇe ignorisati, ali u analizi kompletnog sitema odrzˇavanja ova odstupanja bitno degradiraju performanse sistema. Pod vremenom isporuke (lead time) za dati rezervni deo podrazumeva se: − vreme koje je potrebno da bi se rezervni deo dopremio iz nekog spoljnjeg izvora − vreme koje je potrebno da bi se rezervni deo sklopio prema utvrdenoj proceduri skla- panja − vreme da bi se poluproizvod obradio do nivoa gotovog rezervnog dela Na ovo vreme uticˇe mnosˇtvo faktora. Neki od faktora su: − problemi u transportu − kvar na masˇinama − problemi vezani za kvalitet 47 Planiranje odrzˇavanja vazduhoplova Uvodna razmatranja Ovi faktori su po svojoj prirodi slucˇajne velicˇine, pa je i ovo vreme isporuke po pravilu slucˇajna velicˇina. Jedan od pristupa kojim se mozˇe umanjiti uticaj ovih slucˇajnih velicˇina je skladiˇstenje gotovih rezervnih delova, odnosno odrzˇavanje zaliha gotovih rezervnih delova. U slucˇaju da je ovaj nivo iznad odgovarajuc´eg javic´e se nepotrebni trosˇkovi skladiˇstenja. Sa druge strane ako je nivo zaliha ispod odgovarajuc´eg nivoa javic´e se trosˇkovi kasˇnjenja. Cilj je odrzˇavati nivo zaliha kojim se obezbeduju minimalni trosˇkovi skladiˇstenja sa jedne strane a pri tome se garantuje visok nivo raspolozˇivosti gotovih delova kako bi se minimizovali trosˇkovi kasˇnjenja. Za uspesˇno resˇavanje ovog problema neophodno je razviti odgovarajuc´e matematicˇke modele koji c´e na odgovarajuc´i nacˇin tretirati neizvesnost pojedinih faktora u sistemu odrzˇavanja. Posebno problem odredivanja nivoa zaliha rezervnih delova u kontekstu slucˇajnog broja zahteva za rezervnim delovima je problem koji je najviˇse izucˇavan i analiziran. Kako je narucˇivanje i prodaja dnevnih novina ilustrativna metafora za ovaj tip problema, za probleme ovog tipa koristi se termin newsboy problem, a za odgovarajuc´i model se koristi termin newsboy model [28]. Newsboy problemi nisu samo problemi iz oblasti upravljanja zalihama, oni se javljaju u svim situacijama kada treba izvrsˇiti ocenu neke slucˇajne promen- ljive, a ta ocena je rezultat kompromisa izmedu gubitaka u slucˇaju da je vrednost slucˇajne promenljive precenjena i gubitaka koji su posledica potcenjene vrednosti slucˇajne promen- ljive. Posebno ovaj problem se mozˇe iskoristiti u situacijama kada treba odrediti optimalni vremenski trenutak kada treba zapocˇeti neku aktivnost odrzˇavanja. U planiranju odrzˇavanja cˇesta je sledec´a situacija. Neki skup aktivnosti odrzˇavanja ima hijerarhijsku strukturu i pri tome je trajanje svake aktivnosti slucˇajna velicˇina. Pod pretpo- stavkom da aktivnost na viˇsem nivou hijerarhije ne mozˇe zapocˇeti pre nego sˇto su zavrsˇene sve aktivnosti na nizˇem nivou hijerarhije i da su poznati gubici koji nastaju u slucˇaju da se sa nekim aktivnostima kasni, odnosno da su poznati gubici u slucˇaju da su neke aktivnosti preuranjene, potrebno je formirati optimalnu strategiju aktiviranja aktivnosti iz datog skupa. Bez gubitka opsˇtosti mozˇemo pretpostaviti da su te aktivnosti vezane za proces sklapanja (pripreme) rezervnog dela koji je opisan odgovarajuc´im stablom sklapanja. Dakle u kontekstu sklapanja rezervnih delova problem je sledec´i. Zahteva se da neki finalni sklop (rezervni deo) bude sklopljen (raspolozˇiv) u datom vremenskom trenutku. Neka su aktivnosti sklapanja (pripreme) datog finalnog sklopa opisane stablom sklapanja. Vreme potrebno za sklapanje svakog od podsklopova je slucˇajna velicˇina. Sklapanje nadsklopa ne mozˇe zapocˇeti pre nego sˇto su svi podsklopovi raspolozˇivi. U slucˇaju da je neki podsklop sklopljen ranije javic´e se trosˇkovi skladiˇstenja. Ako je finalni sklop sklopljen pre utvrdenog roka javic´e se trosˇkovi skladiˇstenja, slicˇno ako je sklapanje finalnog sklopa zavrsˇeno nakon utvrdenog roka javic´e se trosˇkovi kasˇnjenja. Potrebno je odrediti optimalne vremenske trenutke aktiviranja faza sklapanja pojedinih podsklopova tako da se sklapanje finalnog sklopa zavrsˇi uz minimalne trosˇkove. Problem o kome je recˇ je u susˇtini isuviˇse komplikovan u opsˇtem slucˇaju, kada je proces sklapanja opisan stablom sklapanja proizvoljnog nivoa. Problem se znacˇajno uprosˇc´ava ako se resˇenje problema za stablo visine jedan iterativno primeni na podstblima datog stabla sklapanja proizvoljnog nivoa. Na ovaj nacˇin se resˇenje jednostavnijeg problema na stablu visine jedan mozˇe na odgovarajuc´i nacˇin produzˇiti na stabla sklapanja proizvoljne visine. 48 Planiranje odrzˇavanja vazduhoplova Uvodna razmatranja Primeri takvih istrazˇivanja su [30], koji obradjuje slicˇan problem u sistemu sklapanja sa dva odnosno tri nivoa, pri tome je glavna potesˇkoc´a u ovom modelu predstavljanje funkcije cilja u konacˇnom obliku za sisteme sklapanja nivoa vec´eg od tri. U [8], je razvijena rekurzivna sˇema za efikasno izracˇunavanje funkcije cilja u sistemima sklapanja proizvoljnog nivoa. Primeri radova koji analiziraju slicˇne probleme za jednostepene odnosno dvostepne sisteme su [6], [10] i [29]. Slicˇno resˇenje koje se sastoji u iterativnoj primeni resˇenja jednostavnijeg problema se mozˇe nac´i u [2]. 49 Planiranje odrzˇavanja vazduhoplova Newsboy model 3.2 Newsboy model U sistemima za odrzˇavanje vazduhoplova newsboy model se mozˇe direktno koristiti u slucˇajevima kada treba proceniti vremena isporuke odnosno vremena sklapanja rezervnih delova. Neka je poznat vremenski trenutak t0 kad je neophodno da rezervni deo bude raspolozˇiv i neka je slucˇajna promenljiva L vreme isporuke (lead time) rezervnog dela, odnosno vreme koje je potrebno da bi se sklopio zahtevani rezervni deo. U daljem tekstu c´emo podrazumevati da se rezervni delovi sklapaju, odnosno slucˇajna promenljiva L predstavlja vreme neophodno da bi se sklopio neki rezervni deo i bio raspolozˇiv za ugradnju. Prirodno je pretpostaviti da je vreme sklapanja L nenegativna ogranicˇena slucˇajna promenljiva. Potrebno je odrediti vremenski trenutak t∗0 kada treba zapocˇeti proces sklapanja rezervnog dela. Neka je vremenski trenutak t∗0 odreden na neki nacˇin, slucˇajna promenljiva t∗0 + L predstavlja vremenski trenutak kada je rezervni deo raspolozˇiv. Neka su pri tom poznati jedinicˇni trosˇkovi: − h skladiˇstenja rezervnog dela u slucˇaju da je realizovano vreme sklapanja takvo da je vremenski trenutak u kome je rezervni deo raspolozˇiv nastupio pre utvrdenog roka (holding cost) − b kasˇnjenja u slucˇaju da je realizovano vreme sklapanja takvo da je vremenski trenutak u kome je rezervni deo raspolozˇiv nastupio nakon utvrdenog roka (backlogging cost) Pretpostavimo da su trosˇkovi skladiˇstenja odnosno kasˇnjenja proporcionalni odstupanju pro- cene od realizovane vrednosti, odnosno pretpostavimo da su ovi trosˇkovi proporcinalni vre- menu cˇekanja na ugradnju odnosno vremenu kasˇnjenja ugradnje. Funkcija ukupnih trosˇkova C je u ovom slucˇaju jednaka: C = C(t∗0, t0, L) = h · (t0 − (t∗0 + L))+ + b · ((t∗0 + L)− t0)+ (3.1) = h · ((t0 − t∗0)− L)+ + b · (L− (t0 − t∗0))+ Oznacˇimo sa τ0 = t0 − t∗0, tada je: C = C(τ0, L) = h · (τ0 − L)+ + b · (L− τ0)+ (3.2) Ovaj model daje ukupne trosˇkove koji su rezultat procene slucˇajne promenljive L vrednosˇc´u τ0 = t0 − t∗0, sˇto je standardni newsboy model cˇije je resˇenje: F (τ∗) = b b+ h (3.3) odnosno: τ∗ = F−1 ( b b+ h ) (3.4) 50 Planiranje odrzˇavanja vazduhoplova Newsboy model gde je F funkcija raspodele slucˇajne promenljive L. Optimalni vremenski trenutak, kada treba zapocˇeti sklapanje rezervnog dela je: t∗0 = t0 − F−1 ( b b+ h ) (3.5) 3.2.1 Jedna linija sklapanja Neka se proces sklapanja sastoji iz n > 1 faza koje se sekvencijalno izvrsˇavaju i neka je recˇ samo o jednoj liniji sklapanja. Pretpostavimo pri tom da nema skladiˇstenja izmedu pojedinih faza sklapanja, odnosno sa zavrsˇetkom jedne faze aktivira se sledec´a faza sklapanja (3.1). Slika 3.1: Jedna linija sklapanja Neka je Li, i = 1, 2, . . . , n niz slucˇajnih promenljivih koje predstavljaju vremena trajanja i-te faze respektivno, tada je ukupno vreme sklapanja slucˇajna promenljiva: L = n∑ i=1 Li (3.6) Resˇenje ovog problema je dato sa: t∗0 = t0 − F−1L ( b b+ h ) (3.7) gde je FL funkcija raspodele slucˇajne promenljive (3.6). Problem odredivanja raspodele sume slucˇajnih promenljivih je u opsˇtem slucˇaju slozˇen, ali se mozˇe uprostiti ako uvedemo dodatne pretpostavke o nizu slucˇajnih promenljivih Li, i = 1, 2, . . . , n. Pretpostavimo da vazˇi: F−1∑ i Li = ∑ i F−1Li (3.8) sˇto odgovara linearnosti i aditivnosti vremena u procesu odrzˇavanja. Uslov (3.8) vazˇi ako 51 Planiranje odrzˇavanja vazduhoplova Newsboy model postoji slucˇajna promenljiva X takva da je: Li = αiX,αi ∈ R, i = 1, 2, . . . , n (3.9) i u tom slucˇaju resˇenje problema linijskog procesa sklapanja je dato sa: t∗0 = t0 − n∑ i=1 F−1Li ( b b+ h ) (3.10) Pod odredenim uslovima raspodela slucˇajne promenljive (3.6) mozˇe se odrediti koriˇsc´enjem Centralne Granicˇne Teoreme [1]. 3.2.2 Viˇsestruka neodredenost Neka je poznat vek trajanja datog rezervnog dela i neka je to slucˇajna promenljiva X i neka je ocˇekivani vek trajanja rezervnog dela E(X). To znacˇi da c´e u nekom trenutku biti neop- hodna zamena datog rezervnog dela, odnosno dati rezervni deo mora biti raspolozˇiv u nekom vremenskom trenutku. Ekonomski je neopravdano istovremeno sa ugradnjom rezervnog dela, obezbediti jedan ili viˇse primeraka koji bi se skladiˇstili do trenutka otkaza ugradenog dela kada treba izvrsˇiti zamenu. Ako belezˇimo trenutak ugradnje tu rezervnog dela tada slucˇajna promenljiva T = tu + X predstavlja trenutak otkaza ugradenog rezervnog dela, odnosno trenutak kada rezervni deo mora biti raspolozˇiv. Jedna od procena trenutka otkaza je: t0 = E(T ) = tu + E(X) (3.11) Ako iskoristimo klasicˇan newsboy problem dobic´emo funkciju ukupnih trosˇkova C: C = C(t∗0, t0, L) = h · (t0 − (t∗0 + L))+ + b · ((t∗0 + L)− t0)+ (3.12) Potrebno je odrediti optimalni vremenski trenutak t∗0 kada treba zapocˇeti proces sklapanja datog rezervnog dela. Ako dozvolimo da utvrdeni rok t0 mozˇe biti slucˇajna promenljiva doc´i c´emo do jednog uopsˇtenja klasicˇnog newsboy modela. Dakle neka je i utvrdeni rok slucˇajna promenljiva T , funkcija ukupnih trosˇkova C postaje: C = C(t∗0, T, L) = h · (T − (t∗0 + L))+ + b · ((t∗0 + L)− T )+ (3.13) Neka je t0 = E(T ) C = C(t∗0, T, L) = h · (t0 + (T − t0)− (t∗0 + L))+ + b · ((t∗0 + L)− (t0 + (T − t0)))+ (3.14) = h · ((t0 − t∗0)− (L− (T − t0)))+ + b · ((L− (T − t0))− (t0 − t∗0))+ Oznacˇimo sa τ0 = t0 − t∗0 i ∆ = T − t0, tada je funkcija ukupnih trosˇkova: 52 Planiranje odrzˇavanja vazduhoplova Newsboy model C = C(τ0,∆, L) = C(τ0, L−∆) (3.15) = h · (τ0 − (L−∆))+ + b · ((L−∆)− τ0)+ sˇto je klasicˇan newsboy model . Njegovo resˇavanje se svodi na odredivanje raspodele slucˇajne promenljive L−∆. Kako postoji veza izmedu gustina raspodela razlike nezavisnih slucˇajnih promenljivih [1]: fL−∆(t) = +∞∫ −∞ fL(t+ x)f∆(x)dx (3.16) mozˇe se odrediti funkcija raspodele FL−∆ razlike nezavisnih slucˇajnih promenljivih L−∆ FL−∆(t) = +∞∫ −∞ FL(t+ x)f∆(x)dx (3.17) dalje se optimalna vrednost: t∗0 = t0 − F−1L−∆ ( b b+ h ) (3.18) mozˇe odrediti numericˇkim metodama. 53 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I 3.3 Simultani zahtev I Razmotrimo sada opsˇtiji problem kada n > 1 rezervnih delova treba simultano obezbediti u datom vremenskom trenutku. Neka je proces sklapanja rezervnog dela opisan stablom visine dva (3.2). R0 R1 R2 Ri. . . . . . Rn Slika 3.2: Stablo sklapanja visine 2 Kako u ovoj situaciji rezervni deo ima neku strukturu u daljem tekstu c´emo za rezervni deo u zavisnosti od uloge u uocˇenoj strukturi koristiti termine sklop, podsklop ili nadsklop. Neka je t0 vremenski trenutak kada finalni sklop mora biti raspolozˇiv. Neka je vreme sklapanja finalnog sklopa modelirano slucˇajnom promenljivom L sa funkcijom raspodele F i neka su dalje h i b, trosˇkovi skladiˇstenja odnosno kasˇnjenja finalnog sklopa. Ovo je klasicˇan newsboy problem i njegovim resˇavanjem se dobija vremenski trenutak t∗0 kada treba zapocˇeti sklapa- nje finalnog sklopa. Ako pretpostavimo da proces sklapanja nadsklopa mozˇe zapocˇeti tek nakon sˇto su svi podsklopovi raspolozˇivi, vremenski trenutak t∗0 je simultani rok do koga svi podsklopovi finalnog sklopa moraju biti raspolozˇivi. Neka je sklapanje i-tog podsklopa zapocˇeto u trenutku ti, i = 1, 2, . . . , n, a vreme potrebno za sklapanje i-tog podsklopa nepre- kidna slucˇajna promenljiva Li, i = 1, 2, . . . , n, sa funkcijom raspodele Fi i funkcijom gustine fi. Vremenski trenutak kada je i-ti podsklop sklopljen je Ti = ti + Li, i = 1, 2, . . . , n, a faza sklapanja podsklopova je zavrsˇena u trenutku kada je i poslednji podsklop sklopljen, odnosno u trenutku Tz = max i {Ti}. Kako bi obezbedili da se proces sklapanja zavrsˇava u konacˇnom vremenu, pretpostavic´emo da su vremena sklapanja Li, i = 1, 2, . . . , n nenegativne ogranicˇene slucˇajne promenljive. U konacˇnom trenutku Tz svi podsklopovi su raspolozˇivi i mozˇe zapocˇeti faza sklapanja nadsklopa, posebno ako je i-ti podsklop sklopljen u trenutku Ti < Tz, i = 1, 2, . . . , n, on se svakako mora skladiˇstiti do trenutka Tz. Pretpostavic´emo da su jedinicˇni trosˇkovi skladiˇstenja i-tog podsklopa jednaki hi i da su proporcionalni periodu skladiˇstenja (Tz − Ti), i = 1, 2, . . . , n. Dakle svaki podsklop se od trenutka Ti kada je sklo- pljen, do trenutka Tz kada su svi podsklopovi sklopljeni, pojedinacˇno skladiˇsti i odgovarajuc´e trosˇkove skladiˇstenja hi(Tz −Ti), i = 1, 2, . . . , n c´emo zvati pojedinacˇni trosˇkovi skladiˇstenja. Zbog prirode procesa sklapanja pojedinacˇni trosˇkovi kasˇnjenja ne figuriˇsu u ovom modelu, odnosno ne postoji podsklop cˇije je sklapanje zavrsˇeno nakon trenutka Tz kada je moguc´e zapocˇeti sklapanje nadsklopa. Faza sklapanja podsklopova je modelirana grupnom karakte- ristikom Tz = max i {Ti}, pa u zavisnosti od odnosa ove velicˇine i predvidenog roka t∗0 javic´e se grupni trosˇkovi: − Tz < t∗0 - podsklopovi su sklopljeni pre predvidenog roka t∗0. Odgovarajuc´e trosˇkove 54 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I c´emo zvati grupni trosˇkovi skladiˇstenja. Slicˇno kao kod pojedinacˇnih trosˇkova skladiˇstenja, pretpostavimo da su jedinicˇni trosˇkovi grupnog skladiˇstenja jednaki hˆ i neka su propor- cionalni vremenu grupnog skladiˇstenja (t∗0 − Tz) (3.3). − Tz > t∗0 - podsklopovi su sklopljeni nakon predvidenog roka t∗0. Odgovarajuc´e trosˇkove c´emo zvati grupni trosˇkovi kasˇnjenja. Neka su jedinicˇni trosˇkovi grupnog kasˇnjenja jednaki bˆ i neka su proporcionalni vremenu grupnog kasˇnjenja (Tz − t∗0) (3.4). Slika 3.3: Grupno skladiˇstenje Iz ove analize izvodi se funkcija ukupnih trosˇkova: C = C(t1, . . . , tn, t ∗ 0, L1, . . . , Ln) = hˆ(t∗0 − Tz)+ + n∑ i=1 hi(Tz − Ti) + bˆ(Tz − t∗0)+ (3.19) Uzimajuc´i u obzir cˇinjenicu da su trosˇkovi kasˇnjenja samo grupni trosˇkovi kasˇnjenja, u daljem tekstu c´emo koristiti termin trosˇkovi kasˇnjenja podrazumevajuc´i grupne trosˇkove kasˇnjenja. Slicˇno koristic´emo termin trosˇkovi koji mozˇe u zavisnosti od konteksta podrazumevati je- dinicˇne trosˇkove. Problem je sledec´i odrediti vremenske trenutke ti, i = 1, 2, . . . , n, kada treba zapocˇeti proces sklapanja i-tog podsklopa kako bi, kada su svi podsklopovi sklopljeni u trenutku Tz, ocˇekivani ukupni trosˇkovi koji su posledica odstupanja od predvidenog roka t ∗ 0 bili minimalni. Kako bi obezbedili da nasˇ problem ima jedinstveno resˇenje uvodic´emo neop- 55 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I Slika 3.4: Grupno kasˇnjenje hodne pretpostavke koje c´e obezbediti konveksnost funkcije [3] ocˇekivanih ukupnih trosˇkova, a time i jedinstvenost resˇenja. Primetimo da funkcija ukupnih trosˇkova izmedju ostalih ukljucˇuje i parametre jedinicˇnih trosˇkova i to: − jedinicˇne trosˇkove pojedinacˇnog skladiˇstenja podsklopova hi, i = 1, 2, . . . , n − jedinicˇne trosˇkove grupnog skladiˇstenja hˆ − jedinicˇne trosˇkove grupnog kasˇnjenja bˆ. Prirodno je pretpostaviti da su poznati samo jedinicˇni trosˇkovi pojedinacˇnog skladiˇstenja podsklopova, a da su parametri grupnih trosˇkova hˆ i bˆ funkcije jedinicˇnih trosˇkova h i b na nadsklopu (u ovom slucˇaju radi se o finalnom sklopu). Opravdano je pretpostaviti da c´e kasˇnjenje za vremenski period (Tz − t∗0)+ na podsklopovima proizvesti isto kasˇnjenje na nadsklopu odnosno, trosˇkovi kasˇnjenja na podsklopovima proizvode iste trosˇkove kasˇnjenja na nadredjenom sklopu. Dakle, opravdano je pretpostaviti: bˆ(Tz − t∗0)+ = b(Tz − t∗0)+ odnosno jedinicˇni trosˇkovi kasˇnjenja bˆ na neposrednim podsklopovima finalnog sklopa su jednaki jedinicˇnim trosˇkovima kasˇnjenja b finalnog sklopa (3.5) odnosno: bˆ = bˆ(L1, . . . , Ln, b) = b 56 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I Slika 3.5: Grupno kasˇnjenje Sa ovim pretpostavkama funkcija ukupnih trosˇkova na nivou neposrednih podsklopova final- nog sklopa je: C = C(t1, τ2, . . . , tn, t ∗ 0, L1, . . . , Ln) = hˆ(t∗0 − Tz)+ + n∑ i=1 hi(Tz − Ti) + b(Tz − t∗0)+ (3.20) Ostaje da na neki nacˇin definiˇsemo jedinicˇne trosˇkove grupnog skladiˇstenja: hˆ = hˆ(h1, h2, . . . , hn, L1, . . . , Ln, h) na nivou neposrednih podsklopova finalnog sklopa. Pretpostavimo da se proces sklapanja izvodi na sledec´i nacˇin, sklopljeni podsklopovi se uvek skladiˇste do predvidenog roka t∗0, bez obzira sˇto je sklapanje svih podsklopova zavrsˇeno pre predvidenog roka t∗0. Drugim recˇima nema trosˇkova grupnog skladiˇstenja, sva skladiˇstenja su pojedinacˇnog tipa tj. svaki sklopljeni podsklop se skladiˇsti do predvidenog roka t∗0 sa svojim jedinicˇnim trosˇkovima hi (3.6). Dakle pretpostavimo sledec´e: hˆ(t∗0 − Tz)+ = n∑ i=1 hi(t ∗ 0 − Tz)+ (3.21) 57 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I odnosno: hˆ = hˆ(h1, h2, . . . , hn, L1, . . . , Ln, h) = n∑ i=1 hi (3.22) Slika 3.6: Grupno skladiˇstenje Funkcija ukupnih trosˇkova C = C(t1, t2, . . . , tn, t ∗ 0, L1, . . . , Ln) je u ovom slucˇaju: C = n∑ i=1 hi(t ∗ 0 − Tz)+ + n∑ i=1 hi(Tz − Ti) + b(Tz − t∗0)+ = n∑ i=1 hi(t ∗ 0 − Tz) + n∑ i=1 hi(Tz − Ti) + ( b+ n∑ i=1 hi ) (Tz − t∗0)+ (3.23) = n∑ i=1 hi(t ∗ 0 − Ti) + ( b+ n∑ i=1 hi ) (Tz − t∗0)+ Kako je Ti = ti + Li, odnosno Tz = max i {Ti}, dobijamo: C = n∑ i=1 hi(t ∗ 0 − ti − Li) + ( b+ n∑ i=1 hi )( max i {ti + Li − t∗0} )+ (3.24) Uvedimo sledec´u oznaku τi = t ∗ 0 − ti, i = 1, 2, . . . , n i imac´emo: 58 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I C = C(τ1, τ2, . . . , τn, L1, . . . , Ln) = n∑ i=1 hi(τi − Li) + ( b+ n∑ i=1 hi )( max i {Li − τi} )+ (3.25) Ocˇekivani ukupni trosˇkovi Z = E(C) = Z(τ1, τ2, . . . , τn) su: Z = n∑ i=1 hi(τi − E(Li)) + ( b+ n∑ i=1 hi ) E ( (max i {Li − τi})+ ) (3.26) Iz ove forme funkcije Z se direktno mozˇe utvrditi egzistencija globalnog minimuma odnosno vazˇi sledec´i stav: Teorema 3.3.1. Funkcija ocˇekivanih trosˇkova Z = E(C) = Z(τ1, τ2, . . . , τn) data sa (3.26) ima globalni minimum u konacˇnoj tacˇki (τ∗1 , τ∗2 , . . . , τ∗n). Dokaz. Pokazˇimo prvo da je funkcija ukupnih trosˇkova Z data sa (3.26) konveksna funkcija svojih argumenata τ1, τ2, . . . , τn. Prvi sabirak: n∑ i=1 hi (τi − E(Li)) (3.27) je linearna dakle konveksna funkcija argumenata τ1, τ2, . . . , τn, dok konveksnost drugog sa- birka: ( b+ n∑ i=1 hi ) E ( (max i {Li − τi} )+ ) (3.28) sledi iz iz monotonosti i linearnosti ocˇekivanja i konveksnosti maksimuma konveksnih funk- cija. Dakle data funkcija ukupnih trosˇkova Z je konveksna funkcija kao zbir konveksnih funkcija. Sa druge strane mozˇemo zakljucˇiti sledec´e: • τi → +∞⇒ Z ∼ hiτi → +∞ • τi → −∞⇒ Z ∼ hiτi − τi ( b+ n∑ i=1 hi ) = −τi ( b+ ( n∑ i=1 hi ) − hi ) = −τi b+ n∑ j 6=i hj → +∞ odnosno: limτi→±∞Z = +∞ (3.29) Navedene osobine konveksne funkcije ocˇekivanih trosˇkova obezbeduju egzistenciju lokalnog mi- nimuma u konacˇnoj tacˇki (τ∗1 , τ∗2 , . . . , τ∗n), koji c´e biti i globalni minimum [2] [9] [26]. 59 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I  Razvijmo dalje funkciju ocˇekivanih trosˇkova. Pre svega neophodno je odrediti funkciju ras- podele slucˇajne promenljive D+: D+ = ( max i {Li − τi} )+ = max { max i {Li − τi} , 0 } (3.30) Neka je t > 0, funkcija raspodele FD+ slucˇajne promenljive D + je: FD+(t) = P (D + < t) = P ( max { max i {Li − τi} , 0 } < t ) = P ( max i {Li − τi} < t ) (3.31) = P (⋂ i (Li − τi < t) ) = ∏ i P (Li < t+ τi) = ∏ i Fi(t+ τi) Ocˇekivanje E(D+) slucˇajne promenljive D+ se mozˇe odrediti kao ocˇekivanje nenegativne slucˇajne promenljive [1]: E(D+) = +∞∫ 0 P (D+ ≥ t)dt = +∞∫ 0 ( 1− P (D+ < t)) dt = +∞∫ 0 (1− FD+(t)) dt = +∞∫ 0 ( 1− ∏ i Fi(t+ τi) ) dt (3.32) Sada mozˇemo dati funkciju ocˇekivanih ukupnih trosˇkova u razvijenom obliku: Z(τ1, τ2, . . . , τn) = n∑ i=1 hi(τi − E(Li)) + ( b+ n∑ i=1 hi )+∞∫ 0 ( 1− ∏ i Fi(t+ τi) ) dt (3.33) Stacionarna tacˇka funkcije Z je resˇenje sledec´eg sistema jednacˇina: ∂Z ∂τi = hi + ( b+ n∑ i=1 hi ) ∂ ∂τi +∞∫ 0 ( 1− ∏ i Fi(t+ τi) ) dt  = 0, i = 1, 2, .., n (3.34) dalje pretpostavimo uslove o funkcijama raspodele Fi, i = 1, 2, . . . , n tako da parcijalni izvod i integral komutiraju [25] i dobic´emo: 60 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I ∂Z ∂τi = hi + ( b+ n∑ i=1 hi )+∞∫ 0 ∂ ∂τi ( 1− ∏ i Fi(t+ τi) ) dt = 0, i = 1, 2, .., n ∂Z ∂τi = hi − ( b+ n∑ i=1 hi )+∞∫ 0 fi(t+ τi) ∏ j 6=i Fj(t+ τj)dt = 0, i = 1, 2, .., n (3.35) Konacˇno stacionarne tacˇke su resˇenja sledec´eg sistema nelinearnih jednacˇina: +∞∫ 0 fi(t+ τi) ∏ j Fj(t+ τj)dt = hi b+ n∑ i=1 hi , i = 1, 2, .., n (3.36) Dobijeni sistem jednacˇina se mozˇe resˇiti numericˇkim metodama i neka su τ∗1 , τ∗2 , . . . , τ∗n, ove vrednosti. Na ovaj nacˇin su odredeni optimalni vremenski trenuci t∗i = t ∗ 0 − τi, i = 1, . . . , n, kada treba zapocˇeti sklapanje i-tog podsklopa tako da su ocˇekivani ukupni troskovi minimalni. Primer 3.3.1. Primetimo sledec´e, neka je n = 1 tada se stacionarna tacˇka, odnosno opti- malno resˇenje τ∗1 dobija kao resˇenje jednacˇine: +∞∫ 0 f1(t+ τ1)dt = h1 b+ h1 (3.37) kako je: +∞∫ 0 f1(t+ τ1)dt = +∞∫ τ1 f1(u)du = 1− F1(τ1), gornja jednacˇina postaje: 1− F1(τ1) = h1 b+ h1 F1(τ1) = 1− h1 b+ h1 = b b+ h1 (3.38) i njeno resˇenje je: τ∗1 = F −1 1 ( b b+ h1 ) (3.39) sˇto je resˇenje klasicˇnog newsboy problema na nivou podsklopa. Ovaj rezultat je ocˇekivan jer je pretpostavljeno sledec´e: − lokalno skladiˇstenje podsklopa sa jedinicˇnim trosˇkovima h1 − kasˇnjenje na nivou podsklopa c´e se reprodukovati na finalnom sklopu, dakle jedinicˇni trosˇkovi kasˇnjenja na nivou podsklopa su b 3.3.1 Stablo sklapanja sa viˇse nivoa I Neka je proces sklapanja rezervnog dela opisan stablom visine vec´e od dva. Na opisani nacˇin mi mozemo odrediti kriticˇna vremena t∗1, τ∗2 , . . . , t∗n na nivou neposrednih podsklopova 61 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I finalnog sklopa. Uocˇimo podstablo visine dva cˇiji je koren jedan od neposrednih podsklopova finalnog sklopa, neka je to i-ti (1 ≤ i ≤ n) podsklop. Formirajmo funkciju ukupnih trosˇkova (3.23) koji odgovaraju uocˇenom podstablu sklapanja: Ci = ∑ j (hi)j (t ∗ i − (Ti)j) + bˆi +∑ j (hi)j  ((Ti)z − t∗i )+ (3.40) gde su: − t∗i - utvrdeni rok za simultanu raspolozˇivost podsklopova i-tog podsklopa − (Ti)j - trenutak raspolozˇivosti pojedinih podsklopova i-tog podsklopa − (Ti)z - simultana raspolozˇivost podsklopova i-tog podsklopa − (hi)j - jedinicˇni trosˇkovi skladiˇstenja pojedinih podsklopova i-tog podsklopa − bˆi - grupni trosˇkovi kasˇnjenja i-tog podsklopa Da bismo navedni postupak sproveli na ovom stablu sklapanja, neophodno je proceniti je- dinicˇne trosˇkove kasˇnjenja bˆi i-tog (1 ≤ i ≤ n) podsklopa koji je u korenu ovog podstabla. Jedno resˇenje je da se izvrsˇi raspodela trosˇkova kasˇnjenja bˆ nadsklopa u ovom slucˇaju finalnog sklopa bˆ = b, na trosˇkove kasˇnjenja njegovih neposrednih podsklopova. Analizirajmo trosˇkove kasˇnjenja nadsklopa: B = bˆ(Tz − t∗0)+ (3.41) Svaki od podsklopova ima svoj udeo Bi = bˆi(Tz−t∗0)+ u ukupnim trosˇkovima kasˇnjenja. Odre- dimo trosˇkove kasˇnjenja i-tog podsklopa bˆi. Neka se sklapanje i-tog (1 ≤ i ≤ n) podsklopa pokrene u nekom trenutku ti + ∆ti za proizvoljno mali vremenski period ∆ti. Pretpostavimo Tz ≥ t∗0 (u suprotnom nema trosˇkova kasˇnjenja niti ikakve promene za dovoljno malo ∆ti). U situaciji kao na slici (3.7) promena trosˇkova kasˇnjenja je: ∆iB = ∆ti bˆ; Ti = Tz0; Ti < Tz (3.42) pa za jedinicˇne trosˇkove kasˇnjenja bˆi i-tog (1 ≤ i ≤ n) podsklopa mozˇemo uzeti ocˇekivanje slucˇajne promenljive ∆iB ∆ti , odnosno bˆi = E ( ∆iB ∆ti ) = bˆP (Ti = Tz). Primer 3.3.2. Primetimo sledec´e, u slucˇaju da nadsklop ima tacˇno jedan podsklop, tj. n = 1, kako je T1 = Tz bic´e: bˆ1 = bˆ · 1 = bˆ (3.43) sˇto je i logicˇno, jer u slucˇaju jedne linije sklapanja kasˇnjenje u podfazi sklapanja rezultuje istim kasˇnjenjem u zavrsˇnoj fazi sklapanja, pa su i jedinicˇni trosˇkovi kasˇnjenja u podfazama sklapanja jednaki jedinicˇnim trosˇkovima kasˇnjenja u zavrsˇnoj fazi sklapanja. Josˇ viˇse, neka se 62 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I Slika 3.7: Promena trosˇkova kasˇnjenja kasni sa sklapanjem svakog od podsklopova za neki vremenski period ∆t. Ocˇigledno sa jedne strane kasnic´e se sa sklapanjem nadsklopa za isti vremenski period ∆t odnosno trosˇkovi kasˇnjenja c´e se uvec´ati za iznos bˆ∆t, sa druge strane predlozˇeni model ukljucˇuje uvec´anje trosˇkova kasˇnjenja svakog podsklopa za iznos bˆi∆t = bˆP (Ti = Tz) koji su u zbiru jednaki ocˇekivanom uvec´anju bˆ∆t: ∑ i bˆi∆t = ∑ i bˆP (Ti = Tz)∆t = bˆ∆t ∑ i P (Ti = Tz) = bˆ∆t (3.44) Drugim recˇima predlozˇeni model trosˇkova kasnjenja lokalno tretira trosˇkove kasˇnjenja koji se mogu pojaviti u narednoj fazi procesa sklapanja, a koji u toj fazi ne mogu biti tretirani. Na ovaj nacˇin smo pokazali da predlozˇeni model na adekvatan nacˇin pokriva navedeni granicˇni slucˇaj. Konacˇno, jedinicˇni trosˇkovi kasˇnjenja bˆi i-tog (1 ≤ i ≤ n) podsklopa su: 63 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I bˆi = E ( ∆iB ∆ti ) = bˆP (Ti = Tz) = bˆP (Ti = Tz) = bˆP ( Ti = max {Tj} j ) = bˆP ⋂ j 6=i (Ti > Tj)  = bˆ ∏ j 6=i P (Ti > Tj)  = bˆ ∏ j 6=i P (t∗i + Li > t ∗ j + Lj)  (3.45) = bˆ ∏ j 6=i P (Lj − Li < t∗i − t∗j )  = bˆ ∏ j 6=i FLj−Li(t ∗ i − t∗j )  gde je FLj−Li funkcija raspodele slucˇajne promenljive Lj − Li. Neka su poznati trosˇkovi kasˇnjenja svakog pojedinacˇnog podsklopa bˆi, sada mozˇemo formulisati problem odredjivanja kriticˇnih vremenskih trenutaka na svakom od podsklopova datog finalnog sklopa odnosno produzˇiti resˇenje problema odredjivanja kriticˇnih vremenskih trenutaka na procese sklapanja opisanim podstablima korena polaznog stabla sklapanja. Na ovaj nacˇin mozˇemo formulisati rekurzivnu proceduru proracˇuna vremena za proces skla- panja rezervnog dela koji se opisuje stablom sklapanja proizvoljne visine. Neka svaki cˇvor stabla sklapanja, koji predstavlja podsklop finalnog rezervnog dela, ima kao karakteristike je- dinicˇne trosˇkove skladiˇstenja h, jedinicˇne trosˇkove kasˇnjenja b, optimalni vremenski trenutak t∗ kada treba zapocˇeti sklapanje pridruzˇenog podsklopa i neprekidnu slucˇajnu promenljivu L 1, koja predstavlja vreme sklapanja pridruzˇenog podsklopa. Jasno je da su jedinicˇni trosˇkovi kasˇnjenja poznati samo za finalni rezervni deo, odnosno postoje samo u korenu stabla sklapa- nja. Problem je sledec´i, za zadani kriticˇni vremenski trenutak t do kog rezervni deo mora biti sklopljen, odrediti optimalne vremenske trenutke t∗svakog od podsklopova finalnog rezervnog dela, kada treba zapocˇeti njegovo sklapanje. Optimalni vremenski trenutak t∗, koji odgovara finalnom rezervnom delu odnosno, korenu stabla sklapanja se odredjuje resˇavanjem klasicˇnog newsboy problema, a to je prakticˇno kriticˇni vremenski trenutak za simultanu raspolozˇivost njegovih direktnih podsklopova. Dakle mozˇemo pretpostaviti da stablo sklapanja rezervnog dela u korenu ima postavljene izmedu ostalih sledec´e velicˇine: optimalni vremenski trenutak t∗ i jedinicˇne trosˇkove kasˇnjenja b. Koren ovakvog stabla sklapanja je ulazni parametar za rekurzivnu proceduru koja resˇava problem odredjivanja optimalnih vremenskih trenutaka za stablo sklapanja proizvoljne visine. Koraci pomenute rekurzivne procedure su: − Ako je dati podsklop koren nekog podstabla sklapanja visine jedan, odnosno ako pod- sklop nema svojih podsklopova procedura je zavrsˇena. − Za dati podsklop koji je koren nekog podstabla sklapanja, koristec´i izmedu ostalog optimalni vremenski trenutak t∗ i jedinicˇne trosˇkove kasˇnjenja bˆ, resˇavanjem sistema jednacˇina (3.36) odredjuju se optimalni vremenski trenuci t∗1, . . . , t∗n koji odgovaraju nje- govim direktnim podsklopovima. Slicˇno koristec´i jednacˇine (3.45) odredjuju se jedinicˇni trosˇkovi kasˇnjenja bˆ1, . . . , bˆn koji odgovaraju njegovim direktnim podsklopovima. 1Dovoljno je cˇvoru pridruzˇiti funkciju raspodele F odnosno gustine f slucˇajne promenljive L 64 Planiranje odrzˇavanja vazduhoplova Simultani zahtev I − Rekurzivno se izvrsˇava procedura na svakom direktnom podsklopu. Rekurzivnost se mozˇe na jednostavan nacˇin izbec´i. Stablo sklapanja se prolazi po nivoima pocˇevsˇi od korena. Primer 3.3.3. Razmotrimo problem proracˇuna vremena u slucˇaju da postoji samo jedna linija sklapanja, odnosno svako podstablo sklapanja ima tacˇno jednu granu, u predlozˇenom modelu n = 1. Ovaj process se opisuje stablom koje je lanac. Neka je recˇ o lancu duzˇine m > 1 (3.8). Slika 3.8: Jedna linija sklapanja Primetili smo da se u slucˇaju jedne linije sklapanja trosˇkovi kasˇnjenja sa finalnog sklopa prenose na podsklopove, odnosno bˆi = bˆ = b, i = 0, 1, 2, . . . ,m − 1. U pojedinim fazama sklapanja i = 0, 1, . . . ,m− 1 ukupni trosˇkovi su: Ci = hi(ti − Ti)+ + b(Ti − t∗0)+ a ovo je klasicˇan newsboy model, cˇije je resˇenje ti+1 = t ∗ i = ti − F−1i ( b b+ hi ) . Konacˇno resˇenje je: tm = tm−1 − F−1m−1 ( b b+ hm−1 ) = tm−2 − F−1m−2 ( b b+ hm−2 ) − F−1m−1 ( b b+ hm−1 ) = . . . = t0 − m−1∑ i=0 F−1i ( b b+ hi ) 65 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II 3.4 Simultani zahtev II Neka je proces sklapanja rezervnog dela opisan stablom visine dva (3.9). R0 R1 R2 Ri. . . . . . Rn Slika 3.9: Stablo sklapanja visine 2 Za dati vremenski trenutak t0 kada finalni rezervni deo treba da bude sklopljen, treba odrediti optimalni vremenski trenutak t∗0, kada treba zapocˇeti proces sklapanja rezervnog dela. Neka su poznati jedinicˇni trosˇkovi skladiˇstenja h, jedinicˇni trosˇkovi kasˇnjenja b i funkcija raspodele F slucˇajne promenljive L koja predstavlja vreme sklapanja rezervnog dela. Ovo je klasicˇan newsboy problem i optimalni vremenski trenutak se odreduje na sledec´i nacˇin: t∗0 = t0 − F−1 ( b b+ h ) (3.46) Da bi se proces sklapanja odvijao po optimalnoj putanji, ocˇigledno svi podsklopovi rezervnog dela moraju biti raspolozˇivi u vremenskom trenutku t∗0. Na ovaj nacˇin dolazimo do problema simultane raspolozˇivosti. Vreme sklapanja i-tog i = 1, 2, . . . , n podsklopa je neprekidna slucˇajna promenljiva Li. Od trenutka kada je podsklop sklopljen do trenutka kada se zapocˇinje sklapanje nadsklopa, podsklop se skladiˇsti. Jedinicˇni trosˇkovi skladiˇstenja i-tog podsklopa su hi. Treba odrediti optimalne vremenske trenutke t ∗ 1, . . . , t ∗ n, kada treba zapocˇeti proces sklapanja svakog pojedinacˇog podsklopa. Pretpostavimo da sklapanje nadsklopa ne mozˇe zapocˇeti pre nego sˇto su svi podsklopovi sklopljeni. Funkcija ukupnih trosˇkova je (3.20): C = C(t1, . . . , tn, t ∗ 0, L1, . . . , Ln) = hˆ(t∗0 − Tz)+ + n∑ i=1 hi(Tz − Ti) + b(Tz − t∗0)+ (3.47) gde su sa hˆ oznacˇeni jedinicˇni trosˇkovi grupnog skladiˇstenja. U prethodnoj analizi (3.3) pret- postavili smo da se podsklopovi pored toga sˇto se skladiˇste do trenutka Tz kada mozˇe zapocˇeti faza sklapanja nadsklopa, pojedinacˇno skladiste do predvidenog roka t∗0 ako je sklapanje svih podsklopova zavrsˇeno pre utvrdenog roka odnosno, hˆ = n∑ i=1 hi za Tz < t ∗ 0. Uzimajuc´i ove pretpostavke u obzir funkcija ukupnih trosˇkova je: 66 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II C = n∑ i=1 hi(t ∗ 0 − Tz)+ + n∑ i=1 hi(Tz − Ti) + b(Tz − t∗0)+ = n∑ i=1 hi(t ∗ 0 − Ti) + ( b+ n∑ i=1 hi ) (Tz − t∗0)+ (3.48) Pretpostavimo sada drugu krajnost, nema nepotrebnog skladiˇstenja, odnosno u trenutku Tz kada su svi podsklopovi raspolozˇivi zapocˇinje sklapanje nadsklopa (3.10): Slika 3.10: Grupno skladiˇstenje Postavlja se pitanje kako ovu situaciju ugraditi u funkciju ukupnih trosˇkova. Kako sklapanje nadsklopa zapocˇinje pre predvidenog roka (Tz < t ∗ 0) opravdana je pretpostavka da c´e nadsklop biti sklopljen pre utvrdenog roka, odnosno prevremeno aktiviranje faze sklapanja nadsklopa c´e proizvesti trosˇkove skladiˇstenja nadsklopa h(t∗0 − Tz). Dakle pretpostavimo: hˆ(t∗0 − Tz) = h(t∗0 − Tz) (3.49) odnosno jedinicˇni trosˇkovi grupnog skladiˇstenja hˆ na neposrednim podsklopovima finalnog sklopa su jednaki jedinicˇnim trosˇkovima skladiˇstenja h finalnog sklopa: hˆ = hˆ(h1, h2, . . . , hn, L1, . . . , Ln, h) = h (3.50) Pretpostavimo josˇ da su sumarni troskovi skladiˇstenja podsklopova vec´i od trosˇkova skladiˇstenja 67 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II nadsklopa odnosno: n∑ i=1 hi ≥ h (3.51) Dakle uz ove pretpostavke funkcija ukupnih troskova je: C = h(t∗0 − Tz)+ + n∑ i=1 hi(Tz − Ti) + b(Tz − t∗0)+ (3.52) Transformiˇsimo gornji izraz u pogodniji oblik, iz koga c´e se dobiti oblik funkcije ocˇekivanih trosˇkova iz koga se relativno lako mozˇe utvrditi njena konveksnost [3] i ustanoviti egzistencija njenog globalnog minimuma: C = h(t∗0 − Tz) + n∑ i=1 hi(Tz − Ti) + (b+ h)(Tz − t∗0)+ = h(t∗0 − Tz) + n∑ i=1 hi ((Tz − t∗0)− (Ti − t∗0)) + (b+ h)(Tz − t∗0)+ = ( n∑ i=1 hi − h ) (Tz − t∗0)− n∑ i=1 hi(Ti − t∗0) + (b+ h)(Tz − t∗0)+ (3.53) = ( n∑ i=1 hi − h ) (Tz − t∗0) + n∑ i=1 hi(t ∗ 0 − Ti) + (b+ h)(Tz − t∗0)+ kako je Ti = ti + Li, odnosno Tz = max i {Ti}, dobijamo: C = ( n∑ i=1 hi − h )( max i {ti + Li − t∗0} ) + n∑ i=1 hi(t ∗ 0 − ti − Li) +(b+ h) ( max i {ti + Li − t∗0} )+ (3.54) na kraju, oznacˇimo τi = t ∗ 0 − ti, i = 1, 2, . . . , n, pa je funkcija ukupnih trosˇkova: C = C(τ1, τ2, . . . , τn, L1, . . . , Ln) = ( n∑ i=1 hi − h ) max i {Li − τi}+ n∑ i=1 hi(τi − Li) (3.55) +(b+ h) ( max i {Li − τi} )+ 68 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II Ocˇekivani ukupni trosˇkovi Z = E(C) = Z(τ1, τ2, . . . , τn) su: Z = ( n∑ i=1 hi − h ) E ( max i {Li − τi} ) + n∑ i=1 hi (τi − E(Li)) + (b+ h)E ( (max i {Li − τi})+ ) (3.56) Na isti nacˇin kao sˇto je to vec´ uradeno u prethodnoj analizi (3.3.1) mozˇemo zakljucˇiti da funkcija ocˇekivanih ukupnih trosˇkova Z ima globalni minimum u konacˇnoj tacˇki. Teorema 3.4.1. Funkcija ocˇekivanih ukupnih trosˇkova Z = E(C) = Z(τ1, τ2, . . . , τn) data sa (3.56) ima globalni minimum u konacˇnoj tacˇki (τ∗1 , τ∗2 , . . . , τ∗n). Dokaz. Pokazˇimo prvo da je funkcija ukupnih trosˇkova Z data sa (3.56) konveksna funkcija svojih argumenata τ1, τ2, . . . , τn. Drugi sabirak n∑ i=1 hi (τi − E(Li)) (3.57) je linearna dakle konveksna funkcija argumenata τ1, τ2, . . . , τn dok konveksnost prvog odnosno trec´eg sabirka: ( n∑ i=1 hi − h ) E ( max i {Li − τi} ) (3.58) (b+ h)E ( (max i {Li − τi})+ ) (3.59) sledi iz iz monotonosti i linearnosti ocˇekivanja i konveksnosti maksimuma konveksnih funk- cija. Dakle data funkcija ukupnih trosˇkova Z je konveksna funkcija kao zbir konveksnih funkcija. Sa druge strane mozˇemo zakljucˇiti sledec´e: • τi → +∞⇒ Z ∼ hiτi → +∞ • τi → −∞⇒ Z ∼ −τi ( n∑ i=1 hi − h ) + hiτi − τi(b+ h) = −τi ( b+ ( n∑ i=1 hi ) − hi ) = −τi b+ n∑ j 6=i hj → +∞ odnosno: limτi→±∞Z = +∞ Navedene osobine konveksne funkcije ocˇekivanih trosˇkova obezbeduju egzistenciju lokalnog mi- nimuma u konacˇnoj tacˇki (τ∗1 , τ∗2 , . . . , τ∗n), koji c´e biti i globalni minimum [2] [9] [26]. 69 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II  Razvijmo dalje funkciju ocˇekivanih trosˇkova. Pre svega neophodno je odrediti funkciju ras- podele slucˇajne promenljive: D = max i {Li − τi} (3.60) odnosno: D+ = max { max i {Li − τi} , 0 } (3.61) Kako je za odredivanje ocˇekivanja nenegativne slucˇajne promenljive dovoljno poznavanje njene funkcije raspodele [1], iskoristimo osobinu D = D+ −D− i imac´emo: Z = ( n∑ i=1 hi − h ) E(D) + n∑ i=1 hi (τi − E(Li)) + (b+ h)E(D+) = ( n∑ i=1 hi − h ) E(D+ −D−) + n∑ i=1 hi (τi − E(Li)) + (b+ h)E(D+) (3.62) = ( h− n∑ i=1 hi ) E(D−) + n∑ i=1 hi (τi − E(Li)) + ( b+ n∑ i=1 hi ) E(D+) Analogno kao sˇto je to uradeno za slucˇajnu promenljivu D+ nadimo ocˇekivanje slucˇajne pro- menljive D− = (max i {Li − τi})− = max { −max i {Li − τi} , 0 } . Kako se radi o nenegativnoj slucˇajnoj promenljivoj dovoljno je odrediti P (D− ≥ t). Neka je t > 0, imac´emo: P (D− ≥ t) = P (max { −max i {Li − τi} , 0 } ≥ t) = P ( −max i {Li − τi} ≥ t ) = P ( max i {Li − τi} ≤ −t ) = P (⋂ i (Li − τi ≤ −t) ) (3.63) = ∏ i P (Li ≤ τi − t) = ∏ i Fi(τi − t) pa je ocˇekivanje nenegativne slucˇajne promenljive D−: E(D−) = +∞∫ 0 P (D− ≥ t)dt = +∞∫ 0 ∏ i Fi(τi − t)dt (3.64) Sada funkcija ocˇekivanih ukupnih trosˇkova Z, ima oblik: 70 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II Z = ( h− n∑ i=1 hi )+∞∫ 0 ∏ i Fi(τi − t)dt+ n∑ i=1 hi (τi − E(Li)) + ( b+ n∑ i=1 hi )+∞∫ 0 ( 1− ∏ i Fi(t+ τi) ) dt (3.65) Stacionarna tacˇka funkcije Z, je resˇenje sledec´eg sistema jednacˇina: ∂Z ∂τi = ( h− n∑ i=1 hi ) ∂ ∂τi +∞∫ 0 ∏ i Fi(τi − t)dt + hi + ( b+ n∑ i=1 hi ) ∂ ∂τi +∞∫ 0 ( 1− ∏ i Fi(t+ τi) ) dt  = 0, i = 1, 2, .., n (3.66) dalje pretpostavimo uslove o funkcijama raspodele Fi, i = 1, 2, . . . , n tako da parcijalni izvod i integral komutiraju [25] i dobic´emo: ∂Z ∂τi = ( h− n∑ i=1 hi )+∞∫ 0 ∂ ∂τi ∏ i Fi(τi − t)dt + hi + ( b+ n∑ i=1 hi )+∞∫ 0 ∂ ∂τi ( 1− ∏ i Fi(t+ τi) ) dt  = 0, i = 1, 2, .., n = ( h− n∑ i=1 hi )+∞∫ 0 fi(τi − t) ∏ j 6=i Fj(τj − t)dt + hi − ( b+ n∑ i=1 hi )+∞∫ 0 fi(t+ τi) ∏ j 6=i Fj(t+ τj)dt  = 0, i = 1, 2, .., n Konacˇno stacionarne tacˇke su resˇenja sledec´eg sistema nelinearnih jednacˇina: hi = ( −h+ n∑ i=1 hi )+∞∫ 0 fi(τi − t) ∏ j 6=i Fj(τj − t)dt  + ( b+ n∑ i=1 hi )+∞∫ 0 fi(t+ τi) ∏ j 6=i Fj(t+ τj)dt  , i = 1, 2, .., n (3.67) Dobijeni sistem jednacˇina se mozˇe resˇiti numericˇkim metodama i neka su τ∗1 , τ∗2 , . . . , τ∗n, ove vrednosti. Na ovaj nacˇin su odredeni optimalni vremenski trenuci t∗i = t ∗ 0 − τi, i = 1, . . . , n, kada treba zapocˇeti sklapanje i-tog podsklopa tako da su ocˇekivani ukupni troskovi minimalni. 71 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II Primer 3.4.1. Primetimo sledec´e, neka je n = 1 tada se stacionarna tacˇka, odnosno opti- malno resˇenje τ∗1 dobija kao resˇenje jednacˇine: (−h+ h1) +∞∫ 0 f1(τ1 − t)dt+ (b+ h1) +∞∫ 0 f1(t+ τ1)dt = h1 (3.68) kako je: +∞∫ 0 f(τ − t)dt = τ∫ −∞ f(u)du = τ∫ −∞ f(u)du = F (τ) odnosno: +∞∫ 0 f(t+ τ)dt = +∞∫ τ f(u)du = 1− F (τ) gornja jednacˇina postaje: (−h+ h1)F1(τ1) + (b+ h1)(1− F1(τ1)) = h1 (3.69) −hF1(τ1) + b+ h1 − bF1(τ1) = h1 (3.70) F1(τ1) = b b+ h (3.71) i njeno resˇenje je: τ∗1 = F −1 1 ( b b+ h ) (3.72) sˇto je resˇenje klasicˇnog newsboy problema na nivou podsklopa. Ovo je ocˇekivan rezultat jer su pretpostavke da c´e se dinamika sklapanja podsklopa preslikati na zavrsˇnu fazu pa su svi trosˇkovi preuzeti sa finalnog sklopa. Dakle predlozˇeni model je uopsˇtenje newsboy modela za slucˇaj da postoji jedna linija sklapanja rezervnog dela. 3.4.1 Stablo sklapanja sa viˇse nivoa II Neka je proces sklapanja rezervnog dela opisan stablom visine vec´e od dva. Na opisani nacˇin mi mozˇemo odrediti kriticˇna vremena t∗1, . . . , t∗n na nivou neposrednih podsklopova finalnog sklopa. Uocˇimo podstablo visine dva cˇiji je koren jedan od neposrednih podsklopova finalnog sklopa, neka je to i-ti (1 ≤ i ≤ n) podsklop. Formirajmo funkciju ukupnih trosˇkova (3.54) koji odgovaraju uocˇenom podstablu sklapanja: Ci = ∑ j (hi)j − hˆi  ((Ti)z − t∗i ) +∑ j (hi)j (t ∗ i − (Ti)j) +(bˆi + hˆi) ((Ti)z − t∗i )+ (3.73) 72 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II gde su: − t∗i - utvrdeni rok za simultanu raspolozˇivost podsklopova i-tog podsklopa − (Ti)j - trenutak raspolozˇivosti pojedinih podsklopova i-tog podsklopa − (Ti)z - simultana raspolozˇivost podsklopova i-tog podsklopa − (hi)j - jedinicˇni trosˇkovi skladiˇstenja pojedinih podsklopova i-tog podsklopa − hˆi - grupni trosˇkovi skladiˇstenja i-tog podsklopa − bˆi - grupni trosˇkovi kasˇnjenja i-tog podsklopa Da bismo navedni postupak sproveli na ovom stablu sklapanja neophodno je proceniti je- dinicˇne trosˇkove grupnog skladiˇstenja hˆi, odnosno jedinicˇne trosˇkove kasˇnjenja bˆi i-tog (1 ≤ i ≤ n) podsklopa koji je u korenu ovog podstabla. Procenu jedinicˇnih troskova kasˇnjenja i-tog podsklopa smo vec´ ustanovili (3.45): bˆi = bˆ ∏ j 6=i FLj−Li(t ∗ i − t∗j )  gde su sa bˆ = b oznacˇeni jedinicˇni trosˇkovi kasˇnjenja nadsklopa koji je u ovom slucˇaju finalni sklop. Na slicˇan nacˇin kao sˇto je to izvedeno sa jedinicˇnim trosˇkovima kasˇnjenja bˆi, mozˇemo proceniti i jedinicˇne trosˇkove grupnog skladiˇstenja hˆi za podsklopove i-tog (1 ≤ i ≤ n) podsklopa. Dakle jedno resˇenje je da se izvrsˇi raspodela troskova grupnog skladiˇstenja hˆ = h podsklopova finalnog sklopa, na trosˇkove grupnog skladiˇstenja za podsklopove njegovih neposrednih podsklopova. Analizirajmo trosˇkove skladiˇstenja: H = hˆ(t∗0 − Tz)+ + n∑ i=1 hi(Tz − Ti) (3.74) Svaki od podsklopova ima svoj udeo u ukupnim trosˇkovima skladiˇstenja koji pored trosˇkova pojedinacˇnog skladiˇstenja Hi = hi(Tz−Ti) ukljucˇuje i trosˇkove vezane za grupno skladiˇstenje Hˆ = hˆ(t∗0 − Tz)+. Ukupnost ovih trosˇkova cˇini trosˇkove grupnog skladiˇstenja hˆi podsklopova i-tog podsklopa. Neka se sklapanje i-tog (1 ≤ i ≤ n) podsklopa pokrene u nekom prethodnom trenutku ti −∆ti, gde je ∆ti proizvoljno mali vremenski period. Pretpostavimo Tz ≤ t∗0 (u suprotnom nema trosˇkova skladiˇstenja niti ikakve promene za dovoljno malo ∆ti) (3.11): U situaciji kao na slici (3.11) promena trosˇkova skladiˇstenja je: ∆iH = ∆ti  hˆ−∑ j 6=i hj ; Ti = Tz hi; Ti < Tz (3.75) Ocˇekivani jedinicˇni trosˇkovi skladiˇstenja E ( ∆iH ∆ti ) su: E ( ∆iH ∆ti ) = hˆ−∑ j 6=i hj P (Ti = Tz) + hiP (Ti < Tz) (3.76) 73 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II Slika 3.11: Promena trosˇkova skladiˇstenja prvi sabirak odgovara ucˇesˇc´u u jedinicˇnim trosˇkovima grupnog skladiˇstenja hˆ, a drugi odgo- vara jedinicˇnim trosˇkovima pojedinacˇnog skladiˇstenja i-tog podsklopa. Dakle opravdano je pretpostaviti: hˆi = hˆ−∑ j 6=i hj P (Ti = Tz) + hiP (Ti < Tz) = hˆ−∑ j hj P (Ti = Tz) + hi Primer 3.4.2. Primetimo sledec´e, u slucˇaju da nadsklop ima tacˇno jedan podsklop, tj. n = 1, kako je T1 = Tz bic´e: hˆ1 = ( hˆ− h1 ) · 1 + h1 = hˆ (3.77) odnosno u slucˇaju jedne linije sklapanja trosˇkovi skladiˇstenja se spusˇtaju niz lanac sklapa- nja. Slicˇno, ako pretpostavimo hˆ = ∑ i hi, odnosno ako pretpostavimo da se podsklopovi pojedinacˇno skladiˇste do predvidenog roka t∗0 (3.3), imac´emo: hˆi = hˆ−∑ j hj P (Ti = Tz) + hi = 0 · P (Ti = Tz) + hi = hi (3.78) odnosno grupni trosˇkovi skladiˇstenja za podsklopove i-tog podsklopa su jedinicˇni trosˇkovi 74 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II skladiˇstenja i-tog podsklopa. Pretpostavimo dalje, da je sklapanje svakog od podsklopova zavrsˇeno ranije odnosno neka je zavrsˇeno u trenutku Ti−∆t, u tom slucˇaju c´e sklapanje nad- sklopa pocˇeti u vremenskom trenutku Tz−∆t, sˇto c´e proizvesti promenu trosˇkova skladiˇstenja nadsklopa za iznos hˆ∆t. Pokazac´emo da su ovi trosˇkovi obuhvac´eni modelom na nivou pod- sklopova: ∑ i ∆iH = ∑ i hˆ−∑ j hj P (Ti = Tz) + hi ∆t = hˆ−∑ j hj ∑ i P (Ti = Tz) + ∑ i hi ∆t = hˆ−∑ j hj  · 1 +∑ i hi ∆t = hˆ∆t Drugim recˇima predlozˇeni model lokalno tretira trosˇkove koji se mogu pojaviti u narednoj fazi procesa sklapanja, a koji u toj fazi ne mogu biti tretirani. Na ovaj nacˇin smo pokazali da predlozˇeni model na adekvatan nacˇin pokriva navedene granicˇne slucˇajeve. Analogno kako je to uradeno za jedinicˇne trosˇkove kasˇnjenja na nivou podsklopova, jedinicˇni trosˇkovi grupnog skladiˇstenja hˆi podsklopova i-tog posklopa su: hˆi = hˆ−∑ j hj ∏ j 6=i FLj−Li(t ∗ i − t∗j ) + hi (3.79) Neka su poznati grupni trosˇkovi skladiˇstenja odnosno trosˇkovi kasˇnjenja svakog pojedinacˇnog podsklopa, sada mozemo formulisati proceduru proracˇuna vremena na svakom od podsklo- pova datog rezervnog dela. Odgovarajuc´a funkcija trosˇkova za podsklopove i-tog podsklopa je: Ci = ∑ j (hi)j − hˆi  ((Ti)z − t∗i ) +∑ j (hi)j(t ∗ i − (Ti)j) +(bˆi + hˆi)((Ti)z − t∗i )+ (3.80) dok su ocˇekivani ukupni trosˇkovi Zi = E(Ci) na i-tom podsklopu: Zi = ∑ j (hi)j − hˆi E ((Ti)z − t∗i ) +∑ j (hi)j(t ∗ i − E(Ti)j) +(bˆi + hˆi)E(((Ti)z − t∗i )+) (3.81) Da bi predlozˇeni iterativni postupak konvergirao, neophodno je pokazati da je Zi konvek- 75 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II sna funkcija [3], odnosno dovoljno je dokazati da je ∑ j (hi)j ≥ hˆi. Ispunjenost navedenog uslova direktno sledi iz pretpostavke da trosˇkovi skladiˇstenja nadsklopa nisu vec´i od trosˇkova skladiˇstenja posklopova hˆ = h ≤∑ i hi, odnosno hi ≤ ∑ j (hi)j : hˆi = hˆ−∑ j hj P (Ti = Tz) + hi ≤ ∑ i hj − ∑ j hj P (Ti = Tz) + hi = hi ≤ ∑ j (hi)j Na ovaj nacˇin mozˇemo produzˇiti resˇenje problema proracˇuna vremena na procese sklapanja rezervnog dela koji se opisuju stablom proizvoljne visine. Procedura kojom bi se resˇavao ovaj problem je identicˇna navedenoj proceduri za proracˇun vremena kada se podsklopovi skladiˇste do utvrdenog roka (3.3.1), s tom razlikom sˇto se pored izracˇunavanja jedinicˇnih trosˇkova kasˇnjenja podsklopa izracˇunavaju i jedinicˇni grupni troskovi skladiˇstenja podsklopa jednacˇinama (3.79). Jasno optimalna resˇenja se dobijaju resˇavanjem sistema jednacˇina (3.67). Primer 3.4.3. Razmotrimo problem proracˇuna vremena u slucˇaju da postoji samo jedna linija sklapanja, odnosno svako podstablo sklapanja ima tacˇno jednu granu, u predlozˇenom modelu n = 1. Ovaj process se opisuje stablom koje je lanac. Neka je recˇ o lancu duzˇine m > 1 (3.12) Slika 3.12: Jedna linija sklapanja Primetili smo da se u slucˇaju jedne linije sklapanja trosˇkovi sa finalnog sklopa prenose na podsklopove, odnosno hˆi = hˆ = h i bˆi = bˆ = b, i = 0, 1, 2, . . . , n − 1. U pojedinim fazama sklapanja i = 0, 1, . . . , n− 1 ukupni trosˇkovi su: 76 Planiranje odrzˇavanja vazduhoplova Simultani zahtev II Ci = h(ti − Ti)+ + b(Ti − t∗0)+ a ovo je klasicˇan newsboy model , cˇije je resˇenje ti+1 = t ∗ i = ti − F−1i ( b b+ h ) . Konacˇno resˇenje je: tm = tm−1 − F−1m−1 ( b b+ h ) = tm−2 − F−1m−2 ( b b+ h ) − F−1m−1 ( b b+ h ) = . . . = t0 − m−1∑ i=0 F−1i ( b b+ h ) 77 Glava 4 Sastavnice 4.1 Uvodna razmatranja Vazduhoplovi su savremena saobrac´ajna sredstva vrhunske tehnologije sa velikim brojem komponenti i kompleksnom strukturom. Pojedine komponente vazduhoplova se koriste na razlicˇit nacˇin, trpe razlicˇita opterec´enja i odrzˇavaju se po programu koji je njima najbolje prilagoden. Jedan od nacˇina savladavanja slozˇenosti je takozvana hijerarhijska dekompozi- cija. Slozˇeni koncept se na jednom nivou apstrakcije posmatra kao jedinstvena celina. Na nizˇem nivou apstrakcije se posmatra kao koncept koji se sastoji od delova (komponenti). Uza- stopnom primenom opisanog postupka dobija se takozvana hijerarhijska sastavnica. Dakle jedan od bitnih koncepata u sistemu odrzˇavanja vazduhoplova jeste sastavnica. Sastavnica je najprostije recˇeno [4], lista komponenti koji su sastavni delovi posmatranog objekta. Pri tome se vodi racˇuna o vezama izmedu sastavnih komponenti, pa je u osnovi sastavnice hi- jerarhijska struktura podataka. Bez gubitka opsˇtosti, u daljem tekstu c´emo pod sastavni- com podrazumevati fizicˇku strukturu posmatranog objekta, pa c´emo koristiti termine sklop, podsklop, nadsklop koji istovremeno oznacˇavaju i uzajamni odnos komponenata hijerarhije. Dakle podrazumevac´emo sastavnice sklopova koje se dobijaju hijerarhijskom dekompozicijom vazduhoplova, nad kojima se izvode aktivnosti odrzˇavanja. Dalje c´emo podrazumevati da su aktivnosti odrzˇavanja zapravo aktivnosti ugradnje podsklopova u nadredeni sklop. U praksi se koriste dve vrste sastavnica: − modularna − hijerarhijska Modularna sastavnica daje strukturu i veze elemanata samo u okviru jednog modula - sklopa. Pri tome nije vazˇna struktura samih podsklopova. Hijerarhijska sastavnica daje kompletnu strukturu odredenog sklopa ukljucˇujucˇi i hijerarhiju strukture svih podsklopva. Bez obzira na vrstu i klasu sastavnica, projektovanje i funkcionalna upotreba sastavnica zasniva se na hijerarhijskoj strukturi podataka odnosno na strukturi podataka tipa stablo. Svaka sastav- nica se mozˇe bijektivno preslikati na stablo. Cˇvor stabla mozˇe imati podredene i nadredene cˇvorove. Elementi sklopa, u inzˇenjerskom smislu odgovaraju podredenim cˇvorovima. Ele- menti se ugraduju u sklop - koji je predstavljen nadredenim cˇvorom. 78 Sastavnice Uvodna razmatranja − Koren stabla ima samo podredene cˇvorove i on odgovara slozˇenom sklopu − Listovi nemaju podredene cˇvorove i odgovaraju materijalima ili slozˇenim sklopovima koji nisu ukljucˇeni u sistem odrzˇavanja U nastavku glave koristic´emo stvarnu sastavnicu posebnog podsklopa kojim se odrzˇava kon- stantna temperatura hidraulicˇne tecˇnosti u vazduhoplovima. Ovaj podsklop ima sledec´e elemente: Tabela 4.1: Spisak delova grejnog tela - radijatora hidraulike. ident naziv 00001 grejno telo 00002 posuda gornja I 00003 posuda gornja II 00004 posuda donja 00005 blok sac´a 00006 nosacˇ natpisne plocˇe 00007 natpisna plocˇa 00008 lim posude gornje 00009 cev 00010 lim posude donje 00011 cevni zid Hijerarhijska sastavnica sklopa datog u tabeli (4.1), dobijena na osnovu tehnicˇkog crtezˇa ima sledec´i oblik (4.1): 00001 00002 00008 00009 00003 00009 00010 00004 00005 00011 00006 00007 Slika 4.1: Sastavnica radijatora hidraulike preuzeta iz proizvodnje. Baza podataka koja je u osnovi informacionog sistema za podrsˇku odrzˇavanja vazduhoplova izmedu ostalog ukljucˇuje tabelu sklopova, podsklopova elemenata i materijala koja zajedno sa tabelom skladiˇsta cˇini osnovu skladiˇsnog poslovanja. Ne ulazec´i u problematiku skladiˇsta, izlozˇic´emo strukturu pomenutih tabela: 79 Sastavnice Uvodna razmatranja sifra ::= 〈CHAR, 3,FORMAT :999〉 naziv ::= 〈CHAR, 40〉 skladiste ::= 〈sifra, naziv, ∗〉 skladista := {skladiste : PRIMARY KEY IS sifra} (4.1) Odgovarajuc´a tabela sklopova, podsklopova, elemenata i materijala c´e biti tabela artikala i imac´e sledec´u strukturu: ident ::= 〈CHAR, 5,FORMAT :99999,AUTONUMBER〉 skladiste ::= skladista.sifra naziv ::= 〈CHAR, 40〉 sifra ::= 〈CHAR, 12〉 artikal ::= 〈ident, skladiste, naziv, sifra, ∗〉 artikli := {artikal : PRIMARY KEY IS ident} (4.2) Posebno komponenetama podsklopa (4.1) odgovara niz zapisa tabele artikli (4.2) sledec´eg oblika: P00001 =  〈00001, ., grejno telo, .〉, 〈00002, .,posuda gornja I, .〉, 〈00003, .,posuda gornja II, .〉, 〈00004, .,posuda donja, .〉, 〈00005, .,blok sac´a, .〉, 〈00006, .,nosacˇ natpisne plocˇe, .〉, 〈00007, .,natpisna plocˇa, .〉, 〈00008, ., lim posude gornje, .〉, 〈00009, ., cev, .〉, 〈00010, ., lim posude donje, .〉, 〈00011, ., cevni zid, .〉  (4.3) Sastavnicu (4.1) c´emo dobiti tek nakon sˇto skup komponenata uocˇenog podsklopa (4.1) ure- dimo na odgovarajuc´i nacˇin. Predmet daljeg istrazˇivanja c´e biti c´e biti modeliranje struktura podataka koje c´e podrzˇati hijerarhijsko uredenje skupa podataka, a samim tim obezbediti podrsˇku konceptu sastavnica. U nastavku ove glave podrazumevac´emo postojanje tabele artikli sa datom strukturom (4.2). 80 Sastavnice Modularna sastavnica 4.2 Modularna sastavnica Modularna sastavnica daje veze elemanata samo u okviru jednog modula, izmedu jednog nadredenog i viˇse podredenih elemenata. Posmatrajmo sastavnicu sa slike (4.2), koja je dobijena iz hijerarhijske sastavnice (4.1). 00001 00002 00003 00004 00005 00006 00007 Slika 4.2: Modularna sastavnica radijatora datog tabelom (4.1) Modularna sastavnica korena stabla najcˇesˇc´e definiˇse nacˇin sklapanja slozˇenog sklopa, sˇto se mozˇe pronac´i u tehnicˇkoj dokumentaciji. Nadredeni element, u ovom slucˇaju sam koren 00001, ima skup podredenih sklopova: {00002, 00003, 00004, 00005, 00006, 00007} Modularna sastavnica sa slike (4.2), mozˇe se modelirati strukturom podataka: ident nad ::= artikli.ident ident pod ::= artikli.ident grana ::= 〈ident nad, ident pod〉 podstablo := {grana : PRIMARY KEY IS ident nad+ ident pod} (4.4) Struktura grane u tabeli (4.4), mozˇe sadrzˇati i detalje kojima se blizˇe odreduje priroda veze izmedu nadredenih i podredenih, sˇto c´e kasnije i biti slucˇaj. Priroda veza c´e biti ustanovljena analizom modularne sastavnice sa sledec´e slike: 1 3 2 4 Slika 4.3: Modularna sastavnica Na slici (4.3), prikazan je neki sklop 1 koji se sastoji od tri podsklopa 3, 2, 4. Sklop 1 naziva se nadredeni dok se podsklopovi 3, 2, 4, nazivaju podredeni. Svako stablo se sastoji od cˇvorova i grana. Cˇvorovima odgovaraju sklopovi i podsklopovi, dok grane opisuju njihovu medusobnu 81 Sastavnice Modularna sastavnica povezanost. Cˇvorovi su povezani granama i na slici (4.3), se mozˇe uocˇiti da su grane obrnuto orijentisane. Pocˇetak grane je na sklopu, dok je kraj grane na odgovarajuc´em podsklopu. Razlog ovakvog povezivanja je posledica same prirode inzˇenjerske analize problema, jer se uvek posmatra sklop i analizira od cˇega se on sastoji, a ne obrnuto. Veze podsklopova sa odgovarajuc´im sklopom, odnosno grane stabla izmedu ostalog mogu ukljucˇivati: − redosled ugradnje pojedinih podsklopova u procesu sklapanja finalnog sklopa − kolicˇine pojedinih podsklopova koje su neophodne za sklapanje finalnog sklopa − vremena neophodna za ugradnju pojedinih podsklopova u procesu sklapanja finalnog sklopa Redosled ugradnje podsklopova je obicˇno dat tehnicˇkim crtezˇom i pri tome uredenje podsklo- pova na samom crtezˇu daje nedvosmislenu informaciju o redosledu ugradnje. Pored uredenja podsklopova tehnicˇki crtezˇ mozˇe sadrzˇati i informacije o neophodnim kolicˇinama pojedinih podsklopova. 4.2.1 Redosled ugradnje Redosled ugradnje podsklopova se obicˇno zadaje graficˇkim prikazom sklopa i njegovih pod- sklopova. Analizirajuc´i cˇvorove sa slike (4.3), sledi da se prvo ugraduje podsklop 3 u sklop 1, zatim podsklop 2 i na kraju se podsklop 4 ugraduje u sklop 1. Na ovaj nacˇin je definisano uredenje podsklopova odnosno na skupu cˇvorova je definisana relacija parcijalnog uredenja (redosled ugradnje). Iz prethodnog sledi da se skup cˇvorova stabla viˇsestruko ureduje. Pored uredenja nadredeni-podredeni sklop imamo i uredenje tipa ugraduje se pre-posle sklopa. Pre svega oznacˇimo sa A skup cˇvorova koje razmatramo. U slucˇaju slike (4.3), skup A jednak je: A = {1, 2, 4, 3} (4.5) Na skupu A uvedimo relaciju: GBOM ⊆ A2 (4.6) koja je opisnog tipa1. Ova relacija je sa racˇunarskog glediˇsta jako vazˇna, jer se na osnovu nje definiˇse struktura podataka kojom se modelira stablo sa slike (4.3). Struktura podataka ima slicˇan oblik kao (4.4): ident nad ::= artikli.ident ident pod ::= artikli.ident grana ::= 〈ident nad, ident pod〉 GBOM := {grana : PRIMARY KEY IS ident nad+ ident pod} (4.7) 1Ekspertsko znanje inzˇenjera koji odreduju koji je nadredeni, a koji je podredeni cˇvor i ne postoji analiticˇki- matematicˇki izraz za ovu relaciju. 82 Sastavnice Modularna sastavnica Ako se (4.6) primeni na (4.5) da bi se opisala slika (4.3), dobija se: GBOM (A) = {〈1, 3〉, 〈1, 2〉, 〈1, 4〉} (4.8) Dobijeni skup grana nije konzistentan u odnosu na redosled ugradnje podsklopova u sklop, jer: GBOM (A) = {〈1, 3〉, 〈1, 2〉, 〈1, 4〉} = {〈1, 2〉, 〈1, 3〉, 〈1, 4〉} ... Struktura podataka (4.4) u literaturi se naziva Generic Bill of Material - genericˇka sastavnica i oznacˇava sa GBOM . Ova struktura podataka je osnov za stvaranje svih drugih sastavnica, jer se njenom modifikacijom - dodefinisanjem i uvodenjem novih operacija jednostavno dobi- jaju slozˇeniji modeli drugih sastavnica. Genericˇka sastavnica prvenstveno treba da omoguc´i prikazivanje viˇse verzija sklopova, a zatim i viˇse verzija proizvoda. Prethodni primer, poka- zuje osnovni nedostatak genericˇke sastavnice u primeni, ne ukljucˇuje uredenje podsklopova. Ovaj nedostatk genericˇke sastavnice se resˇava prosˇirivanjem odgovarajuc´e strukture podataka GBOM na sledec´i nacˇin: ident nad ::= artikli.ident ident pod ::= artikli.ident redosled ::= 〈NUMBER, 5〉 grana ::= 〈ident nad, ident pod, redosled〉 EBOM := {grana : PRIMARY KEY IS ident nad+ ident pod} (4.9) Primenom EBOM na (4.5) dobija se: EBOM (A) = {〈1, 3, 1〉, 〈1, 2, 2〉, 〈1, 4, 3〉} (4.10) sˇto je potpuno, u smislu prenosa informacija, preslikalo stablo sa slike (4.3). Struktura po- dataka EBOM se u literaturi naziva Engineering Bill of Material - inzˇenjerska sastavnica, i predstavlja prvi primer izmene genericˇke sastavnice. Izmena je, samo na prvi pogled jed- nostavna, ali ona donosi moguc´nost potpunog preslikavanja dvonivovskog stabla kojim je predstavljen odnos sklop-podsklop, odnosno prirodno definisan redosled ugradnje podsklo- pova da bi se dobio sklop. 4.2.2 Neophodne kolicˇine Sastavnica data slikom (4.3), u stvarnoj upotrebi ima sledec´i oblik: Velicˇine na granama su neophodne kolicˇine odgovarajuc´ih podsklopova za dobijanje jednog sklopa. Ne ulazec´i u vrstu jedinice mere inzˇenjerska sastavnica data sa (4.9), jednostavnom 83 Sastavnice Modularna sastavnica 1 3 2 4 713 11 Slika 4.4: Potpuna modularna sastavnica izmenom na nivou definicije strukture podataka, podrzˇava belezˇenje kolicˇina i ima sledec´i oblik: ident nad ::= artikli.ident ident pod ::= artikli.ident redosled ::= 〈NUMBER, 5〉 kolicina ::= 〈NUMBER, 13.4〉 grana ::= 〈ident nad, ident pod, redosled, kolicina〉 EBOM − T := {grana : PRIMARY KEY IS ident nad+ ident pod} (4.11) Konacˇno, primenom EBOM-T na (4.5), stablo dato slikom (4.4), preslikava se u skup: EBOM− T (A) = {〈1, 3, 1, 13〉, 〈1, 2, 2, 7〉, 〈1, 4, 3, 11〉} (4.12) Navedene GBOM, EBOM i EBOM-T sastavnice se razlikuju u odnosu na kvalitet podataka - informacija kojim su snabdevene. Kvalitet informacija odreduje njihovu upotrebljivost i oblast primene. U teorijskim analizama jednostavnije je raditi sa GBOM jer se postizˇe mak- simalna usredsredenost na problem koji se resˇava. Sadrzˇajno kvalitetnija EBOM omoguc´ava povezivanje teorijskih dostignuc´a sa stvarnim problemima. Pojedini autori zato strukturu (4.11) opisuju na sledec´i nacˇin: ident nad ::= artikli.ident ident pod ::= artikli.ident redosled ::= 〈NUMBER, 5〉 lista ::= 〈∗〉 grana ::= 〈ident nad, ident pod, redosled, lista〉 EBOM := {grana : PRIMARY KEY IS ident nad+ ident pod} (4.13) pri cˇemu se podrazumeva da c´e stvarni problemi biti na odgovarajuc´i nacˇin resˇavani. Ne sma- njujuc´i opsˇtost, u nastavku pod pojmom inzˇenjerske sastavnice - EBOM podrazumevac´emo strukturu (4.13). 84 Sastavnice Modularna sastavnica 4.2.3 Osobine modularne sastavnice Posle analiza datih u prethodnim delovima ovog teksta mozˇemo zakljucˇiti da modularna sastavnica ima sledec´e osobine: − poseduje samo jedan nadredeni cˇvor, koji odgovara slozˇenom sklopu − poseduje jedan ili viˇse podredenih cˇvorova, kojima odgovaraju neposredni podsklopovi sklopa u nadredenom cˇoru Iz prethodnog sledi da je modularna sastavnica dvonivovska sastavnica modelirana granama stabla na dva uzastopna nivoa, pa se cˇesto u literaturi umesto termina modularna sastavnica koristi termin dvonivovska sastavnica. Samo stablo je opisano strukturom podataka (4.13). Potpuno je jasno da se nadredeni cˇvora ne sme nac´i u spisku podredenih cˇvorova. Ovo ogranicˇenje nije direktno podrzˇano navedenom strukturom podataka (4.13), vec´ se mora programski kontrolisati. Takode, postavlja se pitanje mozˇe li jedan isti sklop imati dve razlicˇite modularne sastavnice? Ovo znacˇajno pitanje za inzˇenjere se resˇava na poseban nacˇin. 85 Sastavnice Hijerarhijska sastavnica 4.3 Hijerarhijska sastavnica Na slici (4.1) data je jedna stvarna hijerarhijska sastavnica. U literaturi se skoro iskljucˇivo razmatra prva hijerarhijska sastavnica i najcˇesˇc´e se koristi za dobijanje spiska neophodnih kolicˇina materijala ili podsklopova za dobijanje gotovog proizvoda. U susˇtini je to izvesˇtaj iz baze podatka. Da bi dobili pomenuti izvesˇtaj pored podataka organizovanih u tabelama baze podataka neophodno je razviti i algoritme koji c´e na odgovarajuc´i nacˇin obraditi postojec´e podatke. Pre svega analizirajmo sledec´u sastavnicu: 1 3 5 6 2 4 7 6 5 8 4 7 6 713 11 21 31 1 55 5 5 1 Nivo 2 3 4 Slika 4.5: Hijerarhijska sastavnica Ocˇigledno hijerarhihjska sastavnica ima strukturu stabla i prirodno je da se koristi stablo kao struktura za modeliranje hijerarhijske sastavnice. Mozˇe se primetiti da je i nivo u hi- jerarhiji komponenta hijerarhijske sastavnice. Ovo je posledica kako organizacije tehnicˇke dokumetacije sa jedne strane, tako i cˇinjenice da je hijerarhijska sastavnica kompozicija mo- dularnih sastavnica. Tradicionalno inzˇenjerski pristup, u formiranju hijerarhijske sastavnice, podrazumevao je: − izostavljanje graficˇke predstave sastavnice, 2 − koriˇsc´enje tehnicˇke dokumentacije uredene prema hijerarhijskoj sastavnici, da bi se odredile kolicˇine potrebnog materijala. Racˇunari su doneli promenu u nacˇinu razmiˇsljanja inzˇenjera i nacˇinu koriˇsc´enja hijerahijske sastavnice. U potpunosti je promenjen tradicionalni inzˇenjerski pristup, pocˇev od vizuelizacije proizvoda, do izvodenja razlicˇitih proracˇuna. Personalizacija proizvoda, velika produktivnost i veliki broj verzija proizvoda se mozˇe podrzˇati odgovarajuc´om upotrebom hijerarhijske sa- stavnice. 2Ovo je razumljivo, prirodno je da se za slozˇene proizvode i ne mozˇe nacrtati sastavnica 86 Sastavnice Hijerarhijska sastavnica 4.3.1 Osnovni pojmovi Stablo sa slike (4.5) sastavljeno je od viˇse modularnih sastavnica, koje se pojavljuju na razlicˇitim pozicijama u stablu. Cˇvorovi skupa: B = {1, 2, 3, 4, 5, 6, 7} (4.14) prirodno se razvrstavaju po nivoima ugradnje, gde se na nivou 0 nalazi koren. Koren stabla je cˇvor koji ima samo izlazne grane. Na slici (4.5) je to cˇvor 1 i on predstavlja gotov proizvod koji se sastoji od podsklopova. root(B) = 〈1〉 (4.15) Na ostalim nivoima se nalaze podsklopovi koji su uredeni po nivoima tako da je jednostavno planirati proizvodnju. Cˇvorovi sa slike (4.5) razvrstavaju se na sledec´i nacˇin: level(B, 0) = 〈1〉 level(B, 1) = 〈3, 2, 4〉 level(B, 2) = 〈5, 6, 4, 5, 8, 7, 6〉 level(B, 3) = 〈7, 6〉 (4.16) U stablu hijerarhijske sastavnice postoje listovi koji odgovaraju neophodnim materijalima ili posebnim sklopovima koji iz nekih razloga nisu podvrgnuti strukturnoj dekompoziciji. Listovi stabla su cˇvorovi koji imaju samo ulazne grane. Hijerarhijska sastavnica sa slike (4.5) ima sledec´e listove: leaf (B) = 〈5, 6, 7, 8〉 (4.17) Na ovaj nacˇin za dati skup cˇvorova: NODE := {spisak cˇvorova} (4.18) definiˇsu se sledec´e funkcije: root(NODE) := {cˇvor} level(NODE, nivo) := {∗} (4.19) leaf(NODE) := {∗} Dalje primetimo da se hijerarhijska sastavnica opisuje konacˇnim stablom. Sve putanje od korena do listova stabla se sastoje od konacˇnog broja grana. Ove cˇinjenice su posebno vazˇne u programiranju i projektovanju hijerarhijskih sastavnica. Hijerarhijska sastavnica se posebno koristi kao podrsˇka resˇaanju sledec´ih problema: 87 Sastavnice Hijerarhijska sastavnica − pronadi sve puteve od listova do korena i izracˇunaj potrebne kolicˇine − pronadi sve korene podstabala u kojima list mozˇe da ucˇestvuje i oni se uspesˇno resˇavaju uz pomoc´ racˇunara. U zavisnosti od prirode samog proizoda cˇija se struktura opisuje hijerarhijskom sastavnicom razlikovac´emo dva tipa hijerarhijskih sastavnica koji c´e dalje odredivati nacˇin njenog formiranja: − staticˇka − dinamicˇka Priroda gotovog proizvoda cˇija je struktura opisana hijerarhijskom sastavnicom, odreduje i prirodu hijerarhijske sastavnice [20]. Ako se posmatra slika (4.5), kojom je data jednostavna hijerarhijska sastavnica, namec´e se pitanje kako se ona formira? − Od korena ka listovima - odozgo na dole − Od listova ka korenu - odozdo na gore Analizom koja sledi mozˇemo zakljucˇiti sledec´e. Ukoliko se radi o malom broju proizvoda, odnosno o proizvodu koji se prakticˇno ne menja odgovarajuc´a hijerarhijska sastavnica je staticˇka i formira se od korena ka listovima odnosno koristi se pristup odozgo na dole. U slucˇaju velikog broja proizvoda, odnosno ukoliko se prizvod cˇesto menja odgovarajuc´a hije- rarhijska sastavnica je dinamicˇka i formira se od listova ka korenu, odnosno koristi se pristup odozdo na gore. 4.3.2 O broju proizvoda Pod brojem proizvoda podrazumevac´emo broj verzija istog proizvoda. Proizvodi u kojima je ugradena vrhunska tehnologija, tehnicˇki su izuzetno slozˇeni i spadaju u proizvode koji imaju staticˇku sastavnicu. Tipicˇan primer su avioni i bilo sˇta sˇto je povezano sa vojnom industri- jom. Staticˇka sastavnica, bez obzira kako je napravljena, je nepromenljiva u bilo kom svom delu, ili ako se menja, struktura joj ostaje nepromenjena. Sa druge strane proizvodi metal- ske industrije, poput automobila, mogu se tretirati na oba nacˇina i kao proizvodi sa malim brojem verzija i kao proizvodi sa velikim brojem verzija. Veliki broj verzija imaju proizvodi metalske industrije koji imaju karakteristiku proizvoda masovne potrosˇnje. Proizvodacˇi su prinudeni da izbacuju “nove proizvode”, i to ne retko ozbiljno menja osnovnu verziju pro- izvoda. Pokazalo se da ja tada pogodno imati sastavnicu za osnovni prozvod, verziju 0, a potom neprekidnim izmenama dobijati “nove” proizvode. Neophodno je analizirati kako broj proizvoda uticˇe na projektovanje sastavnica i na njihovu prirodu. Proizvodi sa malim brojem verzija Hijerarhijska sastavnica za proizvode sa malim brojem verzija najcˇesˇc´e se unosi kao jedin- stveni skup podataka i nad njima se tako i radi. Da bi ilustrovali ovu cˇinjenicu, skup podataka kojim se modelira hijerarhijska sastavnica sa slike (4.5) ima sledec´i izgled: 88 Sastavnice Hijerarhijska sastavnica ident nad ::= artikli.ident ident pod ::= artikli.ident nivo ::= 〈NUMBER, 5〉 redosled ::= 〈NUMBER, 5〉 kolicina ::= 〈NUMBER, 13.4〉 grana ::= 〈ident nad, ident pod, nivo, redosled, kolicina〉 EBOM −H := {grana} (4.20) Struktura podataka data sa (4.20) mozˇe jednostavno da prati slaganje tehnicˇke dokumenta- cije, u kom god obliku da je. Staticˇnost strukture je ocˇigledna, jer je jednostavnije iskopirati celokupnu sastavnicu za novi proizod nego dodati, oduzeti ili izmeniti odredenu komponentu u sastavnici. Proizvodi sa velikim brojem verzija Proizvodi sa velikim brojem verzija imaju jedinstvenu hijerarhijsku sastavnicu, ona se cˇesto naziva GBOM bez opasnosti mesˇanja pojmova. Jednostavno se pretpostavlja da postoji sa- stavnica koja opisuje viˇse proizvoda iste klase. Verzije proizvoda se dobijaju malim izmenama postojec´e hijerarhijske sastavnice. Cˇesto se kazˇe da je polazna hijerarhijska sastavnica, sa- stavnica verzije 0 ili sastavnica prototipa. Da bi ovo objasnili navedimo jedan primer koji c´e karakterisati proizvode sa velikim brojem verzija. Iskoristimo zato hijerarhijsku sastavnicu sa slike (4.5) koja c´e nam posluzˇiti kao sastavnica verzije 0. 1 3 5 6 2 4 9 6 5 8 4 9 6 713 11 21 31 1 55 5 5 1 Nivo 2 3 4 Slika 4.6: Hijerarhijska sastavnica novog proizvoda. Razlika izmedu sastavnica sa slike (4.5) i (4.6) je u modularnoj sastavnici: koja je zamenjena sa: Ovo je dovoljno da se dobije nova verzija istog proizvoda. Dobijena hijerarhijska sastavnica 89 Sastavnice Hijerarhijska sastavnica 4 7 6 5 5 Slika 4.7: Modularna sastavnica {〈4, 7, 1, 5〉, 〈4, 6, 2, 5〉}. 4 9 6 5 5 Slika 4.8: Modularna sastavnica {〈4, 9, 1, 5〉, 〈4, 6, 2, 5〉}. sa slike (4.6) je istovetna hijerarhijskoj sastavnici (4.5) uz izmenu odredene modularne sa- stavnice. Pokazalo se da je najjednostavnije uocˇiti zajednicˇke modularne sastavnice od kojih su obe sastavljene, i posebno istac´i razlike. Dakle hijerarhijska sastavnica sa slike (4.6) i hi- jerarhijska sastavnica sa slike (4.5) sastoje se od sledec´ih zajednicˇkih modularnih sastavnica: 1 3 2 4 713 11 Slika 4.9: Modularna sastavnica {〈1, 3, 1, 13〉, 〈1, 2, 2, 7〉, 〈1, 4, 3, 11〉}. dok se razlikuju u modularnim sastavnicama: Priroda hijerarhijske sastavnice Ako se analizira prethodna sekcija jednostavno se mozˇe uocˇiti da je hijerarhijska sastavnica sa slike (4.5) jednaka: EBOM−H (Slika (4.5)) := { {〈1, 3, 1, 13〉, 〈1, 2, 2, 7〉, 〈1, 4, 3, 11〉}, {〈3, 5, 1, 1〉, 〈3, 6, 2, 1〉}, {〈2, 4, 1, 1〉, 〈2, 5, 2, 2〉, 〈2, 8, 3, 3〉}, {〈4, 7, 1, 5〉, 〈4, 6, 2, 5〉} } 90 Sastavnice Hijerarhijska sastavnica 3 5 6 1 1 Slika 4.10: Modularna sastavnica {〈3, 5, 1, 1〉, 〈3, 6, 2, 1〉}. 2 4 5 8 12 3 Slika 4.11: Modularna sastavnica {〈2, 4, 1, 1〉, 〈2, 5, 2, 2〉, 〈2, 8, 3, 3〉}. dok je hijerarhijska sastavnica sa slike (4.6) jednaka: EBOM−H (Slika (4.6)) := { {〈1, 3, 1, 13〉, 〈1, 2, 2, 7〉, 〈1, 4, 3, 11〉}, {〈3, 5, 1, 1〉, 〈3, 6, 2, 1〉}, {〈2, 4, 1, 1〉, 〈2, 5, 2, 2〉, 〈2, 8, 3, 3〉}, {〈4, 9, 1, 5〉, 〈4, 6, 2, 5〉} } odakle sledi da je: EBOM−H (Slika (4.5)) ∩ EBOM−H (Slika (4.6)) := { {〈1, 3, 1, 13〉, 〈1, 2, 2, 7〉, 〈1, 4, 3, 11〉}, {〈3, 5, 1, 1〉, 〈3, 6, 2, 1〉}, {〈2, 4, 1, 1〉, 〈2, 5, 2, 2〉, 〈2, 8, 3, 3〉}, {〈4, 6, 2, 5〉} } Prirodno je dakle klasu proizvoda opisati minimalnim skupom modularnih sastavnica koje su elementi hijerarhijske sastavnice sakog proizvoda iz date klase proizoda. Modularne sastav- nice su dakle gradivni blokovi za hijerarhijsku sastavnicu. Dinamika hijerarhijskih sastavnica se ostvaruje posebnim izborom modularnih sastavnica. Takode, ukoliko su formirane modu- larne sastavnice jednostavno je formirati konkretnu hijerarhijsku sastavnicu, pri tome ni veliki 91 Sastavnice Hijerarhijska sastavnica 4 7 6 5 5 Slika 4.12: Modularna sastavnica, hijerarhijske sastavnice sa slike (4.5) 4 9 6 5 5 Slika 4.13: Modularna sastavnica hijerarhijske sastavnice sa slike (4.6) broj proizvoda ne predstavlja problem. Pre svega neophodno je prosˇiriti EBOM strukturu podataka (4.13) na sledec´i nacˇin: ident nad ::= artikli.ident verzija ::= 〈CHAR, 3〉 ident pod ::= artikli.ident redosled ::= 〈NUMBER, 5〉 lista ::= 〈∗〉 grana ::= 〈ident nad, verzija, ident pod, redosled, lista〉 EBOM −H := {grana} (4.21) Atribut verzija mozˇe imati posebnu vrednost null koja oznacˇava pripadnost verziji 0 datog proizvoda. Tradicionlano, vrednost null specificira situaciju ne postojanja vrednosti. Na ovaj nacˇin se uocˇena problematika izneta u prethodnom poglavlju, vezana za sastavnice proizvoda sa viˇse verzija (4.5) i (4.6) jednostavno resˇava podatkom verzija. Da bi to pokazali pogledajmo kako sada izgleda hijerarhijska sastavnica sa slike (4.5): EBOM (Slika(4.5)) := { {〈1, , 3, 1, 13〉, 〈1, , 2, 2, 7〉, 〈1, , 4, 3, 11〉}, {〈3, , 5, 1, 1〉, 〈3, , 6, 2, 1〉}, {〈2, , 4, 1, 1〉, 〈2, , 5, 2, 2〉, 〈2, , 8, 3, 3〉}, {〈4, , 7, 1, 5〉, 〈4, , 6, 2, 5〉} } 92 Sastavnice Hijerarhijska sastavnica i ona je ocˇigledno hijerarhijska sastavnica verzije 0, dok hijerarhijska sastavnica sa slike (4.6) ima oblik: EBOM (Slika(4.6)) := { {〈1, , 3, 1, 13〉, 〈1, , 2, 2, 7〉, 〈1, , 4, 3, 11〉}, {〈3, , 5, 1, 1〉, 〈3, , 6, 2, 1〉}, {〈2, , 4, 1, 1〉, 〈2, , 5, 2, 2〉, 〈2, , 8, 3, 3〉}, {〈4, 1, 9, 1, 5〉, 〈4, , 6, 2, 5〉} } jer su to u susˇtini dva razlicˇita proizvoda, proizvod 1 verzije 0 i proizvod 1 verzije 1. 4.3.3 Generisanje hijerarhijske sastavnice Hijerarhijska sastavnica predstavljena na slici (4.1) daje kompletnu strukturu razradenu po hijerarhiji nivoa ugradnje podsklopova u konacˇni sklop. Primetimo da jedan podsklop mozˇe ulaziti viˇse puta u strukturu konacˇnog sklopa na istim ili razlicˇitim nivoima. U susˇtini hijerahijska sastavnica na slici (4.1) sastavljena je od dvonivovskih - modularnih sastavnica. Jednu njenu modularnu sastavnicu smo vec´ pokazali na slici (4.2). Na sledec´oj slici se nalaze sve modularne sastavnice koje su neophodne i nalaze se u tabeli (4.1): 00001 00002 00003 00004 00005 00006 00007 00002 00008 00009 00003 00009 00010 00005 00011 Slika 4.14: Modularne sastavnica podsklopova Podsklop 9 se dva puta ugradjuje prema slici (4.1), ali je vazˇno uocˇiti da se kao skup podataka pojavljuje samo jednom. U stvarnosti se ove modularne sastavnice zadaju tabelom: 93 Sastavnice Hijerarhijska sastavnica Tabela 4.2: Sve modularne sastavnice radijatora ident nad ident pod red 00001 00002 1 00001 00003 2 00001 00004 3 00001 00005 4 00001 00006 5 00001 00007 6 00002 00008 1 00002 00009 2 00003 00009 1 00003 00010 2 00005 00011 1 Formiranje hijerarhijske sastavnice se sastoji u povezivanju odgovarajuc´ih modularnih stav- nica, uz neprekidnu kontrolu sˇta su listovi, nadredeni i podredeni elementi. Da bi tabelu (4.2) preslikali u tabelu baze podataka, neophodno je promeniti strukturu podataka (4.4). Prva izmena se sastoji u uvodenju redosleda kojim se ureduju podredeni elementi (4.22). ident nad ::= artikli.ident ident pod ::= artikli.ident redosled ::= 〈NUMERIC, 5〉 grana ::= 〈ident nad, ident pod, redosled〉 podstablo := {grana : PRIMARY KEY IS nadredjeni+ podredjeni} (4.22) Na ovaj nacˇin se modelira redosled ugradnje podsklopova u nadredeni sklop. Navedimo primer kojim se definiˇsu modularne sastavnice sa slike (4.14): podstablo = { 〈00001, 00002, 1〉, 〈00001, 00003, 2〉, 〈00001, 00004, 3〉, 〈00001, 00005, 4〉, 〈00001, 00006, 5〉, 〈00001, 00007, 6〉, (4.23) 〈00002, 00008, 1〉, 〈00002, 00009, 2〉, 〈00003, 00009, 1〉, 〈00003, 00010, 2〉, 〈00005, 00011, 1〉 } 94 Sastavnice Hijerarhijska sastavnica Druga karakteristika hijerarhijske sastavnice je sˇto se broj nivoa - “dubina” hijerarhijske sastavnice u strukturi podataka ne mozˇe elementarno uvesti. Broj nivoa, odnosno dubina se odreduje u toku formiranja hijerarhijske sastavnice. Opsˇti algoritam formiranja hijerarhijske sastavnice Algoritmi za formiranje hijerarhijske sastavnice mogu biti: − rekurzivni − nerekurzivni pri cˇemu je vazˇno istac´i da su ovi drugi izvedeni iz prvih, tako sˇto je rekurzija na neki od standardnih nacˇina eliminisana, na primer simulacijom rekurzije koriˇsc´enjem steka [22] [23]. Ulazna velicˇina je koren podstabla koji odgovara sklopu za koji treba generisati hijerarhijsku sastavnicu. Prikazani algoritam je genericˇkog tipa i generesˇe GBOM sastavnicu [19]. Algoritam 4.1 Rekurzivno generisanje GBOM-a void napravi_gbom( c_ident, n_nivo ) { local sledeci; if ( !dbseek( podstablo, c_ident ) ) { dbappend( gbom , n_nivo, c_ident, "00000" ); return; } else { while( !dbeof( podstablo ) && podstablo.ident_nad == c_ident ) { sledeci = dbnext( podstablo ); dbappend( gbom , n_nivo, c_ident, podstablo.ident_pod ); napravi_gbom( podstablo.ident_pod, n_nivo+1 ); dbgoto( podstablo, sledeci ) }; }; return; } Rekurzivna procedura napravi gbom selektuje cˇvorove stabla hijerarhijske sastavnice po takozvanim “krajnje levim granama”. Rezulat se smesˇta u tabelu cˇija je struktura: 95 Sastavnice Hijerarhijska sastavnica nivo ::= 〈NUMERIC, 5〉 ident nad ::= artikli.ident ident pod ::= artikli.ident grana ::= 〈nivo, ident nad, ident pod〉 gbom := {grana} (4.24) Navedena tabela se koristi kao spremiˇste za ispis rezultata algoritma. Na primer, ako se algoritam primeni na skup modularnih sastavnica (4.23), sadrzˇaj pomenute tabele c´e biti: gbom = { 〈1, 00001, 00002〉 〈2, 00002, 00008〉, 〈3, 00008, 00000〉, 〈2, 00002, 00009〉, 〈3, 00009, 00000〉, 〈1, 00001, 00003〉, 〈2, 00003, 00009〉, 〈3, 00009, 00000〉, 〈2, 00003, 00010〉, 〈3, 00010, 00000〉, 〈1, 00001, 00004〉, 〈2, 00004, 00000〉, 〈1, 00001, 00005〉, 〈2, 00005, 00011〉, 〈3, 00011, 00000〉, 〈1, 00001, 00006〉, 〈2, 00006, 00000〉, 〈1, 00001, 00007〉, 〈2, 00007, 00000〉 } 96 Glava 5 Sistem odrzˇavanja vazduhoplova 5.1 Uvodna razmatranja Podaci o sastavnici proizvoda i tehnologiji izrade predstavljaju osnovu za upravljanje siste- mom odrzˇavanja [16]. Njihova tacˇnost, dobra priprema i moguc´nost upravljanja nastalim promenama su neophodni za efikasno funkcionisanje ostalih sistema, pa samim tim i sistema odrzˇavanja. Najjednostavniji nacˇin za pocˇetno planiranje odrzˇavanja sastoji se u preuzima- nju sastavnice iz tehnicˇke pripreme i iz proizvodnje. Sledec´i korak je prilagoditi ih zahtevima sistema za odrzˇavanje. Najcˇesˇc´e aktivnosti u sistemu za odrzˇavanje vazduhoplova su zapravo aktivnosti sklapanja (pripreme) rezervnog dela i njegova ugradnja u objekat koji je pred- met odrzˇavanja (vazduhoplov), pa je jedan od glavnih izvora podataka, na osnovu kojih se projektuje i realizuje sistem za upraljanje odrzˇavanjem, konstruktivno-tehnolosˇka dokumen- tacija. Pored tehnolosˇkih postupaka (pregleda operacija, operacionih listi) i konstrukcionih crtezˇa, sastavnica proizvoda je posebno znacˇajna. Sastavnica gotovih proizvoda pored struk- ture samog proizvoda daje i postupak ugradnje komponenti u gotov proizvod. Samim tim, ona je osnova za definisanje postupka odrzˇavanja odredenog proizvoda. Utvrdjeni redosled ugradnje podsklopova cˇini osnovu za planiranje odrzˇavanja, odnosno redosled sklapanja (pri- preme) pojedinih komponenti u samom ciklusu odrzˇavanja. Sa druge strane, tehnologija daje spisak operacija sa tacˇno definisanim redosledom i standardnim vremenima po operacijama, sˇto cˇini osnov za planiranje kapaciteta, pa se ovo mozˇe iskoristiti kako za uredivanje niza ak- tivnosti odrzˇavanja tako i za procenu vremena trajanja pojedinih aktivnosti odrzˇavanja. Na ovaj nacˇin se mozˇe efikasno planirati skup aktivnosti odrzˇavanja, odnosno mozˇe se govoriti o optimalnom planiranju odrzˇavanja [18] [12]. U prethodnoj Glavi je predlozˇena fleksibilna struktura sastavnice, dakle postoji osnov za njeno sadrzˇajno rasˇirenje. Sledec´i korak je modeliranje aktivnosti sklapanja odnosno ugrad- nje podsklopova u nadredeni sklop, rezultat pomenutog modeliranja c´e biti dodatni sadrzˇaj takozvane druge hijerarhijske sastavnice. Sam postupak ugradnje (tehnologija ugradnje) se uobicˇajenom tehnikom dekompozicije, rasˇcˇlanjuje na niz elementarnih zahvata koji se zatim modeliraju u strukturi druge hijerarhijske sastavnice. 97 Sistem odrzˇavanja vazduhoplova Projektovanje algoritma za generisanje druge sastavnice 5.2 Projektovanje algoritma za generisanje druge sastavnice Druga hijerarhijska sastavnica je sastavnica kojom se definiˇse tehnologija odrzˇavanja pro- izvoda [21]. Da bi pojednostavili projektovanje podrazumeva se da postoje odgovarajuc´e strukture podataka u kojima se belezˇe informacije o prolazu u odredenom zahvatu odredene operacije. Izmedu ostalog podrazumevac´emo postojanje evidencije zahvata, odnosno tabele sa sledec´om strukturom: ident ::= 〈CHAR, 5,FORMAT : 99999,AUTONUMBER〉 sifra ::= 〈CHAR, 15〉 naziv ::= 〈CHAR, 40〉 zahvat ::= 〈ident, sifra, naziv, ∗〉 operacije := {zahvat : PRIMARY KEY IS ident} (5.1) U zavisnosti od strukture grane u modularnoj (dvonivovskoj) sastavnici koja definiˇse kontekst u kome se zahvat izvodi, razlikuju se cˇetiri tipa zahvata u odrzˇavanju. Ova klasifikacija je izvedena prema tome sˇta su krajevi grane kojoj je zahvat pridruzˇen: − zahvat ima nadredeni i nema podredeni sklop − zahvat ima nadredeni i podredeni sklop i pri tome su to isti sklopovi − zahvat ima nadredeni i podredeni sklop i to su razlicˇiti sklopovi − zahvat ima podredeni i nema nadredeni sklop Zahvati se vezuju za tehnolosˇki postupak i imaju svoj redosled i ostale atribute. Redosled je bitan jer u susˇtini on sa vrstom zahvata i odreduje tehnolosˇki postupak. U nastavku ove glave dac´emo prikaz sva cˇetri tipa zahvata i njihove veze sa modularnim sastavnicama. Pre svega definisac´emo modularne sastavnice koje u granama nose informacije o operacijama - zahvatima. Tabela tehnologija u kojoj se belezˇe ove modularne sastavnice, ima sledec´u strukturu: ident nad ::= artikli.ident ident pod ::= artikli.ident ident ::= operacije.ident redosled ::= 〈NUMERIC, 5〉 zahvat ::= 〈ident nad, ident pod, ident, redosled, ∗〉 tehnologija := {zahvat : PRIMARY KEY IS ident nad+ ident pod+ redosled} (5.2) Pokazalo se da je vrlo vazˇno analizirati klase zahvata jer direktno uticˇu na nacˇin konstruisanja algoritma formiranja druge sastavnice. U nastavku ove glave daju se predstavnici pojedinih tipova zahvata i odgovarajuc´i primeri. 98 Sistem odrzˇavanja vazduhoplova Projektovanje algoritma za generisanje druge sastavnice 5.2.1 Zahvat ima nadredeni i nema podredeni sklop Na sledec´oj slici prikazan je skup zahvata koji imaju nadredeni sklop i pri tome nemaju podredene sklopove. 00011 00010 00011 00033 00021 00031 00032 00022 00033 Slika 5.1: Skup zahvata sa nadredenim sklopom i bez podredenih sklopova Na slici (5.1) ocˇigledna je veza sa modularnom sastavnicom, ali nije istaknut redosled zahvata koji je izuzetno bitan jer taj redosled cˇini tehnologiju. Na sledec´oj slici se posebno isticˇe redosled zahvata: 00011 00010 00011 00033 00021 00031 00032 00022 00033 Slika 5.2: Redosled zahvata sa nadredenim sklopom i bez podredenih sklopova U slucˇaju zahvata sa slike (5.2), podskup Pnad1→pod0 tabele (5.2) je: 99 Sistem odrzˇavanja vazduhoplova Projektovanje algoritma za generisanje druge sastavnice Pnad1→pod0 = { 〈00011, 00000, 00010, 1〉, 〈00011, 00000, 00011, 2〉, 〈00011, 00000, 00033, 3〉, 〈00011, 00000, 00021, 4〉, 〈00011, 00000, 00031, 5〉, 〈00011, 00000, 00032, 6〉, 〈00011, 00000, 00022, 7〉, 〈00011, 00000, 00033, 8〉 } gde je nepostojanje sklopa oznacˇeno identifikacionom sˇifrom 00000. 5.2.2 Zahvat ima nadredeni i podredeni sklop i pri tome su to isti sklopovi Postoje sklopovi u odrzˇavanju koji zahtevaju niz pripremnih radnji pre nego sˇto se zapocˇne njihova ugradnja odnosno apliciranje u sklop. Jedan dobar primer je avio motor koji zahteva niz zahvata nad samim motorom pre nego sˇto dode do prvih zahvata njegove ugradnje. Na slici koja sledi je prikazan takav sklop koji zahteva izvrsˇavanje niza zahvata u definisanom redosledu da bi se dalje ugradio u sklop. 00005 00001 00023 00024 00025 00036 00027 00028 00029 00030 00033 Slika 5.3: Skup zahvata sa nadredenim sklopom koji je istovremeno i podredeni sklop U slucˇaju zahvata sa slike (5.3), podskup Pnad1→pod1 tabele (5.2) je: Pnad1→pod1 = { 〈00005, 00005, 00001, 1〉, 〈00005, 00005, 00023, 2〉, 〈00005, 00005, 00024, 3〉, 〈00005, 00005, 00025, 4〉, 〈00005, 00005, 00026, 5〉, 〈00005, 00005, 00027, 6〉, 〈00005, 00005, 00028, 7〉, 〈00005, 00005, 00029, 8〉, 〈00005, 00005, 00030, 9〉, 〈00005, 00005, 00033, 10〉 } Ovakvi zahvati narusˇavaju strukturu stabla (pojavljuju se ciklusi) kojim je sastavnica defi- nisana. Algoritam za generisanje druge hijerarhijske sastavnice mora na odgovarajuc´i nacˇin tretirati ovu situaciju. 100 Sistem odrzˇavanja vazduhoplova Projektovanje algoritma za generisanje druge sastavnice 5.2.3 Zahvat ima nadredeni i podredeni sklop i to su razlicˇiti sklopovi Pokazalo se u razlicˇitim fazama odrzˇavanja da pokusˇaj ugradnje jednog podsklopa izaziva niz provera i aktivnosti - zahvata na razlicˇitim podsistemima - podsklopovima. Svi ovi zahvati se posebno kontroliˇsu jer obezbeduju dobro funkcionisanje sklopa. Na sledec´oj slici je prikazan primer takvog zahvata: 00002 00011 00011 00033 00012 00013 00033 00014 00015 00033 00017 00018 00033 00008 00033 00033 00033 00033 00009 Slika 5.4: Skup zahvata sa nadredenim sklopom i podredenim sklopovima U slucˇaju zahvata sa slike (5.4), podskup Pnad1→pod2 tabele (5.2) je: Pnad1→pod2 = { 〈00002, 00008, 00010, 1〉, 〈00002, 00008, 00011, 2〉, 〈00002, 00008, 00033, 3〉, 〈00002, 00008, 00012, 4〉, 〈00002, 00008, 00013, 5〉, 〈00002, 00008, 00033, 6〉, 〈00002, 00008, 00014, 7〉, 〈00002, 00008, 00015, 8〉, 〈00002, 00008, 00016, 9〉, 〈00002, 00008, 00033, 10〉, 〈00002, 00008, 00017, 11〉, 〈00002, 00008, 00018, 12〉, 〈00002, 00008, 00033, 13〉, 〈00002, 00009, 00019, 1〉, 〈00002, 00009, 00033, 2〉, 〈00002, 00009, 00020, 3〉, 〈00002, 00009, 00033, 4〉 } 101 Sistem odrzˇavanja vazduhoplova Projektovanje algoritma za generisanje druge sastavnice Ovaj slucˇaj je posebno slozˇen i predstavlja problem u projektovanju tehnologije odrzˇavanja. 5.2.4 Zahvat ima podredeni i nema nadredeni sklop Zahvat nad korenom hijerarhije je najcˇesˇc´e ovog tipa. Ovaj tip zahvata nije posebno zanimljiv za analizu. 5.2.5 Algoritam druge hijerarhijske sastavnice Rekurzija se prirodno namec´e jer je to u osnovi i strukture podataka (5.2) i osnovnog algoritma za formiranje hijerarhijske sastavnice. Algoritam za generisanje druge hijerarhijske sastanice se mozˇe dobiti razradom osnovnog algoritma (4.1) koja na odgovarajuc´i nacˇin tretira situacije opisane u prethodnoj analizi zahvata (5.1). 102 Sistem odrzˇavanja vazduhoplova Projektovanje algoritma za generisanje druge sastavnice Algoritam 5.1 Rekurzivno generisanje druge sastavnice void napravi_tbom( c_ident, n_nivo ) { local sledeci, c_ident_pod; if ( !dbseek( tehnologija, c_ident ) ) { dbappend( tbom , n_nivo, c_ident, "00000", tehnologija.ident, tehnologija.red ); return; } while( !dbeof( tehnologija ) && tehnologija.ident_nad == c_ident ) { c_ident_pod = tehnologija.ident_pod; if ( c_ident_pod == c_ident ) { while( !dbeof( tehnologija ) && tehnologija.ident_nad == c_ident && tehnologija.ident_pod == c_ident ) { dbappend( tbom , n_nivo, c_ident, c_ident, tehnologija.ident, tehnologija.redosled ); dbskip( tbom ); } } if ( c_ident_pod == "00000" ) { while( !dbeof( tehnologija ) && tehnologija.ident_nad == c_ident_pom && tehnologija.ident_pod == "00000" ) { dbappend( tbom , n_nivo, c_ident, "00000", tehnologija.ident, tehnologija.redosled ); dbskip( tbom ); } } sledeci = dbnext( tehnologija ); dbappend( tbom , n_nivo, c_ident, tehnologija.ident_pod, tehnologija.ident, tehnologija.redosled ); napravi_tbom( tehnologija.ident, n_nivo+1 ); dbgoto( tehnologija, sledeci ); } return; } 103 Sistem odrzˇavanja vazduhoplova Projektovanje algoritma za generisanje druge sastavnice Rezulat rada ovog algoritma se smesˇta u tabelu koja ima sledec´u strukturu: nivo ::= 〈NUMERIC, 5〉 ident nad ::= artikli.ident ident pod ::= artikli.ident ident ::= operacije.ident redosled ::= 〈NUMERIC, 5〉 zahvat ::= 〈nivo, ident nad, ident pod, ident, redosled〉 TBOM := {zahvat} (5.3) U Dodatku B dat je primer obrade podataka opisanim algoritmom, ulazni podaci su dati u (2.1), a rezltat obrade je dat u (2.2) 104 Sistem odrzˇavanja vazduhoplova Proracˇun vremena 5.3 Proracˇun vremena 5.3.1 Osnovne pretpostavke Neophodno je pre svega prosˇiriti strukturu tabele operacije (5.1) tako da ukljucˇuje podatak o vremenu trajanja operacije [17]. To se mozˇe izvesti na sledec´i nacˇin (5.4): ident ::= 〈CHAR, 5,FORMAT : 99999,AUTONUMBER〉 sifra ::= 〈CHAR, 15〉 naziv ::= 〈CHAR, 40〉 vreme ::= 〈NUMERIC, 10.4〉 zahvat ::= 〈ident, sifra, naziv, opis, vreme, ∗〉 operacije := {zahvat : PRIMARY KEY IS ident} (5.4) Slicˇno prosˇirimo i strukturu tabele tehnologija (5.2) i imac´emo (5.5): ident nad ::= artikli.ident ident pod ::= artikli.ident ident ::= operacije.ident redosled ::= 〈NUMERIC, 5〉 napomena ::= 〈CHAR, 40〉 vremeprip ::= 〈NUMERIC, 10.4〉 vremeizr ::= 〈NUMERIC, 10.4〉 zahvat ::= 〈ident nad, ident pod, ident, redosled, napomena, vremeprip, vremeizr, ∗〉 tehnologija := {zahvat : PRIMARY KEY IS ident nad+ ident pod+ redosled} (5.5) gde je: vremeprip pomoc´no masˇinsko vreme vremeizr tehnolosˇko masˇinsko vreme Ova vremena su detaljno objasˇnjena u Dodatku C. U nastavku pretpostavimo da u tabeli tehnologija postoje sledec´i zapisi (5.1): Zapisi (5.1) su karakteristicˇni za sklopove koji nemaju podredene, ali se nad njima moraju izvesti odredene operacije. Zapisi (5.2) su karakteristicˇni za sklopove koji se nalaze visoko u sastavnicama i nad njima se moraju izvesti odredene operacije tako da su u pogledu zahvata sami sebi podsklopovi. Konacˇno zapisi (5.3) opisuju nizove zahvata koji se odnose na sklop koji ima dva podredena sklopa. 105 Sistem odrzˇavanja vazduhoplova Proracˇun vremena 5.3.2 Odredivanje maksimalnog vremena Prvi korak je odredivanje maksimalnog vremena trajanja pojedine operacije: maxvreme = vremeprip+ vremeizr Maksimalna vremena pojedinih operacija se mogu dobiti jednostavnim upitom, u slucˇaju operacija datih u (5.1) rezultat je sledec´i (5.4): ident n ident p operacija redosled vremeprip vremeizr maxvr 00011 - 00010 1 20 0.20 20.20 00011 - 00011 2 20 0.20 20.20 00011 - 00033 3 - - 0 00011 - 00021 4 30 0.60 30.60 00011 - 00031 5 - - 0 00011 - 00032 6 30 0.05 30.05 00011 - 00022 7 30 1.20 31.20 00011 - 00033 8 - - 0 Tabela 5.4: Maksimalno vreme operacije 5.3.3 Odredivanje vremena kompletiranja Neka je maksimalno vreme operacije odredeno na prethodno opisani nacˇin, vreme kompleti- ranja niza operacija se mozˇe odrediti na sledec´i nacˇin: vremenorm = ∑ maxvreme U slucˇaju (5.4), nakon grupisanja na nivou sklopa imac´emo (5.5): Tabela 5.5: Vreme kompletiranja ident n ident p vremenorm 00011 - 132.25 sˇto je dovoljno za dobijanje neophodnog izvesˇtaja. Dakle mozˇemo pretpostaviti postojanje niza zapisa oblika (5.6): 106 Sistem odrzˇavanja vazduhoplova Proracˇun vremena Tabela 5.6: Vreme kompletiranja ident n ident p vremenorm 00001 00001 256.00 00002 00002 47.60 00002 00008 252.20 00002 00009 61.00 00003 00003 47.60 00003 00009 71.20 00003 00010 242.00 00004 - 170.10 00005 00005 316.50 00011 - 132.25 5.3.4 Algoritam proracˇuna vremena Iskoristimo prvu hijerarhijsku sastavnicu datu u (4.25), odnosno pretpostavimo postojanje zapisa (5.7): Tabela 5.7: GBOM nivo ident n ident p 1 00001 00002 2 00002 00008 3 00008 - 2 00002 00009 3 00009 - 1 00001 00003 2 00003 00009 3 00009 - 2 00003 00010 3 00010 - 1 00001 00004 2 00004 - 1 00001 00005 2 00005 00011 3 00011 - 1 00001 00006 2 00006 - 1 00001 00007 2 00007 - 107 Sistem odrzˇavanja vazduhoplova Proracˇun vremena Na osnovu rezultata iz (5.6) proracˇun vremena se mozˇe dobiti na sledec´i nacˇin: Prvi korak Terminalnim cvorovima se dodeljuju odgovarajuc´a vremena koja se preuzimaju iz (5.6), rezultat ove obrade je (5.8): Tabela 5.8: GBOM-nivo 3 nivo ident n ident p vreme 1 00001 00002 2 00002 00008 3 00008 - 0.00 2 00002 00009 3 00009 - 0.00 1 00001 00003 2 00003 00009 3 00009 - 0.00 2 00003 00010 3 00010 - 0.00 1 00001 00004 2 00004 - 170.10 1 00001 00005 2 00005 00011 3 00011 - 132.25 1 00001 00006 2 00006 - 0.00 1 00001 00007 2 00007 - 0.00 Drugi korak Iterativno se vremena izracˇunavaju na viˇsim nivoima, tako sˇto se svakoj grani na datom nivou pridruzˇi zbir vremena sa same grane iz (5.6) i vremena pridruzˇenog podsklopu na datoj grani. U navedenom primeru dobic´emo (5.9): 108 Sistem odrzˇavanja vazduhoplova Proracˇun vremena Tabela 5.9: GBOM-nivo 2a nivo ident n ident p vreme 1 00001 00002 2 00002 00008 252.20+0.00 2 00002 00009 61.00+0.00 1 00001 00003 2 00003 00009 71.20+0.00 2 00003 00010 242.00+0.00 1 00001 00004 2 00004 - 170.10 1 00001 00005 2 00005 00011 0.00+132.25 1 00001 00006 2 00006 - 0.00 1 00001 00007 2 00007 - 0.00 Zatim se odreduje vreme koje odgovara nadredenom sklopu na datom nivou i ono je jednako maksimalnom od svih vremena koja odgovaraju granama u kojima je dati sklop nadredeni, odnosno (5.10): Tabela 5.10: GBOM-nivo 2b nivo ident n ident p vreme 1 00001 00002 2 00002 - max{252.20, 61.00} 1 00001 00003 2 00003 - max{71.20, 242.00} 1 00001 00004 2 00004 - max{170.10} 1 00001 00005 2 00005 - max{132.25} 1 00001 00006 2 00006 - max{0.00} 1 00001 00007 2 00007 - max{0.00} Jedan korak iteracije se zavrsˇava tako sˇto se odgovarajuc´e vreme koje odgovara sklopu na datom nivou uvec´ava za vreme koje odgovara operaciji u kojoj je dati sklop isto- vremeno i nadredeni i podredeni, a sadrzˇano je u (5.6). U datom primeru imac´emo 109 Sistem odrzˇavanja vazduhoplova Proracˇun vremena (5.11): Tabela 5.11: GBOM-nivo 2c nivo ident n ident p vreme 1 00001 00002 2 00002 - 252.20+47.60 1 00001 00003 2 00003 - 242.00+47.60 1 00001 00004 2 00004 - 170.10+ 0.00 1 00001 00005 2 00005 - 132.25+316.50 1 00001 00006 2 00006 - 0.00+ 0.00 1 00001 00007 2 00007 - 0.00+ 0.00 Dakle posle jedne iteracije dobic´emo raspodelu vremena na drugom nivou (5.12): Tabela 5.12: GBOM-nivo 2d nivo ident n ident p vreme 1 00001 00002 2 00002 - 299.80 1 00001 00003 2 00003 - 289.60 1 00001 00004 2 00004 - 170.10 1 00001 00005 2 00005 - 448.75 1 00001 00006 2 00006 - 0.00 1 00001 00007 2 00007 - 0.00 Sledec´a iteracija daje proracˇun vremena na prvom nivou, odnosno maksimalno vreme skla- panja finalnog sklopa 00001. Tok obrade dat je sledec´im tabelama (5.13), (5.14) i (5.15): 110 Sistem odrzˇavanja vazduhoplova Proracˇun vremena Tabela 5.13: GBOM-nivo 1a nivo ident n ident p vreme 1 00001 00002 299.80+0.00 1 00001 00003 289.60+0.00 1 00001 00004 170.10+0.00 1 00001 00005 448.75+0.00 1 00001 00006 0.00+0.00 1 00001 00007 0.00+0.00 Tabela 5.14: GBOM-nivo 1b nivo ident n ident p vreme 1 00001 - max{299.80, 289.60, 170.10, 448.75, 0.00, 0.00} Tabela 5.15: GBOM-nivo 1c nivo ident n ident p vreme 1 00001 - 448.75+256.00 Konacˇno dobijamo (5.16): Tabela 5.16: GBOM-nivo 1d nivo ident n ident p vreme 1 00001 - 704.75 111 Sistem odrzˇavanja vazduhoplova Proracˇun vremena T ab el a 5. 1: O p er ac ij e n ad sk lo p om I id e n t n id e n t p o p e ra c ij a re d o sl e d n a p o m e n a v re m e p ri p v re m e iz r 00 01 1 - 00 01 0 1 S ecˇ en je 2 0 0 .2 0 00 01 1 - 00 01 1 2 P om o c´n ik p ri se cˇe n ju 2 0 0 .2 0 00 01 1 - 00 03 3 3 K on tr ol a se cˇe n ja - - 00 01 1 - 00 02 1 4 Is ec an je u gl ov a 3 0 0 .6 0 00 01 1 - 00 03 1 5 R eg la zˇa al at a - - 00 01 1 - 00 03 2 6 P ro b ij an je 3 0 0 .0 5 00 01 1 - 00 02 2 7 S av ij an je 3 0 1 .2 0 00 01 1 - 00 03 3 8 K on tr ol a iz ra d e ko m ad a - - 112 Sistem odrzˇavanja vazduhoplova Proracˇun vremena T ab el a 5. 2: O p er ac ij e n ad sk lo p om II id e n t n id e n t p o p e ra c ij a re d o sl e d n a p o m e n a v re m e p ri p v re m e iz r 00 00 5 00 00 5 00 00 1 1 H em ij sk a ob ra d a 3 0 1 00 00 5 00 00 5 00 02 3 2 Iz ra d a la m el a 3 0 3 .5 00 00 5 00 00 5 00 02 4 3 Iz ra d a ce v cˇi ca 9 0 3 00 00 5 00 00 5 00 02 5 4 S as ta v lj an je sa c´a 3 0 1 8 00 00 5 00 00 5 00 02 6 5 P ecˇ en je sa c´a - - 00 00 5 00 00 5 00 02 7 6 U gr ad n ja ce v n ih zi d ov a 3 0 8 00 00 5 00 00 5 00 02 8 7 K ap il ar n o le m lj en je ce v n ih zi d ov a 3 0 5 00 00 5 00 00 5 00 02 9 8 P ra n je b lo ka sa c´a - - 00 00 5 00 00 5 00 03 0 9 Is p it iv an je b lo ka sa c´a 3 0 8 00 00 5 00 00 5 00 03 3 10 K on tr ol a u iz ra d i b lo ka sa c´a - - 113 Sistem odrzˇavanja vazduhoplova Proracˇun vremena T ab el a 5. 3: O p er ac ij e n ad sk lo p om II I id e n t n id e n t p o p e ra c ij a re d o sl e d n a p o m e n a v re m e p ri p v re m e iz r 00 00 2 00 00 8 00 01 0 1 S ecˇ en je 2 0 0 .2 0 00 00 2 00 00 8 00 01 1 2 P om o c´n ik p ri se cˇe n ju 2 0 0 .2 0 00 00 2 00 00 8 00 03 3 3 K on tr ol a se cˇe n ja - - 00 00 2 00 00 8 00 01 2 4 Is ec an je 3 0 0 .8 0 00 00 2 00 00 8 00 01 3 5 O p se ca n je 3 0 3 00 00 2 00 00 8 00 03 3 6 K on tr ol a op se ca n ja - - 00 00 2 00 00 8 00 01 4 7 S av ij an je 3 0 1 .5 00 00 2 00 00 8 00 01 5 8 S av ij an je i d ot er iv an je 3 0 4 00 00 2 00 00 8 00 01 6 9 Z av ar iv an je 1 5 4 00 00 2 00 00 8 00 03 3 10 K on tr ol a d ot er iv an ja i za va ri va n ja - - 00 00 2 00 00 8 00 01 7 11 F re zo va n je 3 0 1 .5 0 00 00 2 00 00 8 00 01 8 12 P er tl ov an je 3 0 2 00 00 2 00 00 8 00 03 3 13 K on tr ol a iz ra d e ko m ad a - - 00 00 2 00 00 9 00 01 9 1 S ecˇ en je ce v i 3 0 0 .5 0 00 00 2 00 00 9 00 03 3 2 K on tr ol a se cˇe n ja - - 00 00 2 00 00 9 00 02 0 3 S ik n ov an je 3 0 0 .5 0 00 00 2 00 00 9 00 03 3 4 K on tr ol a iz ra d e ko m ad a - - 114 Glava 6 Zakljucˇak Analizom kako prakticˇnih resˇenja, tako i teorijskih istrazˇivanja u sistemu odrzˇavanja va- zduhoplova, mozˇe se zakljucˇiti da ima prostora za znacˇajnija unapredenja u ovoj oblasti. Savremeni sistemi odrzˇavanja obuhvataju i upravljanje odrzˇavanjem, preciznije zasnovani su na automatizovanoj podrsˇci odrzˇavanju primenom racˇunara (Computer Integrated Mainte- nance Management). Samim tim jedan od vazˇnih zahteva je obezbediti model podataka koji je dovoljno bogat da bi mogao, na relativno lak nacˇin prihvatiti i u sebe ukljucˇiti razlicˇite koncepte realnog sistema zajedno sa svojim atributima i medusobnim vezama. Hijerarhij- ske strukture podataka (strukture podataka tipa stablo) su posebno interesantne u sistemu odrzˇavanja vazduhoplova i one su predmet istrazˇivanja u Glavi 2. Rekurzivnost koja je u osnovi hijerarhijske strukture podataka odnosno stabla koji je reprezent ovakve strukture podataka, mozˇe biti problem u efikasnom upravljanju sistemom odrzˇavanja vazduhoplova. U Glavi 2 su date nove karakterizacije stabla, koje daju osnov za nerekurzivne modele hijerar- hijske strukture podataka: − model sa izlistanim putanjama − model sa ugnjezˇdenim skupovima − model sa ugnjezˇdenim intervalima Teoreme (2.3.2) i (2.3.3) odnosno (2.3.6) i (2.3.7) daju vezu izmedu proizvoljne hijerarhij- ske strukture i hijerarhijske strukture uredene relacijom podskup odnosno nadskup. Drugim recˇima svako stablo je izomorfno stablu koje je uredeno relacijom podskup odnosno nadskup. Pogodnim indeksiranjem cˇorova stabla u skupu prirodnih brojeva, relacijama podskup, od- nosno nadskup c´e odgovarati uobicˇajeno leksikografsko uredenje nizova prirodnih brojeva (model sa izlistanim putanjama), odnosno uobicˇajeno uredenje intervala prirodnih brojeva (model sa ugnjezˇdenim skupovima). Na ovaj nacˇin se pojedine operacije nad hijerarhijskom strukturom podataka mogu efikasno implementirati. Slabosti pomenuta dva modela se mogu otkloniti, ako se cˇvorovi stabla indeksiraju u skupu intervala realnih brojeva. Posebno model sa ugnjezˇdenim intervalima otklanja neke od uocˇenih slabosti. U ovoj klasi modela analizi- rana su dva tipa: − binarni model sa ugnjezˇdenim intervalima 115 Zakljucˇak − ternarni model sa ugnjezˇdenim intervalima Analizom slabosti binarnog modela sa ugnjezˇdenim intervalima, koji ne podrzˇava direktno operaciju umetanja cˇvora, predlozˇen je ternarni model sa ugnjezˇdenim intervalima koji po- menutu operaciju direktno podrzˇava. U kontekstu ogranicˇenih resursa u sistemu za odrzˇavanje vazduhoplova posebno su intere- santne optimalne strategije odrzˇavanja. Bitan segment sistema za upravljanje odrzˇavanjem je planiranje odrzˇavanja. Jedan od osnovnih problema izmedu ostalog je neizvesnost dogadaja koji znacˇajno uticˇu na samo planiranje. Recˇ je o dogadajima koji su po svojoj prirodi slucˇajni. Ovi slucˇajni dogadaji su pored ostalog vezani za: − vremenski trenutak otkaza rezervnog dela − vremenski trenutak zahteva za nekim delom − vreme isporuke, odnosno vreme potrebno za sklapanje (pripremu) rezervnog dela Planiranje odrzˇavanja u kontekstu slucˇajnih faktora je predmet istrazˇivanja u Glavi 3. Po- sebno analizira se planiranje odrzˇavanja u slucˇaju kada skup aktivnosti ima hijerarhijsku strukturu i pri tome je trajanje pojedinih aktivnosti iz datog skupa aktivnosti slucˇajna velicˇina. Pod pretpostavkom da aktivnost na viˇsem nivou hijerarhije ne mozˇe zapocˇeti pre nego sˇto su zavrsˇene sve aktivnosti na nizˇem nivou hijerarhije i da su poznati gubici koji nastaju u slucˇaju da se sa nekim aktivnostima kasni, odnosno da su poznati gubici u slucˇaju da su neke aktivnosti preuranjene, potrebno je formirati optimalnu strategiju aktiviranja ak- tivnosti iz datog skupa. Bez gubitka opsˇtosti pretpostavljeno je da su aktivnosti iz skupa aktivnosti zapravo aktivnosti sklapanja (pripreme) rezervnog dela. Pod ovim pretpostavkama funkcija koju treba optimizoati je funkcija ocˇekivanih trosˇkova i ona ukljucˇuje trosˇkove: − skladiˇstenja u slucˇaju da je aktivnost sklapanja zavrsˇena pre utvrdenog roka − kasˇnjenja u slucˇaju da je aktivnost sklapanja zavrsˇena nakon utrdenog roka U prvom delu Glave 3 problem planiranja aktivnosti u slucˇaju jedne linije sklapanja je resˇen svodenjem na poznati newsboy problem. Zatim je dato resˇenje problema viˇsestruke neodredenosti na jednoj grani hijerarhije, kada su i trajanje aktivnosti sklapanja i utvrdeni rok slucˇajne velicˇine. Sˇto se ticˇe problema sklapanja (pripreme) rezervnog dela u opsˇtem slucˇaju, kada se radi o hijerarhiji sa proizvoljnim brojem nivoa, on je isuviˇse komplikovan da bi se postavila funkcija ocˇekianih trosˇkova. U slucˇaju hijerarhije koja se opisuje stablom visine jedan, predlozˇena su dva modela: − simultani zahtev I − simultani zahtev II Za svaki od modela je formirana funkcija ocˇekivanih trosˇkova i dokazana njena konvek- snost (Teorema (3.3.1) i Teorema (3.4.1)) cˇime se odredivanje optimalnog resˇenja svodi na odredivanje lokalnog minimuma funkcije ocˇekianih trosˇkova. Dalje je pokazano kako se resˇenje problema na stablu sklapanja rezervnog dela visine dva, mozˇe produzˇiti na stablo sklapanja 116 Zakljucˇak proizvoljne visine. Ovo produzˇenje se svodi na iterativnu primenu resˇenja na stablu sklapanja visine dva. Na kraju su date procedure koje (obradom odgovarajuc´e hijerarhijske strukture podataka) daju optimalna vremena aktiviranja pojedinih aktivnosti sklapanja. Jasno je da se navedeni rezultati mogu primeniti na planiranje proizvoljnog skupa aktivnosti koji ima hijerarhijsku strukturu. Vazduhoplovi su savremena saobrac´ajna sredstva vrhunske tehnologije sa velikim brojem komponenti i kompleksnom strukturom. Pojedine komponente vazduhoplova se koriste na razlicˇit nacˇin, trpe razlicˇita opterec´enja i odrzˇavaju se po programu koji je njima najbolje prilagoden. Jedan od nacˇina savladavanja slozˇenosti je takozvana hijerarhijska dekompozi- cija. Slozˇeni koncept se na jednom nivou apstrakcije posmatra kao jedinstvena celina. Na nizˇem nivou apstrakcije se posmatra kao koncept koji se sastoji od delova (komponenti). Uza- stopnom primenom opisanog postupka dobija se takozvana hijerarhijska sastavnica. Dakle jedan od bitnih koncepata u sistemu odrzˇavanja vazduhoplova jeste sastavnica. Sastavnica je najprostije recˇeno, lista komponenti koji su sastavni delovi posmatranog objekta. Pri tome se vodi racˇuna o vezama izmedu sastavnih komponenti, pa je u osnovi sastavnice hijerarhijska struktura podataka. Sastavnica kao hijerarhijska struktura podataka u sistemu odrzˇavanja vazduhoplova je predmet istrazˇivanja u Glavi 4. U Glavi 2 su analizirani neki modeli hije- rarhijske strukture podataka. U analizi modela sva pazˇnja je bila skoncentrisana na jedan aspekt modela, konkretno analizirana je efikasnost obrade hijerarhijske strukture podataka u datom modelu. Drugi problem je obezbediti kvalitetan sadrzˇaj hijerarhijske strukture poda- taka, odnosno u sistemu za upravljanje odrzˇavanjem vazduhoplova treba obezbediti kvalitetnu sastavnicu. Sastavnice predstavljaju posebnu vrstu stabla i u susˇtini su hijerarhijske struk- ture podataka koje su osnov za modeliranje problema iz prethodnih poglavlja, samim tim su posebno interesantne u sistemu za odrzˇavanje vazduhoplova. U Glavi 4 daje se metodicˇki pri- stup resˇavanju problema generisanja sadrzˇajno kvalitetne sastavnice. Pre svega neophodno je sistematizovati podatke koji bi bili podrsˇka kreiranju sastavnice. Pomenuta sistematizacija podataka je izvedena navodenjem opisa viˇse struktura podataka, cˇije se postojanje dalje pod- razumeva jer obezbeduju sadrzˇaj kojim c´e se sastavnice snabdeti. Dalje se daje opis strukture sastavnice koji odreduje sadrzˇaj same sastavnice. Pri tome se razlikuju dva tipa sastavnica: − modularna − hijerarhijska i oba tipa su detaljno obradeni. Predlozˇena struktura sastavnica je fleksibilna i ta fleksibilnost se ogleda u tome sˇto se mozˇe elementarno prosˇiriti i na taj nacˇin obezbediti dodatni sadrzˇaj. U slucˇaju modularnih sastavnica dat je primer kako se mozˇe modelirati uredenje potomaka cˇvora stabla, koje se dalje u sistemu odrzˇavanja vazduhoplova mozˇe interpretirati kao redosled ugradnje delova ili josˇ viˇse kao redosled izvodenja aktivnosti odrzˇavanja. Slicˇno dat je primer kako se mozˇe modelirati viˇsestruka podredenost pojedinih cˇvorova stabla koja se dalje u sistemu odrzˇavanja mozˇe interpretirati kao neophodna kolicˇina pojedinih podsklopova za sklapanje nadredenog sklopa. Kako su modularne sastanice gradivni blokovi hijerarhijske sastavnice, fleksibilnost strukture modularne sastavnice se prenosi na hijerarhijsku sastavnicu. Na kraju Glave 4 uvodi se pojam genericˇke sastavnice, a zatim se daje odgovarajuc´a procedura za generisanje hijerarhijske sastavnice. 117 Zakljucˇak Imajuc´i za osnov fleksibilnu strukturu sastavnice, u Glavi 5 se uvodi pojam druge hijerar- hijske sastavnice. Druga hijerarhijska sastavnica je sadrzˇajno rasˇirenje hijerarhijske sastav- nice uvedene u Glavi 4. Posebno druga hijerarhijska sastavnica obezbeduje sadrzˇaj kojim se opisuje postupak simultane ugradnje podsklopova u nadredeni sklop o cˇemu je bilo recˇi u Glavi 3, s tom razlikom sˇto je u Glavi 3 ova problematika istrazˇivana sa aspekta optimizacije trosˇkova. Sam postupak ugradnje se uobicˇajenom tehnikom dekompozicije, rasˇcˇlanjuje na niz zahvata koji se zatim modeliraju u strukturi druge hijerarhijske sastavnice. Zahvati blizˇe odreduju prirodu veze izmedu nadredenog i podredenog sklopa. Nakon sˇto je izvedena studija slucˇaja koji se koriste u praksi, prepoznata su cˇetri tipa zahvata prema tome sˇta su krajevi veze izmedu nadredenog i podredenog sklopa: − zahvat ima nadredeni i nema podredeni sklop − zahvat ima nadredeni i podredeni sklop i pri tome su to isti sklopovi − zahvat ima nadredeni i podredeni sklop i to su razlicˇiti sklopovi − zahvat ima podredeni i nema nadredeni sklop Zatim je data odgovarajuc´a procedura za generisanje druge hijerarhijske sastavnice, koja na odgovarajuc´i nacˇin tretira prepoznate tipove zahvata. Na kraju je dat algoritam za proracˇun neophodnih vremena u postupku simaultane ugradnje na viˇse nivoa. U daljem radu svakako bi se iˇslo na softversku implementaciju predlozˇenih modela stabla. Ocigledno je da se predlozˇenim modelima hijerarhijska struktura podataka mozˇe implemen- tirati linearnom strukturom podataka kojima su pridruzˇena odgoarajuc´a obelezˇja. Kom- plikovan hijerarhijski odnos izmedu elemenata strukture se prenosi na elementaran odnos izmedu obelezˇja elemenata linearne strukture. Sˇto se ticˇe odrzˇavanja vazduhoplova potrebno je testirati predlozˇene modele planiranja odrzˇavanja. Pre svega neophodno je obezbediti od- govarajuc´e raspodele vremena trajanja pojedinih aktivnosti odrzˇavanja, a to se mozˇe izvesti nekim od standardnih metoda statisticˇke obrade podataka. 118 Literatura [1] I. Arandjelovic´, Z. Mitrovic´, and V. Stojanovic´. Verovatnoc´a i Statistika. Zavod za udzˇbenike, Beograd, 2011. [2] Sven Axsater. Planning order releases for an assembly system with random operation times. OR Spectrum, Vol. 27(2-3):459–470, 2005. [3] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 7th edition, 2009. [4] Franjo Cecelja. Manufacturing Information and Data SystemsM. Penton Press, London, 2002. [5] Joe Celko. Joe Celko’s Trees and hierarchies in SQL for smarties. Morgan-Kaufmann, 2004. [6] Fangruo Chen. Market segmentation, advanced demand information, and supply chain performance. Manufacturing & Service Operations Management, Vol. 3(1):53–67, 2001. [7] Vadim Tropashko Oracle Corp. Nested intervals tree encoding in sql. SIGMOD Record, Vol. 34(2):47–52, 2005. [8] Mohsen Elhafsi. Optimal leadtimes planning in serial production systems with earliness and tardiness costs. IIE Transactions, Vol. 34(3):233–243, 2002. [9] W. Hopp and M. Spearman. Setting safety leadtimes for purchased components in assembly systems. IIE Transactions, Vol. 25(2):1–11, 1993. [10] F. Karaesmen, J.A. Buzacott, and Y. Dallery. Integrating advance order information in make-to-stock production systems. IIE Transactions, Vol. 34(8):649–662, 2002. [11] Donald E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, Reading, 1969. [12] Cˇ. Mitrovic´, D. Bekric´, N. Petrovic´, and S. Radojevic´. Relevantnost ljudskih faktora u vazduhoplovstvu. XXXII Naucˇno - strucˇni skup Odrzˇavanje masˇina i opreme, pages 209–220, 2007. [13] I. Moerdijk and J. Oosten. Sets, Models and Proofs. Utrecht University, 2006. [14] Pavle Mogin. Strukture podataka i organizacija datoteka. Racˇunarski fakultet, Beograd, 2008. 119 Literatura Literatura [15] John Moubray. Reliability Centred Maintenance RCM. Butterworth-Heinnemann Ltd., Oxford, 2nd edition, 1997. [16] S. Radojevic´, Cˇ. Mitrovic´, and M. Arandelovic´. Priprema sastavnica u odrzˇavanju. XXXIII Naucˇno – strucˇni skup Odrzˇavanje masˇina i opreme, 2008. [17] S. Radojevic´, Cˇ. Mitrovic´, M. Arandelovic´, and N. Dondur. Maksimalno vreme odrzˇavanja aviona dobijeno sastavnicom. XXXIII Naucˇno – strucˇni skup Odrzˇavanje masˇina i opreme, 2008. [18] S. Radojevic´, Cˇ. Mitrovic´, M. Lecˇic´, and N. Dondur. Edukacija korisnika za koriˇsc´enje ebom case alata. 33. JUPITER konferencija, 26. CIM u strategiji tehnolosˇkog razvoja industrije prerade metala, Zbornik radova, Vol. 1. [19] S. Radojevic´ and Z.A. Veljkovic´. Rekurzivni algoritam za stvaranje prve hijerarhijske sastavnice. 28. JUPITER konferencija, 30. simpozijum Upravljanje proizvodnjom u in- dustriji prerade metala, Zbornik radova, Vol. 4. [20] S. Radojevic´ and Z.A. Veljkovic´. Osnovne pretpostavke za stvaranje meta-jezika formi- ranja sastavnica. SIE 98, pages 231–234, 1998. [21] S. Radojevic´, Z.A. Veljkovic´, and B. Milinkovic´ Katalinic´. Tehnolosˇka sastavnica u planiranju proizvodnje. Drugi skup privrednika i naucˇnika, Beograd, 2004. [22] Slobodan Radojevic´. Formiranje sastavnica gotovih proizvoda simuliranom rekurzijom i pokazivacˇima u relacionim bazama podataka. Zbornik radova Masˇinskog Fakulteta, pages 40–43, 1991. [23] Slobodan Radojevic´. Algoritam za formiranje sastavnica gotovih proizvoda u relacioniim bazama podataka. Tehnika – Organizacija, pages 46–50, 1994. [24] Bosˇko Rasˇuo. Vazduhoplovnotehnicko obezbedenje. Vojna akademija, Beograd, 2003. [25] Walter Rudin. Principles of mathematical analysis. McGraw-Hill, Inc., 3rd edition, 1976. [26] J.S. Song, C.A. Yano, and P. Lerssrisuriya. Contract assembly: Dealing with combined supply lead time and demand quantity uncertainty. Manufacturing & Service Operations Management 2, Vol. 2(3):287–296, 2000. [27] D. Stevanovic´, M. C´iric´, S. Simic´, and V. Baltic´. Discrete Mathematics – Fundamentals of Combinatorics and Graph Theory. Mathematical Society of Serbia, Beograd, 2007. [28] William J. Stevenson. Operations Management. McGraw-Hill/Irwin, 10th edition, 2009. [29] O. Tang and R.W. Grubbstrom. The detailed coordination problem in a two-level assem- bly system with stochastic lead times. International Journal of Production Economics, Vol. 81-82(1):415–429, 2003. [30] Candace A. Yano. Stochastic leadtimes in two-level assembly systems. IIE Transactions, Vol. 19(4):371–378, 1987. 120 Prilog A Newsboy problem Problem je sledec´i, potrebno je oceniti broj primeraka dnevnih novina koje treba narucˇiti imajuc´i u vidu da je potrazˇnja slucˇajna promenljiva i da na kraju dana neprodate novine gube vrednost . Neka je nabavna cena 10din., a prodajna 20din. i neka se za povrac´aj neprodatog primerka novina dobija 5din. Ocˇigledno je da je resˇenje po kome je broj primeraka koje treba narucˇiti jednak srednjoj vrednosti broja prodatih primeraka na dnevnom nivou neodgovarajuc´e. Ovaj zakljucˇak se mozˇe izvesti iz sledec´e analize: − viˇsak primerka novina koji je neporodat, proizvodi gubitak od 10din− 5din = 5din − manjak primerka novina koji je mogao biti prodat, proizvodi gubitak od 20din− 10din = 10din Dakle gubitak je vec´i ako se ne narucˇi dovoljan broj primeraka nego ako se narucˇi viˇse prime- raka nego sˇto je neophodno. U slucˇaju da se narucˇuje srednja vrednost broja dnevno prodatih primeraka, sa istom frekvencijom c´e se desˇavati situacije kada nema dovoljno primeraka i si- tuacije kada ima viˇsak primeraka. Heuristicˇka analiza nalazˇe da frekvenciju situacije kada nema dovoljno primeraka treba smanjiti u korist ove druge, odnosno treba narucˇivati viˇse od srednje vrednosti broja dnevno prodatih primeraka. Ovo je primer newsboy problema u kome se dati proizvod narucˇuje na pocˇetku izvesnog perioda i mozˇe se koristiti samo u toku tog perioda, a njegovim resˇavanjem se dobija optimalni nivo zaliha. Pretpostavimo da su poznate sledec´e cene kosˇtanja co, cu > 0: − co : cena kosˇtanja po jedinici proizvoda u slucaju pozitivnog nivoa zaliha na kraju perioda u kome je proizvod upotrebljiv (overage cost) − cu : cena kosˇtanja nezadovoljenog zahteva, odnosno cena kosˇtanja po jedinici proizvoda u slucaju negativnog nivoa zaliha na kraju perioda u kome je proizvod upotrebljiv (underage cost) Dalje c´emo pretpostaviti da je broj zahteva D u toku uocˇenog perioda slucˇajna promenljiva. Upravljajuc´i parameter q je broj jedinica proizvoda koji se narucˇuje na pocˇetku perioda. Cilj 121 Newsboy problem je odrediti vrednost parametra q koji minimizira ocˇekivane ukupne trosˇkove na kraju peri- oda. Definiˇsimo sa C(q,D) funkciju ukupnih trosˇkova koji su posledica pozitivnog odnosno negativnog nivoa zaliha na kraju perioda: C(q,D) = co ·max {q −D, 0}+ cu ·max {D − q, 0} (A.1) Ako uvedemo sledec´e oznake: x+ = max {x, 0} (A.2) x− = max {−x, 0} = (−x)+ (A.3) imac´emo: C(q,D) = co · (q −D)+ + cu · (D − q)+ (A.4) Kako vazˇi: x+ = max {x, 0} = x+ max {x− x, 0− x} = x+ max {0,−x} = x+ x− = x+ (−x)+ (A.5) dobijamo: C(q,D) = co · ( (q −D) + (D − q)+)+ cu · (D − q)+ = co · (q −D) + (cu + co) · (D − q)+ (A.6) pa su ocˇekivani trosˇkovi jednaki: Z(q) = E(C(q,D)) = co · (q − E(D)) + (cu + co) · E((D − q)+) (A.7) Teorema A.1. Neka je broj zahteva D u toku uocˇenog perioda diskretna slucˇajna promenljiva sa funkcijom raspodele F (d) = P (D < d), tada je optimalno resˇenje problema (A.7) dato sa: F (q∗) ≤ cu cu + co ≤ F (q∗ + 1) (A.8) Dokaz. Neka je broj zahteva D u toku uocˇenog perioda diskretna slucˇajna promenljiva sa funkcijom raspodele F (d) = P (D) < d), tada je funkcija ocˇekivanih ukupnih trosˇkova: 122 Newsboy problem Z(q) = co · (q − E(D) + (cu + co) · ∑ i≥1 P ((D − q)+ ≥ i) = co · (q − E(D) + (cu + co) · ∑ i≥1 P (D ≥ q + i) = co · (q − E(D) + (cu + co) · ∑ j≥q+1 P (D ≥ j) = co · (q − E(D) + (cu + co) · (E(D)− q∑ j=1 P (D ≥ j)) = coq + cuE(D)− (cu + co) · q∑ j=1 (1− F (j)) = coq + cuE(D)− (cu + co)q + (cu + co) · q∑ j=1 F (j) = cu(E(D)− q) + (cu + co) · q∑ j=1 F (j) a njen prirasˇtaj je: ∆Z(q) = Z(q + 1)− Z(q) = cu · (E(D)− (q + 1)) + (cu + co) · q+1∑ j=1 F (j) − cu · (E(D)− q) + (cu + co) · q∑ j=1 F (j)  = −cu + (cu + co) · F (q + 1) q∗ je optimalno resˇenje ako je: ∆Z(q∗ − 1) ≤ 0 i ∆Z(q∗) ≥ 0, odnosno: −cu + (cu + co)F (q∗) ≤ 0 −cu + (cu + co)F (q∗ + 1) ≥ 0 pa je optimalno resˇenje dato sa: F (q∗) ≤ cu cu + co ≤ F (q∗ + 1)  Teorema A.2. Neka je D neprekidna slucˇajna promenljiva sa gustinom raspodele f i funk- cijom raspodele F , tada je optimalno resˇenje problema (A.7) dato sa: q∗ = F−1 ( cu cu+co ) (A.9) 123 Newsboy problem Dokaz. Neka je broj zahteva D u toku uocˇenog perioda neprekidna slucˇajna promenljiva sa gustinom raspodele f i funkcijom raspodele F , tada su ocˇekivani ukupni trosˇkovi: Z(q) = co · (q − E(D)) + (cu + co) · ∞∫ 0 P (D − q ≥ x) dx = co · (q − E(D)) + (cu + co) · ∞∫ 0 (1− P (D < x+ q))dx = co · (q − E(D)) + (cu + co) · ∞∫ 0 (1− F (x+ q))dx = co · (q − E(D)) + (cu + co) · ∞∫ q (1− F (x))dx Stacionarna tacˇka funkcije ocˇekivanih trosˇkova je resˇenje sledec´e jednacˇine: dZ(q) dq = 0 co − (cu + co) · ∞∫ q f(x)dx = 0 co − (cu + co)(1− F (q)) = 0 −cu + (cu + co)F (q) = 0 F (q) = cu cu + co Kako je: d2Z(q) dq2 = (cu + co)f(q) ≥ 0 funkcija ocˇekivanih ukupnih trosˇkova je konveksna. Neka je pri tome F strogo rastuc´a funk- cija, tada je jedinstveno optimalno resˇenje dato sa: q∗ = F−1 ( cu cu+co )  Newsboy model se mozˇe koristiti u svim situacijama kada treba izvrsˇiti procenu neke slucˇajne velicˇine, a ta procena je rezultat kompromisa izmedu gubitaka u slucˇaju da je vrednost slucˇajne promenljive precenjena i gubitaka koji su posledica potcenjene vrednosti slucˇajne promenljive. 124 Prilog B HSII 2.1 HSII1 P = { 〈00001, 00001, 00001, 1〉, 〈00001, 00001, 00002, 2〉, 〈00001, 00001, 00003, 3〉, 〈00001, 00001, 00004, 4〉, 〈00001, 00001, 00005, 5〉, 〈00001, 00001, 00006, 6〉, 〈00001, 00001, 00007, 7〉, 〈00001, 00001, 00008, 8〉, 〈00001, 00001, 00033, 9〉, 〈00002, 00002, 00001, 1〉, 〈00002, 00002, 00009, 2〉, 〈00002, 00002, 00033, 3〉, 〈00002, 00008, 00010, 1〉, 〈00002, 00008, 00011, 2〉, 〈00002, 00008, 00033, 3〉, 〈00002, 00008, 00012, 4〉, 〈00002, 00008, 00013, 5〉, 〈00002, 00008, 00033, 6〉, 〈00002, 00008, 00014, 7〉, 〈00002, 00008, 00015, 8〉, 〈00002, 00008, 00016, 9〉, 〈00002, 00008, 00033, 10〉, 125 HSII HSII1 〈00002, 00008, 00017, 11〉, 〈00002, 00008, 00018, 12〉, 〈00002, 00008, 00033, 13〉, 〈00002, 00009, 00019, 1〉, 〈00002, 00009, 00033, 2〉, 〈00002, 00009, 00020, 3〉, 〈00002, 00009, 00033, 4〉, 〈00003, 00003, 00001, 1〉, 〈00003, 00003, 00009, 2〉, 〈00003, 00003, 00033, 3〉, 〈00003, 00009, 00019, 1〉, 〈00003, 00009, 00033, 2〉, 〈00003, 00009, 00020, 3〉, 〈00003, 00009, 00033, 4〉, 〈00003, 00010, 00010, 1〉, 〈00003, 00010, 00011, 2〉, 〈00003, 00010, 00033, 3〉, 〈00003, 00010, 00012, 4〉, 〈00003, 00010, 00013, 5〉, 〈00003, 00010, 00033, 6〉, 〈00003, 00010, 00014, 7〉, 〈00003, 00010, 00015, 8〉, 〈00003, 00010, 00016, 9〉, 〈00003, 00010, 00033, 10〉, 〈00003, 00010, 00017, 11〉, 〈00003, 00010, 00018, 12〉, 〈00003, 00010, 00033, 13〉, 〈00004, 00000, 00010, 1〉, 〈00004, 00000, 00011, 2〉, 〈00004, 00000, 00033, 3〉, 〈00004, 00000, 00021, 4〉, 〈00004, 00000, 00022, 5〉, 〈00004, 00000, 00015, 6〉, 〈00004, 00000, 00016, 7〉, 〈00004, 00000, 00033, 8〉, 〈00005, 00005, 00001, 1〉, 126 HSII HSII2 〈00005, 00005, 00023, 2〉, 〈00005, 00005, 00024, 3〉, 〈00005, 00005, 00025, 4〉, 〈00005, 00005, 00026, 5〉, 〈00005, 00005, 00027, 6〉, 〈00005, 00005, 00028, 7〉, 〈00005, 00005, 00029, 8〉, 〈00005, 00005, 00030, 9〉, 〈00005, 00005, 00033, 10〉, 〈00011, 00000, 00010, 1〉, 〈00011, 00000, 00011, 2〉, 〈00011, 00000, 00033, 3〉, 〈00011, 00000, 00021, 4〉, 〈00011, 00000, 00031, 5〉, 〈00011, 00000, 00032, 6〉, 〈00011, 00000, 00022, 7〉, 〈00011, 00000, 00033, 8〉 } 2.2 HSII2 P = { 〈0, 00001, 00001, 00001, 1〉, 〈0, 00001, 00001, 00002, 2〉, 〈0, 00001, 00001, 00003, 3〉, 〈0, 00001, 00001, 00004, 4〉, 〈0, 00001, 00001, 00005, 5〉, 〈0, 00001, 00001, 00007, 7〉, 〈0, 00001, 00001, 00008, 8〉, 〈0, 00001, 00001, 00033, 9〉, 〈1, 00002, 00002, 00001, 1〉, 〈1, 00002, 00002, 00009, 2〉, 〈1, 00002, 00002, 00033, 3〉, 〈2, 00002, 00008, 00010, 1〉, 127 HSII HSII2 〈2, 00002, 00008, 00011, 2〉, 〈2, 00002, 00008, 00033, 3〉, 〈2, 00002, 00008, 00012, 4〉, 〈2, 00002, 00008, 00013, 5〉, 〈2, 00002, 00008, 00033, 6〉, 〈2, 00002, 00008, 00014, 7〉, 〈2, 00002, 00008, 00015, 8〉, 〈2, 00002, 00008, 00016, 9〉, 〈2, 00002, 00008, 00033, 10〉, 〈2, 00002, 00008, 00017, 11〉, 〈2, 00002, 00008, 00018, 12〉, 〈2, 00002, 00008, 00033, 13〉, 〈2, 00002, 00009, 00019, 1〉, 〈2, 00002, 00009, 00033, 2〉, 〈2, 00002, 00009, 00020, 3〉, 〈2, 00002, 00009, 00033, 4〉, 〈1, 00003, 00003, 00001, 1〉, 〈1, 00003, 00003, 00009, 2〉, 〈1, 00003, 00003, 00033, 3〉, 〈2, 00003, 00009, 00019, 1〉, 〈2, 00003, 00009, 00033, 2〉, 〈2, 00003, 00009, 00020, 3〉, 〈2, 00003, 00009, 00033, 4〉, 〈2, 00003, 00010, 00010, 1〉, 〈2, 00003, 00010, 00011, 2〉, 〈2, 00003, 00010, 00033, 3〉, 〈2, 00003, 00010, 00012, 4〉, 〈2, 00003, 00010, 00013, 5〉, 〈2, 00003, 00010, 00033, 6〉, 〈2, 00003, 00010, 00014, 7〉, 〈2, 00003, 00010, 00015, 8〉, 〈2, 00003, 00010, 00016, 9〉, 〈2, 00003, 00010, 00033, 10〉, 〈2, 00003, 00010, 00017, 11〉, 〈2, 00003, 00010, 00018, 12〉, 〈2, 00003, 00010, 00033, 13〉, 128 HSII HSII2 〈1, 00004, 00000, 00010, 1〉, 〈1, 00004, 00000, 00011, 2〉, 〈1, 00004, 00000, 00033, 3〉, 〈1, 00004, 00000, 00021, 4〉, 〈1, 00004, 00000, 00022, 5〉, 〈1, 00004, 00000, 00015, 6〉, 〈1, 00004, 00000, 00016, 7〉, 〈1, 00004, 00000, 00033, 8〉, 〈1, 00005, 00005, 00001, 1〉, 〈1, 00005, 00005, 00023, 2〉, 〈1, 00005, 00005, 00024, 3〉, 〈1, 00005, 00005, 00025, 4〉, 〈1, 00005, 00005, 00026, 5〉, 〈1, 00005, 00005, 00027, 6〉, 〈1, 00005, 00005, 00028, 7〉, 〈1, 00005, 00005, 00029, 8〉, 〈1, 00005, 00005, 00030, 9〉, 〈1, 00005, 00005, 00033, 10〉, 〈3, 00011, 00000, 00010, 1〉, 〈3, 00011, 00000, 00011, 2〉, 〈3, 00011, 00000, 00033, 3〉, 〈3, 00011, 00000, 00021, 4〉, 〈3, 00011, 00000, 00031, 5〉, 〈3, 00011, 00000, 00032, 6〉, 〈3, 00011, 00000, 00022, 7〉, 〈3, 00011, 00000, 00033, 8〉 } 129 Prilog C Klasifikacija vremena u tehnologiji Nacˇelno objasˇnjenje postupka dobijanja normalnog vremena, zahteva rasˇcˇlanjavanje opracije na zahvate i njihovu klasifikaciju. Karakter zahvata nije uvek isti, nisu sve radnje usmerene na promenu oblika radnog predmeta ili izmene strukture i slicˇno, ali su one isto tako sastavni deo zadate operacije ili preduslov za njeno odvijanje. Ovo je posebno izrazˇeno u postupcima odrzˇavanja jer niz zahvata ima posebnu klasifikaciju. Normalno vreme za jednu operaciju Pripremno zavrsˇno vreme Tpz Vreme po komadu Tk Vreme izrade Tiz Tehnolosˇko vreme Tt Tehnolosˇko vreme masˇinsko Ttm Tehnolosˇko vreme rucˇno Ttr Pomoc´no vreme Tp Pomoc´no vreme masˇinsko Tpm Pomoc´no vreme rucˇno Tpr Dopunsko vreme Td Slika C.1: Komponentna vremena Na slici (C.1), dat je graficˇki prikaz strukture komponentnih vremena potrebnih za izvrsˇenje jedne operacije. Kolicˇina normalnog vremena izrade izracˇunava se po sledec´em obrascu: T = Tpz N + Tiz + Td (C.1) gde je: Tpz ukupno potrebno pripremno zavrsˇno vreme za izradu izvesnog broja komada, a obuhvata: 130 Klasifikacija vremena u tehnologiji − prijem naloga za rad sa dokumentacijom i proucˇavanje zadataka − pripremu alata − pripremu ostalih elemenata potrebnih za rad − predaju gotovih komada kontroli − raspremanje radnog mesta posle zavrsˇenog rada N broj istih komada koji se izraduju jedan za drugim bez prekida - broj komada u seriji Tiz vreme predvideno za radnje u vezi sa promenom oblika radnog predmeta i racˇuna se po formuli (C.2) Td dopunsko vreme predvideno za: − odmor radnika − fiziolosˇke potrebe − opsluzˇivanje masˇine, koje je predvideno da obavlja sam radnik Vreme Tiz je kolicˇina vremena vezana za promenu radnog predmeta i racˇuna se: Tiz = Tt + Tp (C.2) gde je: Tt tehnolosˇko vreme izrade predvideno za promenu oblika radnog predmeta, izmenu strukture materijala, postizanje novih osobina spajanjem viˇse delova u celinu, montazˇa i racˇuna se po formuli (C.3) Tp pomoc´no vreme predvideno za: − uzimanje komada koje treba obradivati − osposobljavanje alata za pocˇetak obrade − ukljucˇivanje radnog dela masˇine − kontrolu u toku rada − skidanje i odlaganje komada po zavrsˇenoj obradi i racˇuna se po formuli (C.4) Vreme montazˇe se racˇuna po formuli: Tt = Ttm + Ttr + Ttk (C.3) gde je: Ttm tehnolosˇko vreme izrade predvideno za masˇinski rad u vremenskim jedinicama Ttr tehnolosˇko vreme izrade predvideno za rucˇni rad u vremenskim jedinicama 131 Klasifikacija vremena u tehnologiji Ttk tehnolosˇko vreme izrade kombinovano, masˇinski rad i rucˇni rad u vremenskim jedinicama Pomoc´no vreme se racˇuna po formuli: Tp = Tpm + Tpr + Tpk (C.4) gde je: Tpm pomoc´no vreme izrade predvideno za masˇinski rad u vremenskim jedinicama Tpr pomoc´no vreme izrade predvideno za rucˇni rad u vremenskim jedinicama Tpk pomoc´no vreme izrade kombinovano, masˇinski rad i rucˇni rad u vremenskim jedinicama Proracˇunom se dobijaju vremena Ttm i Tpm, dok se ostala vremena dobijaju snimanjem proizvodnje ili na osnovu standardizovanih podataka dobijenih viˇsestrukim ispitivanjima u laboratorijama. Obrazac za normalno vreme izrade u razvijenom obliku je: T = Tpz N + Ttm + Ttr + Ttk + Tpm + Tpr + Tpk + Td (C.5) i sve mozˇe biti izrazˇeno u razlicˇitim vremenskim jedinicama. 132 Biografija Goran Lazovic´, diplomirani matematicˇar roden je 28.01.1964. godine u Priˇstini. Zavrsˇio je osnovnu 1978 i srednju sˇkolu 1982. godine u Smederevu. Iste godine upisao je Matematicˇki fakultet u Beogradu, odsek za Racˇunarstvo i informatiku. Diplomirao je 01.07.1988. go- dine sa srednjom ocenom 9.42. Poslediplomske studije je upisao sˇkolske 1989/90. godine na istom smeru Matematicˇkog fakulteta u Beogradu. Magistarsku tezu pod nazivom “Prilog fazi-modalnim logicˇkim strukturama i njihovim softverskim implementacijama” odbranio je 05.10.1995. godine na Matematicˇkom fakultetu u Beogradu. Na Masˇinskom fakultetu u Beo- gradu radi od 01.09.1990. godine u zvanju asistenta pripravnika. U zvanje asistenta izabran je 1996. godine i reizabran 2000, 2004, 2008. i 2011. godine. Od dolaska na Masˇinski fa- kultet do danas, Goran Lazovic´, diplomirani matematicˇar, uspesˇno je drzˇao vezˇbe iz sledec´ih predmeta: Matematika 1, Matematika 2, Matematika 3, Programiranje, Nacrtna geome- trija, Racˇunarski alati, Numericˇke metode, Bioautomatika, C/C++, Objektno orijentisana paradigma, Projektovanje baza podataka, Projektovanje inzˇenjerskog softvera na Masˇinskom fakultetu u Beogradu, odnosno Matematika 1, Matematika 2, Matematika 3 i Matematika 4 na Vojno tehnicˇkoj akademiji. Govori engleski jezik i sluzˇi se ruskim jezikom. Otac je petoro dece Lazara (1996), Nikole (1997), Ksenije (2000), Anastasije (2002) i Sofije (2006). 133