Back to search

Οικονομικό Πανεπιστήμιο Αθηνών

ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ: ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ

Abstract

dc:description

THE 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/1201

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Μήλης, Ιωάννης. ΑΝΑΘΕΣΗ ΕΡΓΑΣΙΩΝ ΣΕ ΚΑΤΑΝΕΜΗΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΣΥΣΤΗΜΑΤΑ: ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ. Οικονομικό Πανεπιστήμιο Αθηνών, 1989. http://hdl.handle.net/10442/hedi/1201