Scheduling of independent jobs in star graph networks

Document Type



In this paper, we investigate the problem of how to schedule n independent jobs on an m-dimensional star graph based network. We develop a feasibility algorithm for preemptively scheduling a given set of jobs with dimension and time requirements on a star graph network of given size with a given deadline. We show that the algorithm runs in O(n log n) time where n is the number of jobs. We also develop a simple heuristic for nonpreemptive scheduling of jobs and study its lower and upper bounds.


Cayley graphs; Computer algorithms; Computer network resources; Computer networks; Routing (Computer network management); Scheduling--Computer programs


Electrical and Computer Engineering | Engineering | Signal Processing | Systems and Communications


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library