Τα τελευταία χρόνια η ραγδαία αύξηση της υπολογιστικής ισχύος, των αποθηκευτικών μέσων καθώς και των τηλεπικοινωνιών έχει δημιουργήσει γόνιμο έδαφος για την ανάπτυξη πολύπλοκων, απαιτητικών εφαρμογών, τόσο στον χώρο της επιστημονικής έρευνας, όσο και στα πλαίσια της παραγωγής εμπορικών λύσεων. Ως αποτέλεσμα αυτού, πραγματοποιείται μετάβαση από το μοντέλο των μεμονωμένων διακριτών πόρων στο μοντέλο της συνεργασίας κατανεμημένων πόρων το οποίο υλοποιείται από την τεχνολογία πλέγματος (Grid Computing). Ένα πολύ σημαντικό θέμα που επηρεάζει την συνολική απόδοση των δικτύων πλέγματος είναι η χρονοδρομολόγηση των εργασιών που υποβάλλουν οι χρήστες στους διαθέσιμους πόρους του δικτύου. Στόχος της παρούσας διπλωματικής εργασίας ήταν η μελέτη της χρονοδρομολόγησης στα δίκτυα πλέγματος όχι μέσω προγραμμάτων προσομοίωσης αλλά χρησιμοποιώντας το ενδιάμεσο λογισμικό gLite. Βασικό αντικείμενο μελέτης ήταν η υπηρεσία Workload Management System (WMS) στην οποία υλοποιούνται οι αλγόριθμοι χρονοπρογραμματισμού που παρέχει το gLite. Στόχος ήταν η ανάλυση της λειτουργίας των δύο αλγορίθμων χρονοπρογραμματισμού που παρέχει το ενδιάμεσο λογισμικό και η κατανόηση τόσο της αρχιτεκτονικής της WMS υπηρεσίας, που είναι μια από τις πιο σημαντικές για την λειτουργία ολόκληρου του δικτύου, αλλά και του τρόπου υλοποίησης των δύο αλγορίθμων του gLite. Στην συνέχεια προσθέσαμε στην υπηρεσία WMS ένα νέο δίκαιο αλγόριθμο ανάθεσης εργασιών στους διαθέσιμους πόρους του δικτύου πλέγματος. Τέλος αναπτύξαμε ένα μικρής κλίμακας δίκτυο πλέγματος για την πειραματική αξιολόγηση του νέου αλγορίθμου και την σύγκριση του με τους δύο βασικούς αλγορίθμους του gLite. Τα αποτελέσματα δείχνουν ότι ο αλγόριθμος μας παρέχει καλύτερη αξιοποίηση των πόρων του δικτύου, μειώνοντας παράλληλα το μέσο χρόνο εκτέλεσης μιας εργασίας στο δίκτυο. / The emergence of high speed optical networks is making the vision of Grids a reality. Grids consist of geographically distributed and heterogeneous computational and storage resources that may belong to different administrative domains, but can be shared among users by establishing global resource management architecture. An important issue in the performance of Grids is the scheduling of application tasks to the available resources. The Grid environment is quite dynamic, with resource availability and load varying rapidly with time, and application tasks have very different characteristics and requirements. Scheduling is a key to the success of Grid Networks, since it determines the efficiency in the use of the resources and the QoS provided to the users. In this work we present our experiences from implementing and integrating a new job scheduling algorithm in the gLite Grid middleware and present experimental results that compare it to the existing gLite scheduling algorithms. It is the first time that gLite scheduling algorithms are put under test and compared with a new algorithm under the same conditions. We describe the problems that were encountered and solved, going from theory and simulations to practice and the actual implementation of our fair scheduling algorithm. In this work we also describe the steps one needs to follow in order to develop and test a new scheduling algorithm in gLite. We present the methodology followed and the testbed set up for the comparisons. Our research sheds light on some of the problems of the existing gLite scheduling algorithms and makes clear the need for the development of new.

Οι ροές εργασιών (workflows) αποτελούν έναν από τους πιο σημαντικούς παράγοντες για την σωστή, εύρυθμη και αποδοτική λειτουργία των διαδικασιών που έχουν να φέρουν εις πέρας οι επιχειρήσεις. Καθώς οι επιχειρήσεις έχουν την τάση να γιγαντώνονται με στόχο την αύξηση των κερδών τους, και με δεδομένο ότι οικονομίες είναι ανοιχτές και δε γνωρίζουν φυσικά σύνορα, τελικά, οδηγούμαστε στην ανάγκη για συνεργασίες μεταξύ των επιχειρήσεων που θα τους επιτρέπουν αφενός να επιτύχουν το βέλτιστο ποιοτικά αποτέλεσμα και αφετέρου με το μικρότερο δυνατό κόστος. Το μεγάλο μέγεθος των επιχειρήσεων σε συνδυασμό με την ανάγκη για συνεργασίες μεταξύ τους έχουν ως αποτέλεσμα να αυξάνει η πολυπλοκότητα των διαδικασιών και των προβλημάτων που έχουν να επιλύσουν. Αυτό οδηγεί στην ανάγκη να υπάρξει ένας τρόπος διαχείρισης των ροών εργασιών που απαρτίζουν τις διαδικασίες αυτές. Έτσι, ανατπύχθηκαν μηχανές ροών εργασιών (workflow engine) που επιτρέπουν την διαχείριση των ροών με αποδοτικό και βέλτιστο τρόπο. Στην παρούσα διπλωματική ασχολούμαστε με τη χρήση workflow συστημάτων για την επίλυση του προβλήματος της αποδοτικής διαχείρισης της εφοδιαστικής αλυσίδας (supply chain) στις τουριστικές επιχειρήσεις. Για την αποδοτική λειτουργία των εφοδιαστικών αλυσίδων απαιτείται η ύπαρξη ενός συστήματος διαχείρισής τους, με σκοπό να οργανώνει και να συγχρονίζει τις διαφορετικές οντότητες που παίρνουν μέρος σε όλα τα βήματα μιας εφοδιαστικής αλυσίδας. Έτσι, έχουν αναπτυχθεί τέτοια συστήματα διαχείρισης, όπου με την βοήθεια των υπολογιστών μοντελοποιούν και καταγράφουν όλα τα βήματα της εφοδιαστικής αλυσίδας, κάνοντας έτσι αποδοτική την λειτουργία της. Αφού παρουσιαστούν τα πιο δημοφιλή open source workflow engines, στη συνέχεια υλοποιούμε την δική μας workflow engine που επιλύει το πρόβλημα της διαχείρισης των εφοδιαστικών αλυσίδων σε τουριστικές επιχειρήσεις. Πιο συγκεκριμένα, αναπτύχθηκε ένα basic custom workflow engine προσαρμοσμένο στις ανάγκες των τουριστικών επιχειρήσεων όσον αφορά τη διαδικασία διαχείρισης της εφοδιαστικής τους αλυσίδας στο κομμάτι από την δημιουργία μιας νέας παραγγελίας από προϊόντα και πρώτες ύλες μέχρι το τελικό βήμα της αποδοχής της παραγγελίας από τους υπεύθυνους των τουριστικών επιχειρήσεων. Η εφαρμογή που υλοποιήθηκε είναι web based application. Οι web εφαρμογές παρουσιάζουν αρκετά πλεονεκτήματα έναντι των παραδοσιακών desktop εφαρμογών, τα οποία και παρουσιάζονται στη διπλωματική αυτή. / --

Το Υπολογιστικό Νέφος (Cloud Computing) χαρακτηρίζεται ως το νέο μοντέλο ανάπτυξης λογισμικού και παροχής υπηρεσιών στον τομέα των Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τα κύρια χαρακτηριστικά του είναι η κατά απαίτηση διάθεση υπολογιστικών πόρων, η απομακρυσμένη πρόσβαση σε αυτούς μέσω διαδικτύου και η ευελιξία των παρεχόμενων υπηρεσιών. Η ευελιξία επιτρέπει την αναβάθμιση ή υποβάθμιση των υπολογιστικών πόρων σύμφωνα με τις απαιτήσεις του τελικού χρήστη. Επιπλέον, η συνεχής αύξηση του μεγέθους της παραγόμενης από διάφορες πηγές πληροφορίας (διαδίκτυο, επιστημονικά πειράματα) έχει δημιουργήσει μία τεράστια ποσότητα πολύπλοκων και διάχυτων ψηφιακών δεδομένων . Η απόσπαση χρήσιμης γνώσης από μεγάλου όγκου ψηφιακά δεδομένα απαιτεί έξυπνες και ευκόλως επεκτάσιμες υπηρεσίες ανάλυσης, εργαλεία προγραμματισμού και εφαρμογές. Επομένως, η δυνατότητα της ελαστικότητας και της επεκτασιμότητας έχει κάνει το Υ-πολογιστικό Νέφος να είναι μια αναδυόμενη τεχνολογία αναφορικά με τις αναλύσεις μεγάλου όγκου δεδομένων οι οποίες απαιτούν παραλληλισμό, πολύπλοκες ροές ανάλυσης και υψηλό υπολογιστικό φόρτο εργασίας. Για την καλύτερη δυνατή διαχείριση πολύπλοκων αναλύσεων και ενορχήστρωση των απαιτούμενων διαδικασιών, είναι απαραίτητη η ένθεση ροών εργασιών. Μια ροή εργασίας είναι ένα οργανωμένο σύνολο ενεργειών που πρέπει να πραγματοποιηθούν για να επιτευχθεί μια εμπορική ή ερευνητική διεργασία, καθώς και οι μεταξύ τους εξαρτήσεις αφού κάθε ενέργεια αποτελείται από ορισμένα βήματα που πρέπει να εκτελεστούν σε συγκεκριμένη σειρά. Στην παρούσα μεταπτυχιακή διπλωματική εργασία δημιουργήθηκε ένα σύστημα για τη δυναμική διαχείριση των προσφερόμενων πόρων σε μια υποδομή Υπολογιστικού Νέφους και την εκτέλεση κατανεμημένων υλοποιήσεων υπολογιστικής ανάλυσης δεδομένων. Συγκεκριμένα, η εφαρμογή, αφού λάβει από το χρήστη τα δεδομένα εισόδου για την έναρξη μιας νέας διαδικασίας ανάλυσης, εξετάζει τα δεδομένα των επιστημονικών προβλημάτων καθώς και την πολυπλοκότητά τους και παρέχει δυναμικά και αυτόματα τους αντίστοιχους υπολογιστικούς πόρους για την εκτέλεση της αντίστοιχης λειτουργίας ανάλυσής τους. Επίσης, επιτρέπει την καταγραφή της ανάλυσης και αναθέτει τον συντονισμό της διαδικασίας σε αντίστοιχες ροές εργασιών ώστε να διευκολυνθεί η ενορχήστρωση των παρεχόμενων πόρων και η παρακολούθηση της εκτέλεσης της υπολογιστικής διαδικασίας. Η συγκεκριμένη μεταπτυχιακή εργασία, με τη χρήση τόσο των παρεχόμενων υπηρεσιών μιας υποδομής Υπολογιστικού Νέφους όσο και των δυνατοτήτων που παρέχουν οι ροές εργασιών στην διαχείριση των εργασιών, έχει σαν αποτέλεσμα να απλουστεύει την πρόσβαση, τον έλεγχο, την οργάνωση και την εκτέλεση πολύπλοκων και παράλληλων υλοποιήσεων ανάλυσης δεδομένων από την στιγμή εισαγωγής των δεδομένων από το χρήστη έως τον υπολογισμό του τελικού αποτελέσματος. Πιο αναλυτικά η διπλωματική εργασία επικεντρώθηκε στη πρόταση μιας ολοκληρωμένης λύσης για: 1. τη παροχή μιας εφαρμογής στην οποία ο χρήστης θα έχει τη δυνατότητα να εισάγεται και να ξεκινά μια σύνθετη ανάλυση δεδομένων, 2. τη δημιουργία της κατάλληλης υποδομής για τη δυναμική διάθεση πόρων από μια cloud υποδομή ανάλογα με τις ανάγκες του εκάστοτε προβλήματος και 3. την αυτοματοποιημένη εκτέλεση και συντονισμό της διαδικασίας της ανάλυσης με χρήση ροών εργασιών. Για την επικύρωση και αξιολόγηση της εφαρμογής, αναπτύχθηκε η πλατφόρμα IRaaS η οποία παρέχει στους χρήστες του τη δυνατότητα επίλυσης προβλημάτων πολλαπλών πεδίων / πολλαπλών φυσικών. Η πλατφόρμα IRaaS βασίστηκε πάνω στην προαναφερόμενη εφαρμογή για τη δυναμική ανάθεση υπολογιστικών πόρων και συντονισμός εκτέλεσης πολύπλοκων διαδικασιών ανάλυσης δεδομένων. Εκτελώντας μια σειρά αναλύσεων παρατηρήθηκε ότι η συγκεκριμένη εφαρμογή παρέχει καλύτερους χρόνους εκτέλεσης, μικρότερη δέσμευση υπολογιστικών πόρων και κατά συνέπεια μικρότερο κόστος για τις αναλύσεις. Η εγκατάσταση της πλατφόρμας IRaaS για την εκτέλεση των πειραμάτων έγινε στην υποδομή Υπολογιστικού Νέφους του εργαστηρίου Αναγνώρισης Προτύπων. Η υποδομή βασίστηκε στα λογισμικά XenServer και Cloudstack, τα οποία εγκαταστάθηκαν και παραμετροποιήθηκαν στα πλαίσια της παρούσας εργασίας. / Cloud Computing is the new software development and service providing model in the area of Information and Communication Technologies. The main aspects of Cloud Computing are the on-demand allocation of computational resources, the remote access to the latter via the Internet and the elasticity of the provided services. Elasticity provides the capability to scale the computational resources depending on the computational needs. The continuous proliferation of data warehouses, webpages, audio and video streams, tweets, and blogs is generating a massive amount of complex and pervasive digital data. Extracting useful knowledge from huge digital datasets requires smart and scalable analytics services, programming tools, and applications. Due to the aspects of elasticity and scalability, Cloud Computing has become an emerging technology regarding to big data analysis, which demands parallelization, complex workflow analysis and massive computational workload. In this respect, workflows have an important role in managing complex flows and orchestrating the required processes. A workflow is an orchestrated set of activities that are necessary in order to complete a commercial or scientific task, as well as any dependencies between these tasks, since each one of them can be further decomposed into finer tasks that need to be executed in a predefined order. In this thesis, a system is presented that dynamically allocates the available resources provided by a cloud infrastructure and orchestrates the execution of complex and distrib-uted data analysis on these allocated resources. In particular, the system calculates the required computational resources (memory and CPU) based on the size of the input data and on the available resources of the cloud infrastructure, concluding to allocate dynamically the most suitable resources. . Moreover, the application offers the ability to coordinate the distributed analysis process utilising workflows for the orchestration and monitoring of the different tasks of the computational flow execution. Taking advantage of the services provided by a cloud infrastructure as well as the functionality of workflows in task management, this thesis has resulted in simplifying access, control, coordination and execution of complex and parallel data analysis implementations from the moment that a user enters a set of input data to the computation of the final result. In this context, this thesis focuses on a comprehensive and integrated solution that: 1. provides an application, through which the user is able to log in and start a complex data analysis, 2. offers the necessary infrastructure for dynamically allocating the cloud resources of, based on the needs of the particular problem, and 3. executes and coordinates the analysis process automatically by leveraging workflows. In order to validate and evaluate the application, the IRaaS platform was developed, offering the ability of solving multi-domain/multi-physics problems. The IRaaS platform is based on the aforementioned system in order to enable the dynamic allocation of computational resources and to coordinate the execution of complex data analysis processes. By executing a series of experiments with different input data, we observed that the presented application resulted in improved execution times, better allocation of computational resources and, thus, lower cost. In order to perform experiments, the IRaaS platform was set up on the cloud infrastructure of Pattern Recognition laboratory. In the context of this thesis, a new infrastructure has been installed and parameterized based on XenServer as virtualization hypervisor and CloudStack platform for the creation of a private cloud infrastructure.

H διατριβή διερευνά προβλήματα αποδοτικής οργάνωσης χωροταξικών δεδομένων, προτείνει συγκεκριμένες δενδρικές δομές για τη διαχείρισή τους και, τέλος, δίνει παραδείγματα χρήσης τους σε ειδικές περιοχές εφαρμογών. Το πρώτο κεφάλαιο ασχολείται με το γεωμετρικό πρόβλημα της εύρεσης των ισo-προσανατολισμένων ορθογωνίων που περικλείουν ένα query αντικείμενο που μπορεί να είναι ένα ισο-προσανατολισμένο ορθογώνιο είτε σημείο ή κάθετο / οριζόντιο ευθύγραμμο τμήμα. Για την επίλυσή του προτείνεται μια πολυεπίπεδη δενδρική δομή που βελτιώνει τις πολυπλοκότητες των προηγούμενων καλύτερων λύσεων. Το δεύτερο κεφάλαιο εξετάζει το πρόβλημα της ανάκτησης σημείων σε πολύγωνα. H προτεινόμενη γεωμετρική δομή είναι επίσης πολυεπίπεδη και αποδοτική όταν το query πολύγωνο έχει συγκεκριμένες ιδιότητες. Το τρίτο κεφάλαιο ασχολείται με την εφαρμογή δενδρικών δομών σε δύο βιομηχανικά προβλήματα. Το πρώτο αφορά στη μείωση της πολυπλοκότητας ανίχνευσης συγκρούσεων κατά την κίνηση ενός ρομποτικού βραχίονα σε μια επίπεδη σκηνή με εμπόδια. Ο αλγόριθμος επίλυσης κάνει χρήση μιας ουράς προτεραιότητας και μιας UNION-FIND δομής ενώ αξιοποιεί γνωστές δομές και αλγόριθμους της Υπολογιστικής Γεωμετρίας όπως υπολογισμός κυρτών καλυμμάτων, έλεγχος polygon inclusion, κλπ. Το δεύτερο πρόβλημα ασχολείται με το σχεδιασμό απαιτήσεων υλικών (MRP) σε ένα βιομηχανικό σύστημα παραγωγής. Για το σκοπό αυτό αναπτύχθηκε ένας MRP επεξεργαστής που χρησιμοποιεί διασυνδεμένες λίστες και εκτελείται στην κύρια μνήμη για να είναι αποδοτικός. Το τελευταίο κεφάλαιο εξετάζει το πρόβλημα του ελέγχου της παραγωγής και συγκεκριμένα της δρομολόγησης εργασιών. Στο πλαίσιο αυτό σχεδιάστηκε και υλοποιήθηκε ένα ευφυές σύστημα δρομολόγησης σε περιβάλλον ροής που συνδυάζει γνωσιακή τεχνολογία και προσομοίωση με on-line έλεγχο προκειμένου να υποστηρίξει το διευθυντή παραγωγής στη λήψη αποφάσεων. / Τhe dissertation examines problems of efficient organization of spatial data, proposes specific tree structures for their management, and finally, gives examples of their use in specific application areas. The first chapter is about the problem of finding the iso-oriented rectangles that enclose a query object which can be an iso-oriented rectangle either a point or a vertical / horizontal line segment. A multilevel tree structure is proposed to solve the problem which improves the complexities of the best previous known solutions. The second chapter examines the problem of point retrieval on polygons. The proposed geometric structure is also multileveled and efficient when the query polygon has specific properties. The third chapter is about the application of tree structures in two manufacturing problems. The first one concerns the reduction in the complexity of collision detection as a robotic arm moves on a planar scene with obstacles. For the solution a priority queue and a UNION-FIND structure are used, whereas known data structures and algorithms of Computational Geometry such as construction of convex hulls, polygon inclusion testing, etc. are applied. The second problem is about material requirements planning (MRP) in a manufacturing production system. To this end an MRP processor was developed, which uses linked lists and runs in main memory to retain efficiency. The last chapter examines the production control problem, and more specifically the job scheduling problem. In this context, an intelligent scheduling system was designed and developed for flow shop production control which combines knowledge-based technology and simulation with on-line control in order to support the production manager in decision making.