Document Type




Embargo Period



Dynamic task scheduling algorithm, Load balancing, Execution time, Settling time




Computer Sciences


A dynamic task scheduling algorithm, that is stable, de-centralized, and adaptive to network topology, is presented. The proposed algorithm is an extension of nearest neighbor load balancing strategy with an enhanced degree of efficiency and it is intended for multicomputers connected by a store and forward communication network. The proposed algorithm is modeled by a central server open queuing network. It is shown that the response time of a task consists of two parts. The first part comprises a task‘s settling time which consists of scheduling time, communication time, and waiting time in scheduling and communication queues. The second part comprises waiting time in the execution queue in the execution time itself. In order to reduce the first response time, the scheduling algorithm needs to be stable, so that a task is quickly settled at some node. On the other hand, the second response time is reduced if the algorithm efficiently migrates the task to a lightly loaded node. The proposed algorithm is comprehensively evaluated, through simulation and analytical model, and is shown to be both stable and efficient. For performance evaluation, the task wander cost and the scheduling overhead is also taken into account. Experimental results are also obtained for another nearest neighbor scheduling scheme and compared with the pro-posed algorithm.

Creative Commons License

This work is licensed under a Creative Commons Attribution 3.0 License.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.