Η κατανομή των διαθέσιμων πόρων (πρώτες ύλες, μηχανές κ.α) μίας βιομηχανικής επιχείρησης, με στόχο την ελαχιστοποίηση του κόστους παραγωγής των αγαθών, λέγεται Προγραμματισμός Παραγωγής. Κάθε πρόβλημα βέλτιστης διάταξης εργασιών σε μία ή περισσότερες μηχανές, που εμφανίζεται στον Προγραμματισμό Παραγωγής, ονομάζεται πρόβλημα Χρονικού Προγραμματισμού. Η παρούσα εργασία ασχολείται με την επίλυση ενός τέτοιου προβλήματος. Συγκεκριμένα, του προβλήματος εκείνου που, δοθέντων Ν εργασιών, που πρέπει να εκτελεστούν σε μία μηχανή, χωρισμένων σε Β ομάδες, έτσι ώστε μεταξύ των εκτελέσεων δύο εργασιών που ανήκουν σε διαφορετικές ομάδες να μεσολαβεί ένα χρονικό διάστημα που η μηχανή μένει ανενεργή (χρόνος εξάρμωσης), ζητείται η ελαχιστοποίηση δύο κριτηρίων απόδοσης : του αθροίσματος των χρόνων αποπεράτωσης των εργασιών και της μέγιστης καθυστέρησης. Τα πλουκριτηριακά προβλήματα Χρονικού Προγραμματισμού αποτελούν ρεαλιστικότερη απεικόνιση της πραγματικότητας από τα προβλήματα ενός κριτηρίου, γιατί στην πράξη ζητούνται συνήθως προγράμματα (διατάξεις εργασιών) με μία γενικά καλή συμεριφορά, ως προς διάφορα κριτήρια. Η γενικότερη λύση ενός πολυκριτηριακού προβλήματος είναι ο υπολογισμός του συνόλου των αποδοτικών λύσεων, δηλαδή εκείνων για τις οποίες δεν υπάρχει κάποια άλλη με καλύτερη τιμή σε ένα κριτήριο και όχι χειρότερη στα υπόλοιπα. Αυτό είναι το ζητούμενο και στο πρόβλημα που πραγματεύεται η παρούσα εργασία. Η εύρεση μιας αποδοτικής λύσης ανάγεται στην επίλυση του προβλήματος ελαχιστοποίησης του αθροίσματος των χρόνων αποπεράτωσης δοθέντος ότι, ως προς κατάλληλα μετατοπισμένες δεξιότερα στον άξονα του χρόνου (από τις αρχικές του τιμές) προθεσμίες, δε θα καθυστερήσει καία εργασία. Αντίθετα από άλλα προβλήματα Χρονικού Προγραμματισμού με χρόνους εξάρμωσης, το τελευταίο πρόβλημα δεν είναι διατεταγμένων ομάδων, δηλαδή δεν είναι γνωστή η διάταξη των εργασιών σε κάθε ομάδα από την αρχή, με αποτελέσμα η πλοκή του να μην είναι εκθετική ως προς τον αριθμό των ομάδων, Β, αλλά ως προς τον αριθμό των εργασιών, Ν. Αφού παρουσιάσουμε αναλυτικά τα όσα είπαμε παραπάνω, στη συνέχεια της εργασίας παρουσιάζουμε μεθόδους επίλυσης προβλημάτων Χρονικού Προγραμματισμού που έχουν χρησιμοποιηθεί σε άλλες εργασίες (κυρίως μεθόδους υπολογισμού κάτω φράγματος για ένα κοινό σχήμα διαμερισμού και φραγής) και εξηγούμε γιατί καθεμιά από τις μεθόδους αυτές δεν μπορεί να εφαρμοστεί στο πρόβλημά μας. Οι βαθύτεροι λόγοι γι αυτό είναι πάντα η ύπαρξη των χρόνων εξάρμωσης και το γεγονός ότι το πρόβλημα δεν είναι διατεταγμένων ομάδων. Στη συνέχεια επιχειρούμε μία συγκριτική παρουσίαση των κλασσικότερων αλγορίθμων Δυναμικού Προγραμματισμού, και αναλύουμε τα προτερήματα και τα μειονεκτήματα τους έναντι του γενικού αλγορίθμου διαμερισμού και φραγής που συνήθως χρησιμοποιείται. Αμέσως μετά αναλύουμε τους λόγους που μας ώθησαν στην επιλογή του Δυναμικού Προγραμματισμού για την επίλυση του προβλήματός μας και παρουσιάζουμε τους δύο αλγορίθμους Δυναμικού Προγραμματισμού που υλοποιήσαμε. Έπειτα παρουσιάζουμε τα αποτελέσματα που πήραμε από την εκτέλεση εκτεταμένων πειραμάτων και εξηγούμε την παρατηρούμενη επίδραση του πλήθους των εργασιών, Ν, του πλήθους των ομάδων, Β, της θέσης που κατέχει κάποια αποδοτική λύση ανάμεσα στις υπόλοιπες και διάφορων παραμέτρων του προβλήματος, στον απαιτούμενο χρόνο επίλυσής του. Το μέγεθος των προβλημάτων κάθε αποδοτική λύση των οποίων υπολογίζεται σε χρόνο ενός λεπτού (μέχρι λίγο περισσότερες από 20 εργασίες) είναι μικρότερο του μεγέθους των προβλημάτων που σε άλλες εργασίες, που ασχολούνται με προβλήματα Χρονικού Προγραμματισμού χωρίς χρόνους εξάρμωσης, λύνονται στον ίδιο χρόνο (συνήθως γύρω στις 30 εργασίες, χωρίς να λείπουν και λίγες περιπτώσεις που φτάνουν στις 50), αλλά κρίνεται ικανοποιητικό αν συγκριθεί με τις επιδόσεις αλγορίθμου, που παρουσιάζεται σε πρόσφατα δημοσιευμένη εργασία, για την επίλυση τπυ προβλήματος που προκύπτει εάν από το δικό μας αφιαρέσουμε το κριτήριο της μέγιστης καθυστέρησης και που η λύση του αποτελεί μία από τις αποδοτικές λύσεις του δικού μας προβλήματος. Τελειώνοτας, παρουσιάζουμε μία γενική ιδέα που μπορεί να ακολουθεί ένας ευρηματικός αλγόριθμος, ο οποίος πολύ ταχύτερα από τον ακριβή θα λύνει προσεγγιστικά το δικριτηριακό μας πρόβλημα. Παρουσιάζουμε, επίσης, μία γενίκευση του αλγορίθμου Δυναμικού Προγραμματισμού που χρησιμοποιήσαμε για τον υπολογισμό μιας αποδοτικής λύσης, που λύνει απευθείας, με μεγαλύτερη όμως υπολογιστική πλοκή, το αρχικό δικριτηριακό πρόβλημα.
(EL)
Allocation of resources of an industrial enterprise, aiming to the minimization of the produstion cost, is called Production Scheduling. Each problem of optimal job sequencing (order) in one or more machines, is called Scheduling Problem. In the present work we deal with the solution of one such bicriterion problem: the minimization of the total finishing time and the maximum tardiness of N jobs in one machine, given that the jobs are distributed to B different groups, and a setup time is interposed bet between the executions of two jobs belonging to different groups. Multicriteria Scheduling Problems are in fact a more realistic view of reality compared to one-criterion problems. The most general solution of a multicriteria problem is the computation of the set of efficient solutions, that is, the solutions for which there is no other with better value in one criterion and not worse in the rest. This is the issue to the problem which we deal with in this work. The finding of an efficient solution can be achieved by solving the problem of minimization of the total completion time, given that, according to modified due dates in a right direction adjustment mode, no job will be tardy. This problem does not belong to the class of ordered batch scheduling problems, and so its complexity is exponential to the number of jobs N - not the number of groups B. After the analytical presentation of what we have said until now, we present solution methods of Scheduling Problems which were used in other works (basically, methods to derive lower bounds for a common branch and bound scheme), and we explain the reasons for which none of these methods can be applied to our problem. The main reason for this is the existence of setup times as well as the fact that our problem is not an ordered batch problem. Then we present a comparative study of the most common Dynamic Programming algorithms used for the solution of Scheduling Problems, and we analyze their advantages and disadvantages towards the generally used branch and bound algorithm. The reasons for which we used Dynamic Programming as the solution technique to our problem, as well as the two algorithms implemented, as then presented. We next give the results taken from extended experimentation, and discuss the influence of the number of jobs N, the number of groups B, the position of an efficient solution inside a set of other solutions, and other problem parameters to the solution time. The size of problems (a few more than 20 jobs) for which each efficient solution is found within 1 minute CPU time, is smaller than the size of problems solved, in the same computational time, in order works dealing with Scheduling Problems without setup times (usually around 30 jobs but in a few cases the reach 50). On the other hand, it can be characterized satisfactory when is used for the solution of the problem without the tardiness criterion, and whose solution is one of the efficient solutions of our problem. Finally, we give a general idea for a heuristic algorithm that can solve approximately our bicriterion problem in much less time. We also present a generalization of the Dynamic Programming algorithm that we used to find one efficient solution. This generalized algorithm can solve directly, but with greater complexity, the initial bicriterion problem.
(EN)
