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

    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
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

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

    Keywords

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

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

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

    Cite this