Οικονομικό Πανεπιστήμιο Αθηνών
ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ: ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ
Abstract
dc:descriptionTHE PROBLEM OF ASSIGNING THE TASKS OF A SOFTWARE SYSTEM TO THE PROCESSORS OF A DISTRIBUTED ENVIRONMENT IS EXAMINED. THE AIM OF THE ASSIGNMENT IS THE MINIMIZATION OF THE SUM OF EXECUTION TIME PLUS THE COMMUNICATION OVERHEADS. IN THE THESIS WE FORMALLY SHOW THAT THE PROBLEM, FOR THREE OR MORE PROCESSORS, IS NP-COMPLETE. UNDER THIS MAIN RESTRICTION WE PRESENT THREE NEW ALGORITHMS FOR THE PROBLEM. THE FIRST IS A POLYNOMIAL DYNAMIC PROGRAMMING ALGORITHM FOR THE SPECIAL CASE IN WHICH THE COMMUNICATION PATTERN BETWEEN THE TASKS FORMS A SERIES-PARALLEL GRAPH. THE SECOND, AN EXHAUSTIVE SEARCH ALGORITHM, RELIES ON AN EFFICIENT LOWER BOUND THAT WE GENERATE BY DISREGARDING A NUMBER OF COMMUNICATION LINKS REDUCING THUS THE ORIGINAL COMMUNICATION STRUCTURE TO A TREE FOR WHICH THE OPTIMIZATION PROBLEM IS POLYNOMIALLY SOLVABLE.THESE BOUNDS SERVE AS THE BASIS FOR A BRANCH AND BOUND ALGORITHM FOR THE GENERAL PROBLEM. WE DISCUSS THE IMPLEMENTATION OF THE ALGORITHM AND PROVIDE REPRESENTATIVE RESULTS. THE THIRD IS A HEURISTIC ALGORITHM. THE ALGORITHM USING MIN- CUT TECHNIQUES ACHIEVES A VERY GOOD APPROXIMATION OF THE OPTIMAL SOLUTION, AS SHOWN FROM NUMERICAL RESULTS, WITHIN POLYNOMIAL TIME.
Degree
thesis:*- Grantor dc:publisher
- Οικονομικό Πανεπιστήμιο Αθηνών
- Year dc:date
- 1989
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Μήλης, Ιωάννης
Subjects
dc:subject × 20- BRANCH-ANDBOUND
- Computational complexity
- Distributed systems
- Dynamic programming
- Heuristic algorithms
- MINIMUMCUT
- SERIES-PARALLEL GRAPHS
- TASK ASSIGNMENT
- ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ
- Δυναμικός προγραμματισμός
- ΕΛΑΧΙΣΤΗ ΤΟΜΗ ΓΡΑΦΗΜΑΤΟΣ
- Ευρετικοί αλγόριθμοι
- Κατανεμημένα συστήματα
- ΜΕΘΟΔΟΣ ΔΙΑΚΛΑΔΩΣΗΣ ΚΑΙ ΦΡΑΓΜΑΤΟΣ
- Πολυπλοκότητα
- ΣΕΙΡΙΑΚΑ ΠΑΡΑΛΛΗΛΑ ΓΡΑΦΗΜΑΤΑ
- Κοινωνικές Επιστήμες
- Social Sciences
- Άλλες Κοινωνικές Επιστήμες
- Other Social Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/1201