TY - GEN
T1 - Dynamic windows scheduling with reallocation
AU - Farach-Colton, Martín
AU - Leal, Katia
AU - Mosteiro, Miguel A.
AU - Thraves, Christopher
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - Radio Networks
KW - Reallocation Algorithms
KW - Unit Fractions Bin Packing
KW - Windows Scheduling
UR - http://www.scopus.com/inward/record.url?scp=84903709338&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84903709338&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-07959-2_9
DO - 10.1007/978-3-319-07959-2_9
M3 - Conference contribution
AN - SCOPUS:84903709338
SN - 9783319079585
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 99
EP - 110
BT - Experimental Algorithms - 13th International Symposium, SEA 2014, Proceedings
PB - Springer Verlag
T2 - 13th International Symposium on Experimental Algorithms, SEA 2014
Y2 - 29 June 2014 through 1 July 2014
ER -