Το Πρόβλημα του Bin Packing σε Δύο Διαστάσεις

Abstract

Η παρούσα εργασία μελετάει το πρόβλημα του Bin Packing σε Δύο Διαστάσεις, δηλαδή το πρόβλημα της συσκευασίας, ενός δεδομένου σύνολο μικρών ορθογωνίων, στον ελάχιστο αριθμό πανομοιότυπων μεγάλων ορθογωνίων κάδων, χωρίς να επικαλύπτονται και με τις άκρες τους παράλληλες με εκείνες των κάδων. Καθώς αποτελεί μία ειδική περίπτωση του Μονοδιάστατου Προβλήματος Πακετοποίησης, στο Πρώτο Κεφάλαιο μελετά τα χαρακτηριστικά του γενικού αυτού προβλήματος. Αρχικά, αφού γίνεται μια συνοπτική περιγραφή του προβλήματος, αναφέρονται οι εφαρμογές του σε πραγματικά προβλήματα κυρίως στη βιομηχανία, αλλά και σε πολλούς άλλους τομείς όπως η Οικονομία, Πληροφορική, Δίκτυα κ.α. Στη συνέχεια, δίνεται η μαθηματική προσέγγιση του προβλήματος, όπου περιγράφονται μαθηματικά ο στόχος και οι περιορισμοί του και ακολούθως, αναλύεται η κατηγοριοποίηση των προβλημάτων πακετοποίησης. Καθώς το πρόβλημα πακετοποίησης ανήκει στην κατηγορία των ΝΡ-hard προβλημάτων, καθιστά την εξεύρεση της βέλτιστης λύσης μια πολύ δύσκολη υπόθεση. Γι' αυτό το λόγο, η εξεύρεση της λύσης επιχειρείται μέσω διάφορων μεθόδων και τεχνικών που χρησιμοποιούνται για την επίλυση τέτοιων προβλημάτων. Στο Δεύτερο Κεφάλαιο, κάνουμε μία θεωρητική αναφορά στη Θεωρία της Πολυπλοκότητας, ώστε να καταλάβουμε τι είναι τα ΝΡ-hard προβλήματα, ενώ στο Τρίτο Κεφάλαιο αναλύουμε τις τρείς βασικές κατηγορίες αλγορίθμων (ακριβείς, ευρετικοί, μετα-ευρετικοί) που χρησιμοποιούνται για την εξεύρεση βέλτιστης λύσης ή την επίλυση προβλημάτων πακετοποίησης. Το Τέταρτο Κεφάλαιο αφορά τη Δισδιάστατη εκδοχή του προβλήματος του Bin Packing που αποτελεί και το βασικό αντικείμενο μελέτης της παρούσας εργασίας. Αρχικά επιχειρείται μία γενική θεωρητική ανασκόπηση του προβλήματος, ενώ στη συνέχεια γίνεται η μαθηματική περιγραφή του, με τα επιπλέον χαρακτηριστικά και περιορισμούς που έχει το δισδιάστατο πρόβλημα, σε σχέση με τη μονοδιάστατη εκδοχή που αναφέρθηκε παραπάνω. Στα επόμενα κεφάλαιο αναλύονται διάφοροι αλγόριθμοι, κυρίως ευρετικοί, που επιχειρούν με διαφορετικούς τρόπους να φτάσουν στη λύση του προβλήματος. Για την καλύτερη κατανόηση και προσέγγιση των αλγόριθμων αυτών, επιχειρήσαμε την κατηγοριοποίησή τους βάσει κάποιων βασικών χαρακτηριστικών τους, σε δύο μεγάλες ομάδες: (i) των αλγόριθμων shelf και non-shelf και (ii) των αλγόριθμων μίας φάσης και δύο φάσεων. ΣΤΟ τελευταίο κεφάλαιο, λόγω της ευρείας εφαρμογής της στον πραγματικό κόσμο, αναλύεται η 2ΒΡ|R|G παραλλαγή του δισδιάστατου προβλήματος, δηλαδή η περίπτωση όπου επιτρέπεται η αλλαγή προσανατολισμού των αντικειμένων κατά την τοποθέτησή τους και επιβάλλεται η κοπή σε γκιλοτίνα. Αναλύονται κάποιοι αλγόριθμοι που έχουν ήδη αναφερθεί παραπάνω, προσαρμοσμένοι στην RG περίπτωση, με τα επιπλέον χαρακτηριστικά και περιορισμούς που επιβάλλει η παραλλαγή αυτή του προβλήματος.