Analysis of Heuristic Based Hybrid Simulated Annealing Algorithm for Multiprocessor Task Scheduling

Authors: Supriya Arya, Sunita Dhingra

Abstract:

Multiprocessor task scheduling problem for dependent and independent tasks is computationally complex problem. Many methods are proposed to achieve optimal running time. As the multiprocessor task scheduling is NP hard in nature, therefore, many heuristics are proposed which have improved the makespan of the problem. But due to problem specific nature, the heuristic method which provide best results for one problem, might not provide good results for another problem. So, Simulated Annealing which is meta heuristic approach is considered. It can be applied on all types of problems. However, due to many runs, meta heuristic approach takes large computation time. Hence, the hybrid approach is proposed by combining the Duplication Scheduling Heuristic and Simulated Annealing (SA) and the makespan results of Simple Simulated Annealing and Hybrid approach are analyzed.

Keywords: Multiprocessor task scheduling Problem, Makespan, Duplication Scheduling Heuristic, Simulated Annealing, Hybrid Approach.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1110229

References:

[1] M. Garey and D. Johnson, “Computers and Intractability, A Guide to the Theory of NP Completeness”, W.H. Freeman and Co., 1979.
[2] Yu-Kwong and Ishfaq Ahmad, “Static Scheduling Algorithms for allocating directed task graphs to multiprocessors”, ACM Computing Surveys, Vol.31, No. 4, December 1999, pp. 407-427.
[3] Kruatrachue, B. And Lewis, T.G., “Grain size determination for parallel processing”, IEEE software 5,1988, pp.23-32.
[4] Kirkpatrick S, Gelatt CD, Vecchi M.P., “Optimization by simulated annealing, Science”, Vol.220, 1983, pp. 671–680.
[5] Sunita Dhingra, Satinder Bal Gupta and Ranjit Biswas, “Hybrid GASA for bi-criteria multiprocessor task scheduling with precedence constraints”, Computer Applications: An International Journal, Vol.1, No.1, August 2014, pp. 11-21.
[6] Wie-Ming Lin and Qiuyan Gu, “An Efficient Clustering-Based Task Scheduling Algorithm for Parallel Programs with Task Duplication”, Journal of Information Science and Engineering 23, 2007, pp. 589-604.
[7] Davis, EW., and Patterson, J. H., “A comparison of heuristic and optimum solutions in resource-constrained project scheduling”, Management Science, 21,1975,pp. 718- 722.
[8] Davis, EW., “Project Network Summary Measures and Constrained Resource Scheduling”, lIE Transactions, 7, 1975, pp. 132-142.
[9] Yogendra Kumar Soni and Rajesh Bhatt, “Simulated Annealing optimized PID Controller design using ISE, IAE, IATE and MSE error criteria”, International Journal of Advanced Research in Computer Engineering & Technology (IJARCET) Vol. 2, Issue 7, 2013, pp. 2337- 2340.
[10] Suchismita Pattanaik, Subhendu Prakash Bhoi, Rakesh Mohanty, “Simulated Annealing Based Placement Algorithms and research challenges: a survey”, Journal of Global Search in computer Science, Vol. 3, No. 6, 2012, pp. 33-37.
[11] Younes, N., Santo, D.L., Maria, A., “A Simulated Annealing approach to scheduling in a flow shop with multiple processors”, Industrial Engineering Research Conference Proceedings, Banff, Canada,1998.
[12] Hooda N, Dhingra A. K, “Flow Shop Scheduling using Simulated Annealing: A review”, International Journal of Applied Engineering Research, Dindigul, Vol. 2, No.1, 2011, pp.234-249.
[13] Laha, D., Chakraborty, U.K., “An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling”, International Journal of Advance Manufacturing Technology, 2008, pp.559-569.
[14] Nawaz, M., Enscore, E., Ham, I., “A heuristic for the m-machine n-job flow shop sequencing problem”, Omega, 11, 1983, pp. 91–95.
[15] Bonyadi, M. R. and Moghaddam, M. E., “A bipartite genetic algorithm for multi-processor task scheduling”, International Journal of Parallel Programming, Vol. 37, No. 5, 2009, pp. 462- 487.