Dynamic windows scheduling with reallocation

DOI10.1145/3462208MaRDI QIDQ5102055zbMATH OpenOpenAlexFDO

Authors Martin Farach-Colton, Katia Leal, Miguel A. Mosteiro, Christopher Thraves Caro

Publication date 6 September 2022

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.1087

zbMATH Keywords

radio networksreallocation algorithmsunit fractions bin packingwindows scheduling

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Abstract: We consider the Windows Scheduling problem. The problem is a restricted version of Unit-Fractions Bin Packing, and it is also called Inventory Replenishment in the context of Supply Chain. In brief, the problem is to schedule the use of communication channels to clients. Each client ci is characterized by an active cycle and a window wi. During the period of time that any given client ci is active, there must be at least one transmission from ci scheduled in any wi consecutive time slots, but at most one transmission can be carried out in each channel per time slot. The goal is to minimize the number of channels used. We extend previous online models, where decisions are permanent, assuming that clients may be reallocated at some cost. We assume that such cost is a constant amount paid per reallocation. That is, we aim to minimize also the number of reallocations. We present three online reallocation algorithms for Windows Scheduling. We evaluate experimentally these protocols showing that, in practice, all three achieve constant amortized reallocations with close to optimal channel usage. Our simulations also expose interesting trade-offs between reallocations and channel usage. We introduce a new objective function for WS with reallocations, that can be also applied to models where reallocations are not possible. We analyze this metric for one of the algorithms which, to the best of our knowledge, is the first online WS protocol with theoretical guarantees that applies to scenarios where clients may leave and the analysis is against current load rather than peak load. Using previous results, we also observe bounds on channel usage for one of the algorithms.

Recommendations

• Reallocation problems in scheduling
• Algorithms and Computation
• Windows scheduling as a restricted version of bin packing
• Windows Scheduling Problems for Broadcast Systems
• scientific article; zbMATH DE number 2119694

Cites work

• A general buffer scheme for the windows scheduling problem
• Algorithms and Computation
• Dynamic bin packing of unit fractions items
• Dynamic bin packing with unit fraction items revisited
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• Load Balancing for Response Time
• Minimizing makespan and preemption costs on a system of uniform machines
• Minimizing Service and Operation Costs of Periodic Scheduling
• Minimizing total completion time subject to job release dates and preemption penalties
• On-line bin packing with restricted repacking
• Online inventory replenishment scheduling of temporary orders
• Online scheduling with bounded migration
• Reallocation problems in scheduling
• Semi-on-line bin packing: a short overview and a new lower bound
• Windows scheduling as a restricted version of bin packing
• Windows Scheduling Problems for Broadcast Systems

Cited in

(4)

• scientific article; zbMATH DE number 2088452 (Why is no real title available?)
• Windows scheduling as a restricted version of bin packing
• Station assignment with reallocation
• Contention resolution with message deadlines

This page was built for publication: Dynamic windows scheduling with reallocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5102055)