Optimization methods for complex production planning and scheduling problems

Abstract

This doctoral thesis deals with the development of advanced optimization methods for complex production planning and scheduling problems. The study focuses on the effectiveness of hybrid metaheuristic algorithms. In the context of this thesis highly effective and efficient optimization methods are proposed for the Master Scheduling Optimization problem and the typical shop scheduling problems. The goals of this thesis are threefold: a) the development of an efficient Master Production Schedule (MPS) metaheuristic optimization algorithm (genetic), b) the development of advanced hybrid metaheuristic algorithms for the common shop scheduling problems (job-shop flow-shop open shop), c) the unification and the completion of these algorithms under a common Enterprise Resource Planning (ERP) platform. The results of study indicate that: a) the MPS optimization algorithm developed achieved higher performance against the incorporated optimization algorithm of a modern ERP system, b) the shop scheduling optimization algorithms rival the current state of the art metaheuristic algorithms found in the literature yet they remain fast and simple in structure. It should be reported that in some cases they managed to find new global best solutions. All three algorithms developed are based on artificial intelligence-based methods for the initial solution generation and on a particularly efficient hybrid component composed of variable neighborhood search (VNS) and genetic algorithm (GA), c) The unification scheme of the above algorithms in ERP systems managed to link successfully all the individual aforementioned components. It should be reported that the resulting Decision Support System has already been installed in a leading Greek enterprise with great success.

Η διδακτορική αυτή διατριβή πραγματεύεται την ανάπτυξη μεθόδων βελτιστοποίησης για την επίλυση πολύπλοκων προβλημάτων σχεδιασμού και χρονοπρογραμματισμού παραγωγής. Η κύρια προσπάθεια εστιάζεται στη μελέτη της υπολογιστικής δύναμης των υβριδικών μεταευρετικών αλγορίθμων. Σε μια προσπάθεια να καλυφθούν τα κενά της βιβλιογραφίας η διδακτορική αυτή διατριβή έρχεται να προτείνει ιδιαίτερα αποδοτικές και αποτελεσματικές μεθόδους για την επίλυση των προβλημάτων σχεδιασμού παραγωγής (βελτιστοποίηση Κύριου Προγράμματος Παράγωγης) καθώς και προβλημάτων χρονοπρογραμματισμού παραγωγής τύπου shop. Οι στόχοι αυτής της μελέτης είναι κυρίως τρεις: α) η ανάπτυξη ενός αποδοτικού σχεδίου βελτιστοποίησης σχεδιασμού παραγωγής με την ανάπτυξη ενός απλού και γρήγορου μεταευρετικού (γενετικού) αλγορίθμου για τη βελτιστοποίηση του Κύριου Προγράμματος Παραγωγής (MPS), β) η ανάπτυξη προηγμένων υβριδικών μεταευρετικών αλγορίθμων για τα κοινά προβλήματα προγραμματισμού τύπου shop (job shop, flow shop, open shop) τα οποία αποτελούν ένα μεγάλο ποσοστό των πραγματικών περιβαλλόντων παραγωγής, γ) η ενοποίηση και η ολοκλήρωση αυτών των αλγορίθμων κάτω από την κοινή πλατφόρμα ERP. Τα αποτελέσματα της μελέτης υποδεικνύουν ότι: α) ο αλγόριθμος βελτιστοποίησης σχεδιασμού παραγωγής κατόρθωσε να επιτύχει υψηλότερη απόδοση έναντι της ενσωματωμένης λειτουργίας βελτιστοποίησης ενός σύγχρονου συστήματος ERP, β) οι αλγόριθμοι προγραμματισμού παραγωγής που σχεδιάστηκαν ανταγωνίζονται τους καλυτέρους μεταευρετικούς αλγορίθμους βελτιστοποίησης παγκοσμίως παραμένοντας ταυτόχρονα εύκολοι στην εφαρμογή, γρήγοροι και απλοί στη δομή. Πρέπει να αναφερθεί ότι κατόρθωσαν να βρουν νέες καλύτερες λύσεις σε ορισμένες συγκριτικές μετρήσεις επιδόσεων. Και οι τρεις αλγόριθμοι που αναπτύχθηκαν βασίζονται σε ευφυείς μεθόδους δημιουργίας αρχικών λύσεων και σε ένα ιδιαίτερα αποδοτικό υβρίδιο έρευνας μεταβλητής γειτονίας (VNS) και γενετικού αλγορίθμου (GA), γ) το σχέδιο ενσωμάτωσης των παραπάνω αλγορίθμων σε συστήματα ERP ενώνει επιτυχώς τους αλγορίθμους βελτιστοποίησης που προαναφέρθηκαν. Πρέπει να αναφερθεί ότι το προκύπτον Σύστημα Υποστήριξης Αποφάσεων (ΣΥΑ) έχει ήδη εγκατασταθεί σε μια πρωτοπόρο Ελληνική κατασκευαστική επιχείρηση με μεγάλη επιτυχία.