Πτυχιακή Κυνηγόπουλου

ΠΕΡΙΛΗΨΗ

Η παρούσα πτυχιακή εργασία εκπονήθηκε προσβλέποντας στην επίλυση ορισμένων χρόνιων προβλημάτων του Τμήματος Πληροφορικής του ΑΤΕΙ Θεσσαλονίκης, προβλημάτων που σχετίζονται με την υφιστάμενη διαδικασία δηλώσεων μαθημάτων. Έχει αποδειχθεί στην πράξη ότι η υφιστάμενη μέθοδος εγγραφών από τη μία αδυνατεί να ικανοποιήσει τις προτιμήσεις των φοιτητών και από την άλλη δεν εγγυάται την εφαρμογή όλων των κανονισμών του Τμήματος Πληροφορικής. Επιπρόσθετα, η ισχύουσα διαδικασία δηλώσεων μαθημάτων απαιτεί την προσέλευση όλων των φοιτητών στο Τμήμα, για τη συμπλήρωση εντύπων, με αποτέλεσμα το συνωστισμό και την ταλαιπωρία των ιδίων, του εκπαιδευτικού και του διοικητικού προσωπικού.

Για την αντιμετώπιση αυτών των προβλημάτων κρίθηκε αναγκαία η ανάπτυξη ενός συστήματος, αποτελούμενου από (α) έναν εξελικτικό αλγόριθμο για τον χρονοπρογραμματισμό των φοιτητικών δηλώσεων, (β) τον ιστότοπο υποβολής τους και (γ) την εφαρμογή διαχείρισης. Ο εξελικτικός αλγόριθμος εμπεριέχει όλους εκείνους τους ελεγκτικούς μηχανισμούς που είναι απαραίτητοι για την τήρηση των κανονισμών προτεραιότητας. Ο ιστότοπος παρέχει στους φοιτητές τη δυνατότητα να υποβάλλουν τις δηλώσεις τους μέσω διαδικτύου – μεριμνώντας μεν για την αποθήκευση των σχετικών προτιμήσεων στη βάση δεδομένων, αγνοώντας όμως τη χρονολογική σειρά υποβολής τους. Η εφαρμογή διαχείρισης αποτελεί ένα χρήσιμο εργαλείο για το προσωπικό του Τμήματος, καθώς προσφέρει πλήθος επιλογών για τον έλεγχο του συστήματος και την ομαλή μετάβαση σε επόμενα ακαδημαϊκά εξάμηνα.

Το σύστημα δηλώσεων μαθημάτων που αναπτύχθηκε στα πλαίσια της παρούσας εργασίας δοκιμάστηκε κάνοντας χρήση μιας – ειδικής για το σκοπό αυτό – γεννήτριας εικονικών δηλώσεων μαθημάτων. Τα αποτελέσματα που προέκυψαν από τις πειραματικές δοκιμές του εξελικτικού αλγορίθμου ήταν κάτι περισσότερο από ενθαρρυντικά, σε σημείο μάλιστα που θεωρούμε ότι επιτεύχθηκαν οι αρχικοί μας στόχοι σε ικανοποιητικό βαθμό. Σε κάθε περίπτωση πάντως ευελπιστούμε ότι το σύστημα που αναπτύχθηκε μπορεί να αντικαταστήσει επιτυχώς την υφιστάμενη δια-δικασία δηλώσεων μαθημάτων, ικανοποιώντας όλους όσους εμπλέκονται σε αυτήν.

Λέξεις – κλειδιά:

εξελικτικοί αλγόριθμοι, πολυκριτηριακή βελτιστοποίηση, χρονοπρογραμματισμός δηλώσεων μαθημάτων, κατανεμημένη επεξεργασία, μοντέλο – προβολή – ελεγκτής

ABSTRACT

This final year thesis deals with some longstanding problems of the Informatics Department of ATEI of Thessaloniki, associated with the existing course registration procedure. It has been proven in practice that the current student registration method not only fails to meet the students’ needs but also does not guarantee the observance of the regulations of the Department of Informatics. In addition, the current course registration procedure requires the presence of all students at the same time, for filling in the appropriate forms. The results is overcrowding troubles and discomfort for both students educational and administrative staff.

In order to tackle these problems, we developed a system, consisting of three parts. The first one, is the web application. The second part refers to the evolutionary algorithm which is responsible for scheduling the submitted (via the web application) course selections and finally, there is an administrative tool which controls the whole system. The web application gives students the ability to submit their course preferences to the system’s database via the Internet, while ignoring the chronological order of that submission. The evolutionary algorithm includes all those control mechanisms necessary for the compliance with the Department’s priority regulations. The administrative tool is extremely useful for the staff of the Department, and offers numerous options for controlling the system, while insuring the smooth transition between semesters.

The course registration system, developed in the context of this work, was tested using one – especially designed – virtual course selection generator. The results of the experimental tests of the evolutionary algorithm were more than encouraging, even to the point that we feel we achieved our initial objectives, satisfactorily. In any case, we believe that the above system can successfully replace the existing course registration process and satisfy all those being involved in it.

Keywords:

evolutionary algorithms, multi-objective optimization, student scheduling, distributed computing, model – view - controller

ΠΕΡΙΕΧΟΜΕΝΑ

Αντί προλόγου	iii
Περίληψη	v
Abstract	vi
Κατάλογος σχημάτων	xii
Κατάλογος πινάκων	xvi
1 Εισαγωγή	1
2 Προβλήματα χρονοπρογραμματισμού	3
2.1 Εισαγωγή	3
2.2 Κατηγορίες προβλημάτων	4
2.2.1 Προβλήματα στην παραγωγή	4
2.2.2 Προβλήματα στις υπηρεσίες	7
2.3 Πολυκριτηριακή βελτιστοποίηση	10
2.4 Τεχνικές επίλυσης	12
2.4.1 Διακλάδωση και οριοθέτηση	13
2.4.2 Προγραμματισμός στόχων	13
2.4.3 Προσομοιωμένη ανόπτηση	14
2.4.4 Αποτρεπτική αναζήτηση	15
2.4.5 Προγραμματισμός με περιορισμούς	16
2.4.6 Βελτιστοποίηση αποικιών μυρμηγκιών	17
2.4.7 Εξελικτικοί αλγόριθμοι	18
3 Χρονοπρογραμματισμός με εξελικτικούς αλγορίθμους	21
3.1 Εισαγωγή	21
3.2 Ακαδημαϊκά προβλήματα	21
3.2.1 Προβλήματα κατά παραγγελία	22
3.2.2 Προβλήματα συνεχούς ροής	22
3.2.3 Προβλήματα ελεύθερης ροής	23
3.3 Ρεαλιστικά ακαδημαϊκά προβλήματα	24
3.4 Ιδιοσυγκρασιακά προβλήματα	25
3.5 Τεχνικά ζητήματα	26
3.5.1 Αναπαράσταση	26
3.5.2 Τελεστές ανασυνδυασμού	28

3.6 Μέθοδοι βελτίωσης του εξελικτικού αλγορίθμου	30
3.6.1 Υβριδοποίηση με τοπική αναζήτηση	30
3.6.2 Πολυκριτηριακοί εξελικτικοί αλγόριθμοι	30
3.6.3 Συν-εξέλιξη	32
3.6.4 Υπερ-ευρηστικές προσεγγίσεις	33
4 Χρονοπρογραμματισμός δηλώσεων μαθημάτων	35
4.1 Εισαγωγή	35
4.2 Προβλήματα χρονοπρογραμματισμού δηλώσεων μαθημάτων	38
4.3 Μελέτη περίπτωσης: Τμήμα Πληροφορικής ΤΕΙ-Θ	47
4.3.1 Ισχύουσα διαδικασία	50
4.3.2 Προτεινόμενη διαδικασία	52
5 Ανάλυση απαιτήσεων	57
5.1 Εισαγωγή	57
5.2 Λειτουργικές απαιτήσεις	57
5.3 Ποιοτικές απαιτήσεις	62
5.3.1 Ευχρηστία	62
5.3.2 Αξιοπιστία	65
5.3.3 Επίδοση	69
5.3.4 Υποστηριξιμότητα	71
5.4 Συμπληρωματικές απαιτήσεις	71
6 Αρχιτεκτονική και πλατφόρμα	75
6.1 Εισαγωγή	75
6.2 Αρχιτεκτονική συστήματος	75
6.2.1 Υπηρεσία χρονοπρογραμματισμού δηλώσεων	77
6.2.2 Υπηρεσία ηλεκτρονικών δηλώσεων	81
6.2.3 Υπηρεσία διαχείρισης συστήματος	86
6.3 Πλατφόρμα	88
6.3.1 Java	88
6.3.2 DREAM	90
6.3.2.1 Θεωρία – παράλληλα και κατανεμημένα συστήματα	90
6.3.2.2 Θεωρία – επιδημικοί αλγόριθμοι	94
6.3.2.3 Το ερευνητικό έργο DREAM	97
6.3.2.4 Αρχιτεκτονική και σημεία εισόδου χρηστών	98
6.3.2.5 DRM (Distributed Resource Machine)	100
6.3.2.6 JEO (Java Evolutionary Object)	104
6.3.2.7 Εκτέλεση πειραμάτων στο DREAM	115
6.3.3 Apache Tomcat	116
6.3.4 XHTML	116
6.3.5 Cascading Style Sheets	117
6.3.6 ECMAScript	117
6.3.7 Ajax	117
6.3.8 MySQL – InnoDB	118
6.3.9 Διακομιστές Archimedes και Hydra	120
6.3.10 Οι στοίβες του συστήματος	120
7 Σχεδίαση και υλοποίηση	123
7.1 Εισαγωγή	123
7.2 Εργαλεία ανάπτυξης	123
7.2.1 DB Visual Architect	123
7.2.2 MagicDraw UML	124
7.2.3 Eclipse – PMD	125
7.2.4 Mozilla Firefox – πρόσθετα ανάπτυξης εφαρμογών ιστού	127
7.2.5 JRat – λProbe	130
7.2.6 MySQL Query Browser, Administrator	131
7.3 Σχεδίαση συστήματος	132
7.3.1 Σχεδίαση βάσης δεδομένων	133
7.3.2 Σχεδίαση μηχανισμού προσπέλασης κοινών δεδομένων	137
7.3.3 Σχεδίαση εξελικτικού αλγορίθμου	141
7.3.3.1 Κωδικοποίηση	143
7.3.3.2 Αρχικοποίηση	148
7.3.3.3 Αξιολόγηση	151
7.3.3.4 Επιβίωση	153
7.3.3.5 Κριτήρια τερματισμού	153
7.3.3.6 Επιλογή	154
7.3.3.7 Ανασυνδυασμός	155
7.3.3.8 Μετάλλαξη	165
7.3.3.9 Μετανάστευση	171
7.3.4 Σχεδίαση ιστοτόπου	172
7.3.4.1 Το πρότυπο μοντέλο – προβολή – ελεγκτής (MVC)	172
7.3.4.2 Φίλτρα αιτημάτων και αποκρίσεων	175
7.3.4.3 Διαδικασίες ταυτοποίησης χρηστών	177
7.3.4.4 Καταστάσεις χρήστη	178
7.3.4.5 Πρότυπο ιστοσελίδας	179
7.3.4.6 Έλεγχοι κατά τη δήλωση μαθημάτων	181
7.3.4.7 Δεξαμενές συνδέσεων και νημάτων	183
7.3.4.8 Ακροατές γεγονότων και κρυφή μνήμη	184
7.3.5 Σχεδίαση διαχειριστικής εφαρμογής	185
7.4 Υλοποίηση	187
7.5 Επίπεδα ασφαλείας συστήματος	188
8 Αποτελέσματα πειραμάτων	190
8.1 Κύρια πειραματικά δεδομένα	190
8.2 Γεννήτρια (εικονικών) δηλώσεων μαθημάτων	191
8.3 Παράμετροι δοκιμών	194
8.4 Αποτελέσματα πειραμάτων	196
9 Συμπεράσματα – προοπτικές	201
Βιβλιογραφία	204
Γλωσσάρι	217
Παράρτημα Ι: Η βάση δεδομένων του συστήματος	230
Παράρτημα ΙΙ: Παραμετροποίηση συστήματος	239
Α Παραμετροποίηση βάσης δεδομένων	239
Β Παραμετροποίηση εξελικτικού αλγορίθμου	240
Γ Παραμετροποίηση ιστοτόπου	241
Δ Παραμετροποίηση διαχειριστικής εφαρμογής	244
Παράρτημα ΙΙΙ: Εγχειρίδιο χρήσης της κονσόλας DREAM	245
Α Ξεκινώντας	245
Β Επισκόπηση	246
Γ Επιθεώρηση	247
Δ Έναρξη πειραμάτων	253
Ε Επιλογές	256
ΣΤ Θεατής βοήθειας	258
Ζ Περαιτέρω έννοιες	259
Παράρτημα ΙV: Εγχειρίδιο χρήσης ιστοτόπου	262
Παράρτημα V: Εγχειρίδιο χρήσης διαχειριστικής εφαρμογής	273