caa a22 4500 445804610 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9360-x doi (NATIONALLICENCE)springer-10.1007/s00453-009-9360-x On Centralized Smooth Scheduling [Elektronische Daten] [Ami Litman, Shiri Moran-Schein] 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. Springer Science+Business Media, LLC, 2009 Litman Ami Department of Computer Science, Technion, 32000, Haifa, Israel aut Moran-Schein Shiri IBM Haifa Research Labs, 31905, Haifa, Israel aut Algorithmica Springer-Verlag 60/2(2011-06-01), 464-480 0178-4617 60:2<464 2011 60 453 https://doi.org/10.1007/s00453-009-9360-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9360-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Litman Ami Department of Computer Science, Technion, 32000, Haifa, Israel aut NATIONALLICENCE 700 1- Moran-Schein Shiri IBM Haifa Research Labs, 31905, Haifa, Israel aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 464-480 0178-4617 60:2<464 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer