Συστήματα αλγορίθμων λεπτομερειακού χρονικού προγραμματισμού παραγωγής

Abstract

The aim of this thesis is to provide a thorough assessment regarding the application of the complex and multifaceted hybrid metaheuristics designed for the deterministic job shop scheduling problem, henceforth JSSP, to real world problems. The JSSP problem has been a topic of active research for the past five decades attracting numerous researchers from the fields of operations research, production management and combinatorial optimization. The literature review and computational study of various state of the art algorithms has eloquently evinced that no single strategy can effectively tame this stubborn and intractable problem. Therefore, the research efforts have focused on hybrids that combine underlying myopic heuristics and general meta-techniques. The former are used to incorporate the much necessitated problem specific knowledge stemming from the morphology of the solution space, whereas the latter aim at guiding the search away from the numerous local minima that may be encountered by the algorithm. The current state of the art algorithms, abetted by the constant evolution of processing units and the augmentation of computing power, have managed to achieve high levels of robustness and effectiveness on a wide range of available benchmark problems, while remaining efficient with relatively small computational overhead. This gives rise to the research question posed within the scope of this thesis: are these types of algorithms applicable and efficient in dynamic shop floors as they are on the JSSP? A brief answer derived from the results of the empirical analysis performed is the following: they are not applicable, unless they undergo a significant degree or parameterization, to the point of altering the initial characteristics, and are combined with additional heuristic mechanisms and decision support tools. This statement is in full alignment with the architecture of the APS (Advanced Planning and Scheduling) systems whose development and implementation are geared towards the fulfillment of practical detailed scheduling requirements. The algorithms embedded within these systems are either exact or approximate and are supported by an array of decision support tools to aid the planner in the decision making process. Unfortunately, the implementation of APS systems is not without serious and sometimes insurmountable shortcomings, such as high acquisition and parameterization cost, time consuming schedule generation, redundant functionality, inability by the algorithms to assimilate the endemic particularities of a production process, steep learning curve and problematic interoperability with the rest of the IT infrastructure. Therefore, it is obvious that APS systems are a prohibitory choice for SMEs (Small to Medium Enterprises) and an alternate approach is necessitated. As it happens, this is the main contribution of this thesis: an approach for the application of efficient and effective JSSP algorithms to dynamic problem structures in the form of complete DSSs (Decision Support Systems). In order to construct this blueprint, the research process was sectored in two distinct parts. The first part focuses solely on deterministic detailed production scheduling. An analysis of the solution space properties and the theoretical background of the JSSP is conducted, followed by an extensive literature review regarding the available algorithms applied to combinatorial optimization problems. The conclusions drawn from the review are utilized in order to develop a parallel hybrid metaheuristic which combines genetic algorithms and tabu search. The hybrid is validated through its application on all the available 242 benchmark problems from the JSSP domain, as well as 40 problems from the FSSP (Flow Shop Scheduling Problem). The results clearly demonstrate that the proposed algorithm is state of the art for the FSSP and the state of the art genetic local search method for the JSSP. The second part of the thesis is dedicated to the identification of the preferred approach for adapting the proposed algorithm to dynamic detailed production scheduling problems. In this respect, it was deemed essential first and foremost to study the key differences between theory and practice and highlight the points that merit investigation. Afterwards, an elaborate literature survey is performed concerning the embedded algorithms, functionality and implementations of APS systems. The subsequent conclusions are exploited to transform the proposed algorithm into the eGantt DSS. The effectiveness, robustness and efficiency of the system are tested by its application to a real world case study from the metal forming industry and specifically the manufacturing of light metal sheet products such as door locks and aluminum window panes. The cumulative results of both the first and the second part validate the proposed approach of the thesis.

Σκοπός της παρούσας διατριβής είναι να διερευνήσει ενδελεχώς τις δυνατότητες εφαρμογής των σύνθετων και πολύπλοκων υβριδικών μεταευρετικών αλγορίθμων του θεωρητικού λεπτομερειακού προγραμματισμού παραγωγής σε πρακτικά προβλήματα. Η ντετερμινιστική μορφή του λεπτομερειακού προγραμματισμού παραγωγής, το λεγόμενο και JSSP (Job Shop Scheduling Problem), έχει απασχολήσει ερευνητές ανά τον κόσμο συστηματικά τις τελευταίες πέντε δεκαετίες. Η βιβλιογραφική ανασκόπηση και υπολογιστική σύγκριση μεταξύ state-of-the-art αλγορίθμων κατέδειξε πως δεν υπάρχει μεμονωμένη στρατηγική που να δύναται να επιλύσει αυτό το δυσεπίλυτο και πολύπλοκο πρόβλημα. Ως εκ τούτου, η έρευνα έχει στραφεί σε γενικευμένους υβριδικούς μεταευρετικούς αλγορίθμους και ειδικούς ευρετικούς μηχανισμούς. Οι μεν πρώτοι αξιοποιούνται κατά κύριο λόγο για τον απεγκλωβισμό της αναζήτησης από τοπικά βέλτιστα, ενώ οι δε δεύτεροι αξιοποιούν γνώση συσχετιζόμενη με το χώρο λύσεων του JSSP. Οι σύγχρονοι state-of-the-art αλγόριθμοι υποβοηθούμενοι πάντα από τη διαρκή εξέλιξη των επεξεργαστών και την επαύξηση της υπολογιστικής ισχύος, έχουν κατορθώσει να επιτυγχάνουν πολύ υψηλή απόδοση και σταθερότητα με μικρό σχετικά υπολογιστικό κόστος για την πλειοψηφία των προβλημάτων μέτρησης απόδοσης του JSSP. Μολαταύτα, γεννάται το ερώτημα: τέτοιου είδους αλγόριθμοι είναι εφαρμόσιμοι και εξίσου αποδοτικοί στην πράξη; Μια πρώτη απάντηση δίνεται από το περιεχόμενο αυτής της διατριβής και συνοψίζεται ως εξής: δεν είναι εφαρμόσιμοι, παρεκτός αν παραμετροποιηθούν σε σημαντικό βαθμό, αλλοιώνοντας την πλειοψηφία των αρχικών τους χαρακτηριστικών, και συνδυαστούν με πρόσθετους ευρετικούς μηχανισμούς και εργαλεία υποστήριξης αποφάσεων. Στην απάντηση αυτή συνηγορεί και η αρχιτεκτονική των συστημάτων APS (Advanced Planning Scheduling) που στοχεύουν στην επίλυση δυναμικών προβλημάτων λεπτομερειακού προγραμματισμού παραγωγής. Τα συστήματα αυτά ενσωματώνουν είτε αναλυτικούς, είτε γενικευμένους προσεγγιστικούς αλγορίθμους και τους ενισχύουν με μια σειρά εργαλείων για την υποστήριξη του χρήστη στη λήψη αποφάσεων. Δυστυχώς, χαρακτηρίζονται από μια σειρά μειονεκτημάτων όπως το υψηλό κόστος κτήσης και παραμετροποίησης, η εξαιρετικά χρονοβόρα διαδικασία δημιουργίας πλάνων παραγωγής, η περιττή λειτουργικότητα, η αδυναμία αφομοίωσης των ιδιαιτεροτήτων της παραγωγής από τους διαθέσιμους αλγόριθμους κ.α.. Συνεπώς, είναι προφανές πως ιδίως για SMEs (Small to Medium Enterprises) τα APS καθίστανται απαγορευτικά και είναι σκόπιμη μια εναλλακτική προσέγγιση. Αυτή είναι και η κύρια συνεισφορά της διατριβής: μια προσέγγιση για την καλύτερη δυνατή εφαρμογή λίαν αποδοτικών αλγορίθμων του JSSP σε πρακτικά προβλήματα υπό τη μορφή ολοκληρωμένων συστημάτων υποστήριξης αποφάσεων DSS (Decision Support Systems). Προκειμένου να καταστρωθεί αυτή η προσέγγιση η ερευνητική διαδικασία χωρίστηκε σε δύο μέρη. Το πρώτο μέρος σχετίζεται με θεματικές ενότητες που άπτονται του ντετερμινιστικού λεπτομερειακού προγραμματισμού παραγωγής. Αρχικά, μελετώνται οι ιδιότητες και το θεωρητικό υπόβαθρο του χώρου λύσεων του JSSP και αναλύονται όλοι οι διαθέσιμοι αλγόριθμοι για την επίλυση προβλημάτων διακριτής βελτιστοποίησης. Εν συνεχεία, τα χρήσιμα συμπεράσματα της ανασκόπησης αξιοποιούνται για την ανάπτυξη ενός παράλληλου υβριδικού μεταευρετικού αλγορίθμου που συνδυάζει γενετικούς αλγόριθμους με αναζήτηση tabu. Τέλος, η αποδοτικότητα του αλγοριθμικού μοντέλου αξιολογείται κατά την εφαρμογή του σε 242 προβλήματα μέτρησης απόδοσης διακριτής παραγωγής (JSSP) και 40 ροϊκής (FSSP- Flow Shop Scheduling Problem). Είναι άξιο μνείας πως ο εν λόγω αλγόριθμος αποδείχθηκε state-of-the-art για το FSSP και ως η state-of-the-art μέθοδος γενετικής τοπικής αναζήτησης για το JSSP. Κατά το δεύτερο μέρος εξετάζεται ποια είναι η προτιμητέα ατραπός για την προσαρμογή του προτεινόμενού αλγορίθμου σε δυναμικά προβλήματα λεπτομερειακού προγραμματισμού. Αρχικά, μελετάται η διάσταση μεταξύ θεωρίας και πράξης και υπερτονίζονται τα σημεία που χρίζουν ιδιαίτερης προσοχής. Κατόπιν, διενεργείται βιβλιογραφική ανασκόπηση αναφορικά με τους αλγόριθμους, τη λειτουργικότητα και τις εφαρμογές των συστημάτων APS. Βάσει των προκύπτοντων συμπερασμάτων, ο προτεινόμενος αλγόριθμος μορφοποιείται ως το DSS eGantt. Η αποδοτικότητα του eGantt αξιολογείται καθολικά από την εφαρμογή του σε μελέτη περίπτωσης, προερχόμενη από τον κλάδο μεταποίησης μετάλλου και ειδικότερα την κλειθροποιḯα. Τα συγκεντρωτικά αποτελέσματα του πρώτου και του δεύτερου μέρους επικυρώνουν την προτεινόμενη προσέγγιση της διατριβής.