CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

A Novel Approach for Task Scheduling in Multiprocessor System

by Ranjit Rajak
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 44 - Number 11
Year of Publication: 2012
Authors: Ranjit Rajak
10.5120/6306-8627

Ranjit Rajak . A Novel Approach for Task Scheduling in Multiprocessor System. International Journal of Computer Applications. 44, 11 ( April 2012), 12-16. DOI=10.5120/6306-8627

@article{ 10.5120/6306-8627,
author = { Ranjit Rajak },
title = { A Novel Approach for Task Scheduling in Multiprocessor System },
journal = { International Journal of Computer Applications },
issue_date = { April 2012 },
volume = { 44 },
number = { 11 },
month = { April },
year = { 2012 },
issn = { 0975-8887 },
pages = { 12-16 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume44/number11/6306-8627/ },
doi = { 10.5120/6306-8627 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:35:15.288959+05:30
%A Ranjit Rajak
%T A Novel Approach for Task Scheduling in Multiprocessor System
%J International Journal of Computer Applications
%@ 0975-8887
%V 44
%N 11
%P 12-16
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In multiprocessor system, scheduling of tasks to assigned on the number of processors. The major objective of task scheduling is to find minimum execution time of a program. It is well known that the complexity of a general scheduling problem is NP-Complete [9], there are number of heuristic have been developed. Each of which may either find optimal or near optimal scheduling under the different conditions. The task scheduling is represented by a directed acyclic graph (DAG). In this paper, we present a new scheduling algorithm which is called Task Scheduling based on Breath First Search(TSB). The TSB is queue based approach to schedule parallel tasks on the homogenous parallel multiprocessor system. Its performance is evaluated in comparison with Highest Level First with Estimate Time (HLFET) algorithm, Modified Critical Path (MCP) algorithm, Earliest Time First (ETF) algorithm and Dynamic Level Scheduling (DLS) algorithm in terms of Speedup, Efficiency, Load Balance and Normalized Scheduling Length (NSL).

References
  1. M. R. Gary and D. S. Johnson, "Computer and Intractability: A Guide to the theory of NP Completeness ", San Francisco . CA, W. H freeman, 1989.
  2. Ullman, J,"NP-Complete Scheduling Problem", Journal of Computer System Science, 10,pp384-393,1975.
  3. Jagbir Singh ," Improved Task Scheduling on Parallel System using Genetic Algorithm" International Journal of Computer Applications (0975 – 8887) Volume 39– No. 17, February 2012.
  4. Yashwant Kanetkar ," Data Structure Using C",BPB Publicatins 2003.
  5. M. J. Quinn,"Parallel Programming in C with MPI and OpenMP",Tata McGraw-Hill, Edition 2003.
  6. KwangSik Shin,MyongJin Cha, MunSuck Jang,"Task Scheduling Algorithm using Minimized Duplication in Homogeneous Systems", Journal of Parallel and Distributed Computing ,Vol. 68,pp. 1146-1156,2008.
  7. Fatma A. Omara, Mona M. Arafa,"Genetic Algorithm for Task scheduling Problem",Journal of Parallel and Distributed Computing Vol. 70,13-22,2010
  8. Yu-Kwong Kwok and Ishfaq Ahmad," Static Scheduling Algorithms for Allocating Directed Task Graphs to Mulitprocessors", ACM Conputing Surveys, Vol. 31 N0. 4, December 1999.
  9. H. El-Rewini,T. G. Lewis and H. H. Ali,"Task Scheduling in Parallel and Distributed System" Prentice Hall 1994.
  10. S. R. Vijaylakshmi and G. Padmavarth," International Journal of Computer Science and Security",Vol. 7,pp125- 132,2009.
  11. L. Adam,K. M. Candy and J. Dickson, "A Comparison of list scheduling for parallel processing system", Communication ACM 17, No. 12 , pp 685-690,1974.
  12. Amir Masoud Rahman and Mohammad Ali Vahedi," A Noval Task Scheduling in Multiprocessors System with Genetic Algorithm by Using Elistism Stepping Method", Science and Research Branch,Tehran, Iran,May 26,2008.
  13. Y-K. Kwok and I. Ahmad, "Dynamic Critical Path Scheduling : An Effective Techniques for Allocating Tasks Graph onto Multiprocessor", IEEE Transaction on Parallel and Distributed System,Vol. 7(5) pages 506-621, May 1996.
  14. M-Y. Wu and D. D. Gajski,"Hyperpool: A programming Aid for Message Passing ", IEEE Transaction on Parallel and Distributed System. Vol 3 ,pp. 330-343,July 1990.
  15. J. J. Hwang. Y. C. Chow,F. D. Anger and C. Y. Lee, "Scheduling precedence graph in systems with interprocessor communication times",SIAM Journal of Computing . 18 No 2,pp244-257, April 1989.
  16. G,C. Sih and E. A. Lee," Compile time scheduling heuristic for interconnection –constrained heterogeneous processor architecture ",IEEE Transaction on Parallel and Distributed System 4. No 2,pp-75-87, Feb. 1993.
Index Terms

Computer Science
Information Sciences

Keywords

Task Scheduling Dag Np-complete Parallel Processing

Powered by PhDFocusTM