|
|
| Κωδικός Πόρου |
uch.csd.msc//1991georgiou |
| Τίτλος |
Το Πρόβλημα της Μέγιστης Καθυστέρησης σε μία Μηχανή με Χρόνους Εξάρμωσης |
| Άλλος τίτλος |
The Problem of Maximum Tardiness on One Machine with Setup Times |
| Συγγραφέας |
Γεωργίου, Θαλής
|
| Συντελεστής |
Π. Κωνσταντόπουλος
|
| Περίληψη |
In this paper we consider the problem of sequencing groups of jobs in which there is a set-up time associated with switching from jobs in one group to another. We consider the case of a single machine and sequence independent set-up times. A cost function (maximum tardiness) evaluates a schedule by assigning it a cost. Scheduling problems with set-up times appear in the production planning area. This work is a part of a general attempt concerning the development of an interactive information system for detailed scheduling. Algorithms propose optimal or near optimal solutions according to some basic criteria. The proposals of the algorithms might be reconsidered by the user of the system who is the one that makes the decision upon the final production program. The solution of the maximum tardiness problem is based on the idea of lotts creation ( sequence of jobs coming from the same group, which are executed one after the other in an optimal program ) and the analysis of tardiness distribution in jobs sequences. The ploblem of maximum tardiness without set-up times is simple and can be solved in $O( N log(N))$ time where N is the number of jobs. When we have set-up times it becomes $NP-hard$ and it is expected to be difficult to solve it optimally. Two branch and bound algorithms are proposed in order to find an optimal solution. The first creates the optimal schedule placing jobs from the begining to the end, while the second works in the opposite order. Another approximate algorithm is proposed as well, which solves large-size problems that appear mostly in real time applications. Then we present some experimental results over a set of random problems and our conclusions. Critical factors about the problem is the due-date's distribution, the number of groups and the number of jobs per group. Eventhough the problem is $NP-hard$ the experimental results showed that the nature of the problem is such that we can apply heuristic algorithms in order to have real good approximate solutions. Problems in the order of hundreds of jobs can be solved in one second CPU-time with mean deviation from the optimal solution less than 2%. Finally, we refer to scheduling problems whose solution reletes or it can be reduced to the solution of the problem presented here and to generalizations of the algorithms proposed here.
|
| Θέμα |
Αλγοριθμική και Ανάλυση Συστημάτων |
| Ημερομηνία έκδοσης |
1991-12-01 |
| Ημερομηνία διάθεσης |
1997-06-2 |
| Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
| Εμφανίσεις |
422 |
Το Πρόβλημα της Μέγιστης Καθυστέρησης σε μία Μηχανή με Χρόνους Εξάρμωσης
