Tanker Scheduling Problem

Vilniaus Gedimino technikos universitetas Fundamentinių mokslų fakultetas Grafinių informacinių sistemų katedra Tanker- Scheduling Problem Kursinis darbas Atliko: Ingrida Mažonavičiūtė, IG-2 Tikrino doc. R. Baušys Vilnius 2006 1. Duota problema - Tanker Scheduling Problem “Jūrų garlaivių kompanija, pasirašė sutartį pervežinėti greitai gendančias prekes tarp keleto skirtingų išgabenimo-atgabenimo uostų porų. Kadangi kroviniai yra gendantys, užsakovai turi apibrėžtas datas(pvz. Krovinių pristatymo datas), kada siuntiniai privalo būti pristatymo uostuose(Kroviniai negali atplaukti nei per anksti, nei per vėlai). Jūrų garlaivių kompanija nori rasti, kiek minimaliai laivų reikia, kad laiku įvykdyti užsakovų reikalavimus. Šios problemos modelis būtų toks. Tarkime turime 4 krovinius; kiekvienas krovinys turi charakteristikas pavaizduotas pav.1(a). Pvz. Kaip matome iš 1 lentelės eilutės, kompanija turi paimti 1 krovinį iš uosto A ir pristatyti į uostą C trečią mėnesio dieną. Pav.1(b) ir 1(c) Rodo pilnų laivų su siuntiniais laikus tarp uostų(įskaitant ir laikus krovinių pakrovimui ir iškrovimui) ir tuščių laivų sugrįžimo laivus(be siuntinių). 1pav. Duomenys Tanker Sceduling Problemai: a) krovinių charakteristikos, b)pilnų laivų keliavimo tarp uostų laikai, c) tuščių laivų grįžimo laikai. Ši problema sprendžiama sukonstruojant tinklą pavaizduotą 2pav. Šis tinklas kiekvienam kroviniui turi po mazgą ir sujungimą iš mazgo i į mazgą j jei įmanoma pervežti siuntinį j po to kai pilnai užbaigtas krovinio i pervežimas, t.y. krovinio j paėmimo data neturi būti ankstesnė už krovinio i pristatymo datą pridėjus tuščio garlaivio keliavimą iš uosto i į j . Kryptinis kelias šiame tinkle nurodo tinkamą krovinių paėmimo ir pristatymo seką. Tanker Scheduling problema reikalauja apibrėžti minimalų kiekį kryptinių kelių pervežinėjant krovoinius.” [3]. 2pav. Tinklo formulavimas tanker scheduling problemai – po 2 sugrupuotų tinkamų sekų tinklas. Nors [3] pasiūlyta problemą, kuri žinoma kaip minimalios vertės problema, spręsti išplėtus nagrinėjama grafą ir tada naudojant bet kokį maksimalaus srauto algoritmą, tačiau pastebėjusi, kad šiame uždavinyje akivaizdžiai matomas greedy kriterijus, o taip pat žinant kad būtent tokio tipo uždaviniui spręsti optimaliausia naudoti greedy metodą, uždavinį išsprendžiau būtent šiuo metodu. Panaudotame metode matomas maksimalus srautas. 2. Greedy algoritmai Optimizacijos problemoms spręsti naudojami algoritmai, paprastai turi tam tikrą aibę žingsnių, su daug pasirinkimų kiekviename jų. Daugeliui optimizacijos problemų, geriausiam pasirinkimui rasti naudoti dinaminį programavimą yra bereikalingas galingo algoritmo pasirinimas, paprastai tai galima padaryti su daug efektyvesniais algoritmais. Greedy algoritmas visada padaro sprendimą, kuris atrodo geriausias tam momentui. T.y. jis padaro lokaliai optimalų sprendimą, su ta viltim, kad šis pasirinkimas prives prie globaliai optimalaus sprendimo. Greedy metodu bandoma sukonstruoti optimalų sprendimą pakopomis. Kiekvienoje pakopoje pagal keletą kriterijų priimame tą sprendimą, kuris atrodo geriausias tuo momentu. Sprendimas priimtas vienoje pakopoje nekeičiamas vėlesnėse pakopose, taigi kiekvienas sprendimas turi garantuoti tinkamumą. Kriterijus naudojamas priimti greedy metodu sprendimus kiekvienoje pakopoje vadinamas greedy kriterijumi. Greedy algoritmai ne visada duota optimalius sprendimus, bet su daugeliu problemu jis kuo puikiausiai veikia. Greedy metodas yra pakankamai galingas ir gerai dirba su daugelio sričių problemomis. Minimalios trukmės medžio (minimum-spanning-tree) algoritmai, Dijkstra‘s algoritmas rasti trumpiausiems keliams, išeinantiems iš vieno šaltinio, ir Chvatal‘s algoritmas, kuriam greedy paslepia heuristiką, gali būti puikūs greedy metodo pritaikymo pavyzdžiai.. Paprastai, bet ne trivialiai darbų pasirinkimo problemai, greedy algoritmas efektyviai randa norima rezultatą. 3. Tanker scheduling problem = greedy algoritmas activity-selection(darbų pasirinkimo) problemai. Activity-selection problema, yra resursų paskirstymo problema tarp keleto kompetetingų veiklų. Greedy algoritmas duoda elegantišką ir paprastą metodą parinkti maksimalaus dydžio aibę iš tarpusavyje suderintų veiklų . Greedy algoritmas Activity-selection problemai sprendžiamas tokiu pseudokodu 3pav. Naudojamos veiklos turi būti išdėstytos didėjimo tvarka. 3pav. Activity-selection pseudokodas Greedy Activity parinkimo algoritmas visada randa optimalų sprendimą Activity-selection problemai spręsti Mano nagrinėjamoje tanker scheduling problemoje- maksimalią vienu laivu perplukdomų siuntų, iš siuntinių sąrašo, aibę. Tai galima suprasti, kaip maksimalų srautą, todėl tanker scheduling problema priskirta prie uždavinių, kurie sprendžiami maksimalių srautų algoritmais grupės. Kaip matysime toliau, greedy metodas šiai aplikacijai yra pats tinkamiausias. 3.1 Požiūris į problemą Turime n siuntinių ir m nepriklausomų garlaivių, su kuriais tie siuntiniai bus gabenami. Kadangi vežami gendantys produktai, kiekvienas siuntinys turi fiksuotą pradžios(pakrovimo) laiką si ir pabaigos laiką fi, (į pabaigos laiką įeina siuntinio iškrovimas laikas + kelionė tuščiu laivu į kitą uostą paimti kito krovinio) si

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!