research-article

Cost-Oblivious Reallocation for Scheduling and Planning

Authors:

Michael A. Bender,

Martín Farach-Colton,

Sándor P. Fekete,

Jeremy T. Fineman,

Seth GilbertAuthors Info & Claims

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

Pages 143 - 154

https://doi.org/10.1145/2755573.2755589

Published: 13 June 2015 Publication History

Abstract

In a reallocating-scheduler problem, jobs may be inserted and deleted from the system over time. Unlike in traditional online scheduling problems, where a job's placement is immutable, in reallocation problems the schedule may be adjusted, but at some cost. The goal is to maintain an approximately optimal schedule while also minimizing the reallocation cost for changing the schedule.

This paper gives a reallocating scheduler for the problem of assigning jobs to p (identical) servers so as to minimize the sum of completion times to within a constant factor of optimal, with an amortized reallocation cost for a length-w job of O(f(w)log³logΔ), where Delta is the length of the longest job and f() is the reallocation-cost function. Our algorithm is cost oblivious, meaning that the algorithm is not parameterized by f(), yet it achieves this bound for any subadditive f(). Whenever f() is strongly subadditive, the reallocation cost becomes O(f(w)).

To realize a reallocating scheduler with low reallocation cost, we design a k-cursor sparse table. This data structure stores a dynamic set of elements in an array, with insertions and deletions restricted to k cursors in the structure. The data structure achieves an amortized cost of O(log³ k) for insertions and deletions, while also guaranteeing that any prefix of the array has constant density. Observe that this bound does not depend on n, the number of elements, and hence this data structure, restricted to k<<n cursors, beats the lower bound of Ω(log² n) for general sparse tables.

References

[1]

M. Andrews, M. X. Goemans, and L. Zhang. Improved bounds for on-line load balancing. Algorithmica, 23(4):278--301, 1999.

[2]

C. Archetti, L. Bertazzi, and M. G. Speranza. Reoptimizing the Traveling Salesman Problem. Networks, 42(3):154--159, 2003.

[3]

C. Archetti, L. Bertazzi, and M. G. Speranza. Reoptimizing the 0-1 knapsack problem. Disc. Appl. Math., 158(17):1879--1887, Oct. 2010.

Digital Library

[4]

G. Ausiello, V. Bonifaci, and B. Escoffier. Complexity and approximation in reoptimization. In S. B. Cooper and A. Sorbi, editors, Computability in Context: Computation and Logic in the Real World, pages 101--129. World Scientific, 2011.

[5]

G. Ausiello, B. Escoffier, J. Monnot, and V. T. Paschos. Reoptimization of minimum and maximum traveling salesman's tours. J. Disc. Alg., 7(4):453--463, 2009.

Digital Library

[6]

G. Baram and T. Tamir. Reoptimization of the minimum total flow-time scheduling problem. In G. Even and D. Rawitz, editors, Proc. MedAlg, volume 7659 of LLNCS, pages 52--66, 2012.

Digital Library

[7]

M. A. Bender, M. Farach-Colton, S. P. Fekete, J. T. Fineman, and S. Gilbert. Reallocation problems in scheduling. In Proc. SPAA, pages 271--279, 2013.

Digital Library

[8]

M. A. Bender, M. Farach-Colton, S. P. Fekete, J. T. Fineman, and S. Gilbert. Cost-oblivious storage reallocation. In Proc. PODS, pages 278--288, 2014.

Digital Library

[9]

M. A. Bender and H. Hu. An adaptive packed-memory array. Trans. Datab. Syst., 32(4), 2007.

Digital Library

[10]

H.-J. Böckenhauer, L. Forlizzi, J. Hromkovic, J. Kneis, J. Kupke, G. Proietti, and P. Widmayer. Reusing optimal TSP solutions for locally modified input instances. In Proc. TCS, pages 251--270, 2006.

[11]

J. Bulánek, M. Koucky, and M. Saks. Tight lower bounds for the online labeling problem. In Proc. STOC, pages 1185--1198, 2012.

Digital Library

[12]

A. Caprara, L. Galli, L. Kroon, G. Maróti, and P. Toth. Robust train routing and online re-scheduling. In Proc. ATMOS, pages 24--33, 2010.

[13]

V. Chiraphadhanakul and C. Barnhart. Robust ight schedules through slack re-allocation. EURO Journal on Transportation and Logistics, 2(4):277--306, 2013.

[14]

S. Davis, J. Edmonds, and R. Impagliazzo. Online algorithms to minimize resource reallocations and network communication. In Proc. APPROX-RANDOM, pages 104--115, 2006.

Digital Library

[15]

L. Epstein and A. Levin. A robust APTAS for the classical bin packing problem. In Proc. ICALP, pages 214--225, 2006.

Digital Library

[16]

L. Epstein and A. Levin. Robust algorithms for preemptive scheduling. In Proc. ESA, pages 567--578, 2011.

Digital Library

[17]

S. P. Fekete, T. Kamphans, N. Schweer, C. Tessars, J. C. van der Veen, J. Angermeier, D. Koch, and J. Teich. Dynamic defragmentation of recon_gurable devices. ACM Trans. Reconf. Technol. Syst., 5(2):8:1--8:20, June 2012.

Digital Library

[18]

R. Graham, E. Lawler, J. Lenstra, and A. Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Disc. Math., 5:287--326, 1979.

[19]

N. G. Hall and C. N. Potts. Rescheduling for new orders. Op. Res., 52(3), 2004.

Digital Library

[20]

A. Itai and I. Katriel. Canonical density control. IPL, 104(6):200--204, 2007.

Digital Library

[21]

A. Itai, A. G. Konheim, and M. Rodeh. A sparse table implementation of priority queues. In Proc. ICALP, pages 417--431, 1981.

Digital Library

[22]

H. Jiang and C. Barnhart. Dynamic airline scheduling. Transp. Sc., 43(3):336--354, 2009.

Digital Library

[23]

D. Karger, C. Stein, and J. Wein. Scheduling Algorithms. CRC Press, 1998.

[24]

I. Katriel. Implicit data structures based on local reorganizations. Master's thesis, Technion, May 2002.

[25]

P. Kouvelis and G. Yu. Robust Discrete Optimization and Its Applications. Kluwer, 1997.

[26]

S. Lan, J.-P. Clarke, and C. Barnhart. Planning for robust airline operations: Optimizing aircraft routings and ight departure times to minimize passenger disruptions. Transp. Sc., 40(1):15--28, 2006.

Digital Library

[27]

J. M. Mulvey, R. J. Vanderbei, and S. A. Zenios. Robust optimization of large-scale systems. Op. Res., 43(2), 1995.

Digital Library

[28]

P. Sanders, N. Sivadasan, and M. Skutella. Online scheduling with bounded migration. Math. Oper. Res., 34(2):481--498, 2009.

Digital Library

[29]

H. Shachnai, G. Tamir, and T. Tamir. A theory and algorithms for combinatorial reoptimization. In Proc. LATIN, pages 618--630, 2012.

Digital Library

[30]

M. Skutella and J. Verschae. A robust PTAS for machine covering and packing. In Proc. ESA, pages 36--47, 2010.

Digital Library

[31]

C. A. Tovey. Rescheduling to minimize makespan on a changing number of identical processors. Nav. Res. Logist., 33:717--724, 1986.

[32]

A. T. Unal, R. Uzsoy, and A. S. Kiran. Rescheduling on a single machine with part-type dependent setup times and deadlines. Ann. Op. Res., 70, 1997.

[33]

J. C. Verschae. The Power of Recourse in Online Optimization Robust Solutions for Scheduling, Matroid and MST Problems. PhD thesis, TU Berlin, June 2012.

[34]

J. Westbrook. Load balancing for response time. J. of Alg., 35(1):1--16, 2000.

Digital Library

[35]

D. Willard. Maintaining dense sequential files in a dynamic environment (extended abstract). In Proc. STOC, pages 114--121, 1982.

Digital Library

[36]

D. E. Willard. Good worst-case algorithms for inserting and deleting records in dense sequential files. In Proc. SIGMOD, pages 251--260, 1986.

Digital Library

[37]

D. E. Willard. A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. I&C, 97(2):150--204, 1992.

Digital Library

Cited By

Farach-Colton MKuszmaul WSheffield NWestover AAgrawal KPetrank E(2024)A Nearly Quadratic Improvement for Memory ReallocationProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659965(125-135)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659965
Bender MFarach-Colton MFekete SFineman JGilbert S(2017)Cost-Oblivious Storage ReallocationACM Transactions on Algorithms10.1145/307069313:3(1-20)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3070693

Index Terms

Cost-Oblivious Reallocation for Scheduling and Planning
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Cost-Oblivious Storage Reallocation

Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot ...
Reallocation Problems in Scheduling

In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be ...
Reallocation problems in scheduling
SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures

In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

June 2015

362 pages

ISBN:9781450335881

DOI:10.1145/2755573

General Chair:
Guy Blelloch
Carnegie Mellon University, USA
,
Program Chair:
Kunal Agrawal
Washington University in St. Louis, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SPAA '15

Sponsor:

SPAA '15: 27th ACM Symposium on Parallelism in Algorithms and Architectures

June 13 - 15, 2015

Oregon, Portland, USA

Acceptance Rates

SPAA '15 Paper Acceptance Rate 31 of 131 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
190
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Farach-Colton MKuszmaul WSheffield NWestover AAgrawal KPetrank E(2024)A Nearly Quadratic Improvement for Memory ReallocationProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659965(125-135)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659965
Bender MFarach-Colton MFekete SFineman JGilbert S(2017)Cost-Oblivious Storage ReallocationACM Transactions on Algorithms10.1145/307069313:3(1-20)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3070693

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents