About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica (New York)
Paper
On centralized smooth scheduling
Abstract
This paper studies evenly distributed sets of natural numbers and their applications to scheduling in a centralized environment. Such sets, called smooth sets, have the property that their quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation; namely, for ρ,Δ a set A of natural numbers is (ρ,Δ)-smooth if abs(|I|·ρ-|I∩A|)<Δ for any interval I. The paper studies scheduling persistent clients on a single slot-oriented resource in a flexible and predictable manner. Each client γ has a given rate ρ γ that defines the share of the resource he is entitled to receive and the goal is a smooth schedule in which, for some predefined Δ, each client γ is served in a (ρ γ,Δ)-smooth set of slots (natural numbers). The paper considers a centralized environment where a single algorithm computes the user of the current slot. It constructs a smooth schedule with a very efficient algorithm that computes the user of each slot in O(log∈log∈q) time and O(n) space, where n is the number of clients and q max∈{ρ γ /ρ γ′ | γ,γ′ Γ}; in many practical applications this O(log∈log∈q) value is actually a small constant. Our scheduling technique is based on a reduction from allocation of slots to allocation of sub-intervals of the unit interval. This technique naturally extends to the problem of scheduling multiple resources, even under the restriction that a client can be served concurrently by at most one resource. This paper constructs such a schedule in which the users of each slot are computed very fast-in O(mlog∈log∈q) time per slot and O(n) space where m is the number of resources; this result is a significant improvement on the prior fastest algorithm that produces such a schedule (actually of a special type-a P-fair schedule) in O(mlog∈n) time per slot and O(n) space. Moreover, the paper introduces a novel approach to multi-resource scheduling in which each resource independently computes, slot after slot, what client to serve in this slot. Under this approach the paper constructs a smooth schedule which is computed in O(n) space and O(log∈log∈q) time per slot. © 2009 Springer Science+Business Media, LLC.