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

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.

• Supriya Arya
• Sunita Dhingra

• Multiprocessor task scheduling Problem
• Makespan
• Duplication Scheduling Heuristic
• Simulated Annealing
• Hybrid Approach.

[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.