File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Schedulers for larger classes of pinwheel instances

TitleSchedulers for larger classes of pinwheel instances
Authors
KeywordsPinwheel
Real-Time
Satellite Communication
Scheduling
Issue Date1993
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica, 1993, v. 9 n. 5, p. 425-462 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, ρ(A)=∑i i(l/ai), is larger than 1. It has been shown that all instances whose densities are less than a 0.5 density threshold can always be scheduled. If a schedule exists, another concern is the design of a fast on-line scheduler (FOLS) which can generate each symbol of the schedule in constant time. Based on the idea of "integer reduction," two new FOLSs which can schedule different classes of pinwheel instances, are proposed in this paper. One uses "single-integer reduction" and the other uses "double-integer" reduction. They both improve the previous 0.5 result and have density thresholds of 13/20 and2/3, respectively. In particular, if the elements in A are large, the density thresholds will asymptotically approach In 2 and 1/R2, respectively. © 1993 Springer-Verlag New York Inc.
Persistent Identifierhttp://hdl.handle.net/10722/152190
ISSN
2015 Impact Factor: 0.795
2015 SCImago Journal Rankings: 0.898
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChan, MYen_US
dc.contributor.authorChin, Fen_US
dc.date.accessioned2012-06-26T06:36:24Z-
dc.date.available2012-06-26T06:36:24Z-
dc.date.issued1993en_US
dc.identifier.citationAlgorithmica, 1993, v. 9 n. 5, p. 425-462en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152190-
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, ρ(A)=∑i i(l/ai), is larger than 1. It has been shown that all instances whose densities are less than a 0.5 density threshold can always be scheduled. If a schedule exists, another concern is the design of a fast on-line scheduler (FOLS) which can generate each symbol of the schedule in constant time. Based on the idea of "integer reduction," two new FOLSs which can schedule different classes of pinwheel instances, are proposed in this paper. One uses "single-integer reduction" and the other uses "double-integer" reduction. They both improve the previous 0.5 result and have density thresholds of 13/20 and2/3, respectively. In particular, if the elements in A are large, the density thresholds will asymptotically approach In 2 and 1/R2, respectively. © 1993 Springer-Verlag New York Inc.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmicaen_US
dc.subjectPinwheelen_US
dc.subjectReal-Timeen_US
dc.subjectSatellite Communicationen_US
dc.subjectSchedulingen_US
dc.titleSchedulers for larger classes of pinwheel instancesen_US
dc.typeArticleen_US
dc.identifier.emailChin, F:chin@cs.hku.hken_US
dc.identifier.authorityChin, F=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/BF01187034en_US
dc.identifier.scopuseid_2-s2.0-0001244709en_US
dc.identifier.volume9en_US
dc.identifier.issue5en_US
dc.identifier.spage425en_US
dc.identifier.epage462en_US
dc.identifier.isiWOS:A1993KX53200001-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChan, MY=7402597863en_US
dc.identifier.scopusauthoridChin, F=7005101915en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats