IDEAS home Printed from https://ideas.repec.org/p/ehl/lserod/114914.html
   My bibliography  Save this paper

Online load balancing with general reassignment cost

Author

Listed:
  • Berndt, Sebastian
  • Eberle, Franziska
  • Megow, Nicole

Abstract

We investigate a semi-online variant of load balancing with restricted assignment. In this problem, we are given n jobs, which need to be processed by m machines with the goal to minimize the maximum machine load. Since strong lower bounds rule out any competitive ratio of o(log⁡n), we may reassign jobs at a certain job-individual cost. We generalize a result by Gupta, Kumar, and Stein (SODA 2014) by giving a O(log⁡log⁡mn)-competitive algorithm with constant amortized reassignment cost.

Suggested Citation

  • Berndt, Sebastian & Eberle, Franziska & Megow, Nicole, 2022. "Online load balancing with general reassignment cost," LSE Research Online Documents on Economics 114914, London School of Economics and Political Science, LSE Library.
    • Handle: RePEc:ehl:lserod:114914
    as

    Download full text from publisher

    File URL: http://eprints.lse.ac.uk/114914/
    File Function: Open access version.
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Peter Sanders & Naveen Sivadasan & Martin Skutella, 2009. "Online Scheduling with Bounded Migration," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 481-498, May.
    2. Spyros Angelopoulos & Christoph Dürr & Shendan Jin, 2020. "Online maximum matching with recourse," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 974-1007, November.
    3. Martin Skutella & José Verschae, 2016. "Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 991-1021, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Islam Akaria & Leah Epstein, 2023. "Bin stretching with migration on two hierarchical machines," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 98(1), pages 111-153, August.
    2. Letsios, Dimitrios & Mistry, Miten & Misener, Ruth, 2021. "Exact lexicographic scheduling and approximate rescheduling," European Journal of Operational Research, Elsevier, vol. 290(2), pages 469-478.
    3. Islam Akaria & Leah Epstein, 2022. "Online scheduling with migration on two hierarchical machines," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3535-3548, December.
    4. Leah Epstein, 2023. "Parallel solutions for preemptive makespan scheduling on two identical machines," Journal of Scheduling, Springer, vol. 26(1), pages 61-76, February.
    5. Nasini, Stefano & Nessah, Rabia, 2022. "A multi-machine scheduling solution for homogeneous processing: Asymptotic approximation and applications," International Journal of Production Economics, Elsevier, vol. 251(C).
    6. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    7. Dimitrios Letsios & Jeremy T. Bradley & Suraj G & Ruth Misener & Natasha Page, 2021. "Approximate and robust bounded job start scheduling for Royal Mail delivery offices," Journal of Scheduling, Springer, vol. 24(2), pages 237-258, April.
    8. Martin Skutella & José Verschae, 2016. "Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 991-1021, August.
    9. Leah Epstein, 2018. "A survey on makespan minimization in semi-online environments," Journal of Scheduling, Springer, vol. 21(3), pages 269-284, June.

    More about this item

    Keywords

    competitive analysis; migration; online load balancing; recourse;
    All these keywords.

    JEL classification:

    • R14 - Urban, Rural, Regional, Real Estate, and Transportation Economics - - General Regional Economics - - - Land Use Patterns
    • J01 - Labor and Demographic Economics - - General - - - Labor Economics: General

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ehl:lserod:114914. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: LSERO Manager (email available below). General contact details of provider: https://edirc.repec.org/data/lsepsuk.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.