Title

Scheduling of independent jobs in star graph networks

Document Type

Article

Abstract

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.

Disciplines

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

Permissions

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.