Open Access Open Access  Restricted Access Subscription or Fee Access

Compile-Time Task Scheduling in Computer Networks Using Non-Preemptive Processing and Time Quantum

(*) Corresponding author

Authors' affiliations



Efficient parallel processing can be obtained with powerful scheduling algorithms. An efficient and reliable scheduling algorithm is proposed. The algorithm is called Time Quantum Task Scheduling (TQTS). In TQTS the processing Maskespan is divided into non-overlapping cycles. Each cycle is defined by specific time quantum. The tasks can be assigned to any of the available processors in specific cycle. This approach obtains more organized task scheduling compared to previous approaches. In addition, free time slots can be used by other applications running on the same parallel system. Results showed that the idle time of each processor is reduced and the algorithm is more powerful and efficient than other related approaches.
Copyright © 2015 Praise Worthy Prize - All rights reserved.


Parallel Algorithms; Task Scheduling; Precedence Graph; Task Graphs; Static Scheduling

Full Text:



Hsu, T.S., Lee, J., Lopez, D.R., and Royce, W., “Task Allocation on a Network of Processors,” IEEE Transaction on Computers, Vol. 49, No. 12, pp. 1339-1353, December 2000.

Dertouzos, M.L., and Mok, A.K., "Multiprocessor on-line scheduling of hard-real-time tasks", IEEE Trans. on Software Engineering, 15 (12) (1989) 1497-1506.

Sarkar, V., Partitioning and Scheduling Parallel Programs for Multiprocessors, The M.I.T Press, Cambridge, MA, 1989.

Hamid Arabnejad and Jorge G. Barbosa, “List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table” IEEE Transactions on Parallel and Distributed Systems, Vol. 25, No.3, March 2014

H. Topcuoglu, S. Hariri, and M. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, Mar. 2002.

Yuming Xu, Kenli Li, Tung Truong Khac, Meikang Qiu, “A Multiple Priority Queueing Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems”, IEEE 14th International Conference on High Performance Computing and Communications, pp. 639-646, 2012

Fatos Xhafa, Javier Carretero, “A Tabu Search Algorithm For Scheduling Independent Jobs In Computational Grids” Computing and Informatics, Vol. 28, 2009, 1001–1014, 2009

Wei-Neng Chen, “An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Various QoS Requirements”, IEEE transactions on system, man and cybernetics, part C: applications and reviews, Vol. 39, NO. 1, pp. 29-43, 2009.

C. Boeres, J.V. Filho, and V.E.F. Rebello, “A Cluster-Based Strategy for Scheduling Task on Heterogeneous Processors,” Proc. 16th Symp. Computer Architecture and High Performance Computing, pp. 214-221, 2004.

B. Cirou and E. Jeannot, “Triplet: A Clustering Scheduling Algorithm for Heterogeneous Systems,” Proc. Int’l Conf. Parallel Processing Workshops, pp. 231-236, 2001.

T. Hagras and J. Jane_cek, “A Simple Scheduling Heuristic for Heterogeneous Computing Environments,” Proc. Second Int’l Symp. Parallel and Distributed Computing, pp. 104-110, 2003.

Krishnamoorthy, V., and Efe, K., "Task scheduling with and without communication delays: A unified approach", European Journal of Operational Research, 89 (1996) 366-379.


  • There are currently no refbacks.

Please send any question about this web site to
Copyright © 2005-2023 Praise Worthy Prize