Dynamic windows scheduling with reallocation

Martín Farach-Colton, Katia Leal, Miguel A. Mosteiro, Christopher Thraves

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 that allow at most one transmission per time slot, to clients specified by a maximum delay between consecutive transmissions. We extend previous online models, where decisions are permanent, assuming that clients may be reallocated at some cost. We present three online reallocation algorithms for Windows Scheduling. We analyze one of them and we evaluate experimentally all three showing that, in practice, they achieve constant amortized reallocations with close to optimal channel usage. Our simulations also expose interesting trade-offs between reallocations and channel usage. To the best of our knowledge, this is the first study of Windows Scheduling with reallocation costs.

Original languageEnglish (US)
Title of host publicationExperimental Algorithms - 13th International Symposium, SEA 2014, Proceedings
PublisherSpringer Verlag
Pages99-110
Number of pages12
ISBN (Print)9783319079585
DOIs
StatePublished - 2014
Event13th International Symposium on Experimental Algorithms, SEA 2014 - Copenhagen, Denmark
Duration: Jun 29 2014Jul 1 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8504 LNCS

Other

Other13th International Symposium on Experimental Algorithms, SEA 2014
Country/TerritoryDenmark
CityCopenhagen
Period6/29/147/1/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Radio Networks
  • Reallocation Algorithms
  • Unit Fractions Bin Packing
  • Windows Scheduling

Fingerprint

Dive into the research topics of 'Dynamic windows scheduling with reallocation'. Together they form a unique fingerprint.

Cite this