Eφαρμογές της μεθόδου του στοχαστικού δυναμικού προγραμματισμού σε προβλήματα συντήρησης και δρομολόγησης

Abstract

Στην παρούσα διατριβή μελετώνται δύο κατηγορίες προβλημάτων: i)Προβλήματα για τη βέλτιστη προληπτική συντήρηση μηχανημάτων που είναι συνιστώσες ενός συστήματος παραγωγής, το οποίο περιέχει έναν ή δύο αποθηκευτικούς χώρους ανάμεσα στα μηχανήματα και ii)Προβλήματα για τη βέλτιστη δρομολόγηση ενός οχήματος που διανέμει ή/και συλλέγει προϊόντα από πελάτες, οι οποίοι εξυπηρετούνται σύμφωνα με μία προκαθορισμένη σειρά. Τα προβλήματα αμφοτέρων των κατηγοριών είναι στοχαστικά. Στην πρώτη κατηγορία προβλημάτων θεωρούμε ότι η φθορά των μηχανημάτων περιγράφεται από μία Μαρκοβιανή αλυσίδα και οι χρόνοι των προληπτικών (όπως και των διορθωτικών) συντηρήσεών τους είναι τυχαίες μεταβλητές. Στη δεύτερη κατηγορία προβλημάτων οι ζητήσεις των πελατών για τα προϊόντα που διανέμονται ή/και συλλέγονται είναι τυχαίες μεταβλητές. Χρησιμοποιώντας γνωστά αποτελέσματα από τη θεωρία του στοχαστικού δυναμικού προγραμματισμού σε πεπερασμένο και άπειρο χρονικό ορίζοντα αναπτύσσουμε κατάλληλους αλγορίθμους για την εύρεση της βέλτιστης πολιτικής στις δύο κατηγορίες προβλημάτων. Ως κριτήριο βελτιστοποίησης για την πρώτη κατηγορία προβλημάτων θεωρούμε την ελαχιστοποίηση του μακροπρόθεσμου αναμενόμενου μέσου κόστους ανά μονάδα χρόνου. Ως κριτήρια βελτιστοποίησης για τη δεύτερη κατηγορία προβλημάτων θεωρούμε την ελαχιστοποίηση του αναμενόμενου συνολικού κόστους μέχρι την εξυπηρέτηση όλων των πελατών και την ελαχιστοποίηση του μακροπρόθεσμου αναμενόμενου μέσου κόστους ανά μονάδα χρόνου. Στα περισσότερα υπό μελέτη προβλήματα αποδεικνύεται ότι η βέλτιστη πολιτική χαρακτηρίζεται από συγκεκριμένους κρίσιμους αριθμούς. Στην πρώτη κατηγορία προβλημάτων οι κρίσιμοι αριθμοί είναι συγκεκριμένοι βαθμοί φθοράς των μηχανημάτων. Η βέλτιστη πολιτική θέτει σε λειτουργία τις προληπτικές συντηρήσεις των μηχανημάτων αν και μόνον αν παρατηρηθεί ότι οι βαθμοί φθοράς αυτών υπερβαίνουν τους κρίσιμους αριθμούς. Στη δεύτερη κατηγορία προβλημάτων οι κρίσιμοι αριθμοί είναι συγκεκριμένες ποσότητες των προϊόντων που μένουν μέσα στο όχημα αφού αυτό επισκεφθεί γιά πρώτη φορά και προσφέρει τη μέγιστη εξυπηρέτηση σε κάποιον πελάτη. Η βέλτιστη πολιτική υποδεικνύει στο όχημα να συνεχίσει την πορεία του προς τον επόμενο πελάτη αν τα φορτία του υπερβαίνουν αυτούς τους κρίσιμους αριθμούς. Σε άλλες περιπτώσεις η βέλτιστη ενέργεια είναι να επιστρέψει μία ή δύο φορές στην αποθήκη για ανεφοδιασμό πριν προχωρήσει προς τον επόμενο πελάτη. Σε όλα τα υπό μελέτη προβλήματα παρέχονται εκτενή αριθμητικά αποτελέσματα. Εξετάζεται η επίδραση διαφόρων παραμέτρων στη βέλτιστη πολιτική