Multi-criteria divisible load scheduling in binary tree network
The Divisible Load Theory (DLT) is a paradigm in the area of parallel and distributed computing. Based on the divisible load theory, the computation and communication can be divided into some arbitrary independent parts, in which each part can be processed independently by a processor. A class o...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/69789/ http://psasir.upm.edu.my/id/eprint/69789/1/IPM%202016%209%20-%20IR.pdf |
| _version_ | 1848856507412643840 |
|---|---|
| author | Ghanbari, Shamsollah |
| author_facet | Ghanbari, Shamsollah |
| author_sort | Ghanbari, Shamsollah |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | The Divisible Load Theory (DLT) is a paradigm in the area of parallel and
distributed computing. Based on the divisible load theory, the computation and
communication can be divided into some arbitrary independent parts, in which each
part can be processed independently by a processor.
A class of the scheduling methods which is defined based on the DLT is called the
Divisible Load Scheduling (DLS).
The traditional divisible load scheduling assumes that the processors report their true
computation and communication rates, i.e., they do not cheat the algorithm. In the
real applications, the processors may cheat the algorithm, which means, the
processors might not report their true computation or communication rates.
However, the problem that the processors may not report their true computation rates
is called computation rate-cheating problem. The same definition can be considered
for the communication rate-cheating problem. However, this problem was
investigated by Thomas E. Carroll and D. Grosu in their research publications. The
results of their research indicate that the computation rate-cheating reduces the
performance of the divisible load scheduling.
This thesis focuses on the computation and communication rate-cheating problems
aiming to reduce the effects of computation and communication rate-cheating on the
performance of the divisible load scheduling model.
We adopt a multi-criteria approach to the problem. We propose three different multicriteria
based methods in order to improve the performance of the divisible load
scheduling. The first method is a multi-objective divisible load scheduling method.
The results show that this method is able to considerably improve the performance of
the divisible load scheduling when the processors cheat their computation rates. The experimental results indicate that the proposed method is able to reduce the finish
time by approximately 66% in the best case. The limitation of the proposed multiobjective
method is that this method slightly increases the start-up time. In order to
reduce the limitation of the multi-objective method, a second method has been
proposed, which is an Analytical Hierarchy Process (AHP) method. It is briefly
called AHP-based method.
The experimental results show that the AHP-based method is able to improve the
performance of divisible load scheduling. In addition, it has a lower start-up time
com- paring the multi-objective method.
In the third proposed method, it is assumed that both the communication and
computation might not be reported at the true rates; hence, we have a new approach
to the communication and computation rate-cheating problems. We propose a
priority-based divisible load scheduling method for the first time. The results show
that this method is able to allocate the optimal load when the processors cheat their
computation and communication rates. The proposed priority-based divisible load
scheduling method is a novel effort in the area of divisible load scheduling over the
past two decades. |
| first_indexed | 2025-11-15T11:42:45Z |
| format | Thesis |
| id | upm-69789 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T11:42:45Z |
| publishDate | 2016 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-697892019-10-29T06:59:07Z http://psasir.upm.edu.my/id/eprint/69789/ Multi-criteria divisible load scheduling in binary tree network Ghanbari, Shamsollah The Divisible Load Theory (DLT) is a paradigm in the area of parallel and distributed computing. Based on the divisible load theory, the computation and communication can be divided into some arbitrary independent parts, in which each part can be processed independently by a processor. A class of the scheduling methods which is defined based on the DLT is called the Divisible Load Scheduling (DLS). The traditional divisible load scheduling assumes that the processors report their true computation and communication rates, i.e., they do not cheat the algorithm. In the real applications, the processors may cheat the algorithm, which means, the processors might not report their true computation or communication rates. However, the problem that the processors may not report their true computation rates is called computation rate-cheating problem. The same definition can be considered for the communication rate-cheating problem. However, this problem was investigated by Thomas E. Carroll and D. Grosu in their research publications. The results of their research indicate that the computation rate-cheating reduces the performance of the divisible load scheduling. This thesis focuses on the computation and communication rate-cheating problems aiming to reduce the effects of computation and communication rate-cheating on the performance of the divisible load scheduling model. We adopt a multi-criteria approach to the problem. We propose three different multicriteria based methods in order to improve the performance of the divisible load scheduling. The first method is a multi-objective divisible load scheduling method. The results show that this method is able to considerably improve the performance of the divisible load scheduling when the processors cheat their computation rates. The experimental results indicate that the proposed method is able to reduce the finish time by approximately 66% in the best case. The limitation of the proposed multiobjective method is that this method slightly increases the start-up time. In order to reduce the limitation of the multi-objective method, a second method has been proposed, which is an Analytical Hierarchy Process (AHP) method. It is briefly called AHP-based method. The experimental results show that the AHP-based method is able to improve the performance of divisible load scheduling. In addition, it has a lower start-up time com- paring the multi-objective method. In the third proposed method, it is assumed that both the communication and computation might not be reported at the true rates; hence, we have a new approach to the communication and computation rate-cheating problems. We propose a priority-based divisible load scheduling method for the first time. The results show that this method is able to allocate the optimal load when the processors cheat their computation and communication rates. The proposed priority-based divisible load scheduling method is a novel effort in the area of divisible load scheduling over the past two decades. 2016-01 Thesis NonPeerReviewed text en http://psasir.upm.edu.my/id/eprint/69789/1/IPM%202016%209%20-%20IR.pdf Ghanbari, Shamsollah (2016) Multi-criteria divisible load scheduling in binary tree network. Doctoral thesis, Universiti Putra Malaysia. Computer scheduling - Mathematical models |
| spellingShingle | Computer scheduling - Mathematical models Ghanbari, Shamsollah Multi-criteria divisible load scheduling in binary tree network |
| title | Multi-criteria divisible load scheduling in binary tree network |
| title_full | Multi-criteria divisible load scheduling in binary tree network |
| title_fullStr | Multi-criteria divisible load scheduling in binary tree network |
| title_full_unstemmed | Multi-criteria divisible load scheduling in binary tree network |
| title_short | Multi-criteria divisible load scheduling in binary tree network |
| title_sort | multi-criteria divisible load scheduling in binary tree network |
| topic | Computer scheduling - Mathematical models |
| url | http://psasir.upm.edu.my/id/eprint/69789/ http://psasir.upm.edu.my/id/eprint/69789/1/IPM%202016%209%20-%20IR.pdf |