File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: General schedulers for the pinwheel problem based on double-integer reduction

TitleGeneral schedulers for the pinwheel problem based on double-integer reduction
Authors
KeywordsDensity thresholds
pinwheel
real-time
satellite communication
scheduling
Issue Date1992
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tc
Citation
Ieee Transactions On Computers, 1992, v. 41 n. 6, p. 755-768 How to Cite?
AbstractThe pinwheel is a hard-real-time scheduling problem for scheduling satellite ground stations to service a number of satellites without data loss. Given a multiset of positive integers (instance) A = {a1, ... an}, the problem is to find an infinite sequence (schedule) of symbols from {1,2, ... n} such that there is at least one symbol i within any interval of ai symbols (slots). Not all instances A can be scheduled; for example, no 'successful' schedule exists for instances whose density is larger than 1. It has been shown that any instance whose density is less than 2/3 can always be scheduled. Two new schedulers are proposed which improve this 2/3 result to a new 0.7 density threshold. These two schedulers can be viewed as a generalization of the previously known schedulers, i.e., they can handle a larger class of pinwheel instances including all instances schedulable by the previously known techniques.
Persistent Identifierhttp://hdl.handle.net/10722/152234
ISSN
2023 Impact Factor: 3.6
2023 SCImago Journal Rankings: 1.307
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChan, Mee Yeeen_US
dc.contributor.authorChin, Francis YLen_US
dc.date.accessioned2012-06-26T06:36:39Z-
dc.date.available2012-06-26T06:36:39Z-
dc.date.issued1992en_US
dc.identifier.citationIeee Transactions On Computers, 1992, v. 41 n. 6, p. 755-768en_US
dc.identifier.issn0018-9340en_US
dc.identifier.urihttp://hdl.handle.net/10722/152234-
dc.description.abstractThe pinwheel is a hard-real-time scheduling problem for scheduling satellite ground stations to service a number of satellites without data loss. Given a multiset of positive integers (instance) A = {a1, ... an}, the problem is to find an infinite sequence (schedule) of symbols from {1,2, ... n} such that there is at least one symbol i within any interval of ai symbols (slots). Not all instances A can be scheduled; for example, no 'successful' schedule exists for instances whose density is larger than 1. It has been shown that any instance whose density is less than 2/3 can always be scheduled. Two new schedulers are proposed which improve this 2/3 result to a new 0.7 density threshold. These two schedulers can be viewed as a generalization of the previously known schedulers, i.e., they can handle a larger class of pinwheel instances including all instances schedulable by the previously known techniques.en_US
dc.languageengen_US
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tcen_US
dc.relation.ispartofIEEE Transactions on Computersen_US
dc.subjectDensity thresholds-
dc.subjectpinwheel-
dc.subjectreal-time-
dc.subjectsatellite communication-
dc.subjectscheduling-
dc.titleGeneral schedulers for the pinwheel problem based on double-integer reductionen_US
dc.typeArticleen_US
dc.identifier.emailChin, Francis YL:chin@cs.hku.hken_US
dc.identifier.authorityChin, Francis YL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/12.144627en_US
dc.identifier.scopuseid_2-s2.0-0026882102en_US
dc.identifier.volume41en_US
dc.identifier.issue6en_US
dc.identifier.spage755en_US
dc.identifier.epage768en_US
dc.identifier.isiWOS:A1992JD83000010-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChan, Mee Yee=7402597863en_US
dc.identifier.scopusauthoridChin, Francis YL=7005101915en_US
dc.identifier.issnl0018-9340-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats