Δενδρικές δομές διαχείρισης πληροφορίας και βιομηχανικές εφαρμογές

Abstract

The 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.

Η διατριβή διερευνά προβλήματα αποδοτικής οργάνωσης χωροταξικών δεδομένων προτείνει συγκεκριμένες δενδρικές δομές για τη διαχείριση τους και τέλος δίνει παραδείγματα χρήσης τους σε ειδικές περιοχές εφαρμογών. Το πρώτο κεφάλαιο ασχολείται με το γεωμετρικό πρόβλημα της εύρεσης των ισο προσανατολισμένων ορθογώνιων που περικλείουν ένα query αντικείμενο που μπορεί να είναι ένα ισο προσανατολισμένο ορθογώνιο είτε σημείο η κάθετο/οριζόντιο ευθύγραμμο τμήμα. Για την επίλυση του προτείνεται μια πολυεπίπεδη δενδρική δομή που βελτιώνει τις πολυπλοκότητες των προηγουμένων καλυτέρων λύσεων. Το δεύτερο κεφάλαιο εξετάζει το πρόβλημα της ανάκτησης σημείων σε πολύγωνα. Η προτεινομένη γεωμετρική δομή είναι επίσης πολυεπίπεδη και αποδοτική όταν το query πολύγωνο έχει συγκεκριμένες ιδιότητες. Το τρίτο κεφάλαιο ασχολείται με την εφαρμογή δενδρικών δομών σε δυο βιομηχανικά προβλήματα. Το πρώτο άφορα στη μείωση της πολυπλοκότητας ανίχνευσης συγκρούσεων κατά την κίνηση ενός ρομποτικού βραχίονα σε μια επίπεδη σκηνή με εμπόδια. Ο αλγόριθμος επίλυσης κάνει χρήση μιας ουράς προτεραιότητας και μιας UNION FIND δομής ενώ αξιοποιεί γνωστές δομές και αλγορίθμους της Υπολογιστικής Γεωμετρίας όπως υπολογισμός κυρτών καλυμμάτων έλεγχος polygon inclusion κλπ. Το δεύτερο πρόβλημα ασχολείται με το σχεδιασμό απαιτήσεων υλικών (MRP) σε ένα βιομηχανικό σύστημα παραγωγής. Για το σκοπό αυτό αναπτύχθηκε ένας MRP επεξεργαστής που χρησιμοποιεί διασυνδεμένες λίστες και εκτελείται στην κυρία μνήμη για να είναι αποδοτικός. Το τελευταίο κεφάλαιο εξετάζει το πρόβλημα του ελέγχου της παράγωγης και συγκεκριμένα της δρομολόγησης εργασιών. Στο πλαίσιο αυτό σχεδιάστηκε και υλοποιήθηκε ένα ευφυές σύστημα δρομολόγησης σε περιβάλλον ροής που συνδυάζει γνωσιακή τεχνολογία και προσομοίωση με on line έλεγχο προκειμένου να υποστηρίζει το διευθυντή παράγωγης στη λήψη αποφάσεων.