Επίλυση προβλημάτων βέλτιστης ανάθεσης με το λογισμικό ανοικτού κώδικα Python

Abstract

Η παρούσα διπλωματική εργασία πραγματεύεται το πρόβλημα της πακετοποίησης (bin packing problem) και συγκεκριμένα της μονοδιάστατης εφαρμογής του. Λόγω της πολυπλοκότητας του, το πρόβλημα ανήκει στην κατηγορία των NP-hard προβλημάτων, γεγονός που καθιστά την εξεύρεση της βέλτιστης λύσης μια πολύ δύσκολη υπόθεση. Αρχικά, γίνεται μια αναφορά στην περιγραφή του προβλήματος, στα είδη και στις εφαρμογές του, οι οποίες το καθιστούν επίκαιρο και διαρκώς ενδιαφέρον. Οι περισσότερες φυσικά έχουν να κάνουν με τον τομέα της Πληροφορικής, της Βιομηχανίας, της Έρευνας Επιχειρήσεων και της Οικονομίας. Έπειτα παρατίθενται επιγραμματικά οι προσεγγίσεις επίλυσης που προτείνονται στην βιβλιογραφία. Μετά από την ανάλυση των πιο διαδεδομένων μεθόδων, υλοποιούνται οι προαναφερθείσες προσεγγίσεις με τη βοήθεια της γλώσσας προγραμματισμού Python. Τέλος, καταγράφονται τα συμπεράσματα από την θεωρητική ανασκόπηση αλλά και την πρακτική υλοποίηση της διαδικασίας της επίλυσης του bin packing problem με τη χρήση της Python.

This diploma thesis deals with the problem of bin packing problem, namely its one-dimensional type. Due to its complexity, the problem belongs to the NP-hard problem category, which makes the finding of the optimal solution a very difficult task. Initially, a reference is made to the description of the problem, its types and applications, which make it relevant and constantly interesting. Of course, most of them have to do with IT, Industry, Business Research and the Economy. The resolving approaches proposed in the bibliography are then outlined. After analyzing the most common methods, these approaches are implemented using the programming language Python. Finally, the findings from the theoretical review and the practical implementation of the bin packing problem solution using Python are documented.