You are here

Home » Content

The Branch & Bound Algorithm Improvement in Divisible Load Scheduling with Result Collection on Heterogeneous Systems by New Heuristic Function

Journal Name:

  • International Journal of Science and Engineering Investigations

Publication Year:

  • 2012

Key Words:

Author NameUniversity of Author
Abstract (2. Language): 
in this paper we propose a new heuristic function, for Branch & Bound algorithm. By this function we can increase the efficiency of Branch & bound algorithm. Divisible loads represent computations which can be arbitrarily divided into parts and performed independently parallel. The scheduling problem consists in distributing the load in a heterogeneous system taking into account communication and computation times, so that the whole processing time is as short as possible. Since our scheduling problem is computationally hard, we propose a Branch & Bound algorithm. By simulating and comparing results, it is observed which this result produces better answers than other methods, it means that, branch & bound algorithm have less total average of relative error percentage in the variety Heuristic functions.
Bookmark/Search this post with
FULL TEXT (PDF): 
PDF icon arastirmax-branch-bound-algorithm-improvement-divisible-load-scheduling-result-collection-heterogeneous-systems-new-heuristic-function.pdf
  • 1
62-65
  • English

REFERENCES

References: 

[1] V.Bharadwaj, D.Ghose, V.Mani, T.G.Robertazzi. “Scheduling Divisible
Loads in Parallel And Distributed Systems”, IEEE Computer Society
Press, Los Alamitos CA (1996)
[2] C.H. Lee and K.G. Shin, “Optimal task assignment in homogeneous
networks” IEEE Trans. Parallel Distrib. Syst., vol.8, no.2, pp.119129,
Feb. 1997.
[3] G.D. Barlas, “Collection-aware optimum sequencing of oprations and
closed-form solutions for the distribution of divisible load on arbitrary
processor trees,” IEEE Trans. Parallel Distrib. Syst., vol.9, no.5, pp.429-441, May 1998.
[4] R. Agrawal, H.V. Jagadish, “Partitioning Techniques for Large-Grained
Parallelism”, IEEE Transactions on Computers 37(12), 1627-1634
(1988)
[5] Y.-C.Cheng, T.G.Robertazzi, “Distributed computation with
communication delay”. IEEE Transactions on Aerospace and Electronic
Systems 24, 700-712 (1988)
[6] T.G. Robertazzi. “Ten reasons to use divisible load theory”, IEEE
Computer, 36, 63–68 (2003)
[7] Bharadwaj, V., Ghose, D., Robertazzi, T. G., "Divisible Load Theory: A
New Paradigm for Load Scheduling in Distributed Systems", Cluster
Computing, vol.6, no.1, pp.7-17, Jan. 2003.
[8] Jingxi, J., Bharadwaj, V., Ghose, D., "Adaptive Load Distribution
Strategies for Divisible Load Processing on Resource Unaware
Multilevel Tree Networks", IEEE Transactions on Computers, vol. 65,
no. 7, pp. 99-1005, 2007.
[9] Li, X., Bharadwaj, V., KO, C. C., "Distributed Image Processing on a
Network of Workstations", Int'l J. Computers and Applications, vol. 25,
no. 2, pp. 1-10, 2003.
[10] Blazewicz, J., Drozdowski, M., Markiewicz, M., "Divisible Task
Scheduling: Concept and Verification", Parallel Computing, vol. 25, pp.
87-98, 1990.
[11] Chan, S., Bharadwaj, V., Ghose, D., "Large Matrix-Vector Products on
Distributed Bus Networks with Communication Delays Using the
Divisible Load Paradigm: Performance and Simulation", Math. And
Computers in Simulation, vol. 58, pp.71-92, 2001.
[12] Altilar, D. Paker, Y., "Optimal Scheduling Algorithms for
Communication Constrained Parallel Processing", Proc. Eighth Int'l
Euro-Par Conf. pp. 197-206, 2002.
[13] V.Bharadwaj, D.Ghose, V.Mani, “Multi-installment Load Distribution
in Tree Networks with Delays”. IEEE Transactions on Aerospace and
Electronic Systems 31, 555-567 (1995)
[14] X.Li, V.Bharadwaj, C.C.Ko, “Processing divisible loads on single-level
tree networks with buffer constraints”, IEEE Transactions on Aerospace
and Electronic Systems 36, 1298-1308 (2000)
[15] M. Drozdowski, P. Wolniewicz, “Optimum divisible load scheduling on
heterogeneous stars with limited memory”, European Journal of
Operational Research 172, 545-559 (2006)
[16] Rosenberg, A. L., "Sharing Partitionable Workloads in Heterogeneous
NOWs: Greedier Is not Better", IEEE International Conf. on Cluster
Computing, pp. 124-131, Newport Beach, CA, Oct. 2001.
[17] Beaumont, O., Marchal, L., Rehn, V., Robert Y., "FIFO Scheduling of
Divisible Loads with Return Messages Under the One Port Model",
Proc. Heterogeneous Computing Workshop HCW'06, April 2006.
[18] Ghatpande, A., Nakazato, H., Watanabe, H., Beaumont, O., "Divisible
Load Scheduling with Result Collection on Heterogeneous Systems",
Proc. Heterogeneous Computing Workshop (HCP 2008), April 2008.
[19] Ghatpande, A., Nakazato, H., Beaumont, O., Watanabe, H., "SPORT:
An Algorithm for Divisible Load Scheduling With Result Collection on
Heterogeneous Systems", IEICE Transactions on Communications, vol.
E91-B, no. 8 August 2008.
[20] Ghatpande, A., Nakazato, H., Beaumont, O., Watanabe, H., "Analysis of
Divisible Load Scheduling with Result Collection on Heterogeneous
Systems", IEICE Transactions on Communications, vol. E91-B, no. 7,
July 2008.
[21] Suresh, S., Mani,V., Omkar, S. N., Kim, H. J., "Divisible Load
Scheduling in Distributed Systems with Buffer Constraints: Genetic
Algorithm and Linear Programming Approach", International Journal of
Parallel, Emergent and Distributed Systems, Vol. 21, No. 5, pp. 303-321, Oct. 2006.
[22] Vanderbei, R. J., Linear Programming: Foundations and Extensions, 2nd
Ed., International Series in Operations Research & Management, vol.
37, Kluwer Academic Publishers, 2001.
[23] S.Mohammadi, F.Norouzi Fard, F.Norouzi Fard. “Branch & bound: An
Algorithm for Divisible Load Scheduling with Result Collection on
Heterogeneous Systems”, international conference on computer science
and information engineering (ICCSE 2011), pp. 2010-3778, Venice,
April 2011

Thank you for copying data from http://www.arastirmax.com