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

Abstract

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