Scheduling of Independent Jobs in Star Graph networks

Document Type

Article

Publication Date

9-1996

Publication Title

Computers & Mathematics with Applications

Volume

32

Issue

6

First page number:

45

Last page number:

55

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.

Keywords

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

Disciplines

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

Language

English

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.

UNLV article access

Search your library

Share

COinS