IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v21y2018i3d10.1007_s10951-018-0567-z.html
   My bibliography  Save this article

A survey on makespan minimization in semi-online environments

Author

Listed:
  • Leah Epstein

    (University of Haifa)

Abstract

We discuss variants of online scheduling on identical and uniformly related machines, where the objective is to minimize the makespan. All variants are such that some information regarding the input is provided in advance, and therefore these models are known as semi-online problems. Algorithms are analyzed with respect to the competitive ratio. We discuss the benefit arising from different kinds of available information and find that almost all variants allow one to reduce the competitive ratio significantly compared to the best possible competitive ratio for the corresponding pure online problem.

Suggested Citation

  • Leah Epstein, 2018. "A survey on makespan minimization in semi-online environments," Journal of Scheduling, Springer, vol. 21(3), pages 269-284, June.
    • Handle: RePEc:spr:jsched:v:21:y:2018:i:3:d:10.1007_s10951-018-0567-z
    DOI: 10.1007/s10951-018-0567-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-018-0567-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-018-0567-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. György Dósa & M. Grazia Speranza & Zsolt Tuza, 2011. "Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling," Journal of Combinatorial Optimization, Springer, vol. 21(4), pages 458-480, May.
    2. Peter Sanders & Naveen Sivadasan & Martin Skutella, 2009. "Online Scheduling with Bounded Migration," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 481-498, May.
    3. György Dósa & Armin Fügenschuh & Zhiyi Tan & Zsolt Tuza & Krzysztof Węsek, 2018. "Tight upper bounds for semi-online scheduling on two uniform machines with known optimum," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(1), pages 161-180, March.
    4. Sheng-Yi Cai & Qi-Fan Yang, 2011. "Semi-online scheduling on two uniform machines with the known largest size," Journal of Combinatorial Optimization, Springer, vol. 21(4), pages 393-408, May.
    5. Martin Böhm & Jiří Sgall & Rob Stee & Pavel Veselý, 2017. "Online bin stretching with three bins," Journal of Scheduling, Springer, vol. 20(6), pages 601-621, December.
    6. Paul Mireault & James B. Orlin & Rakesh V. Vohra, 1997. "A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines," Operations Research, INFORMS, vol. 45(1), pages 116-125, February.
    7. Qian Cao & Guohua Wan, 2016. "Semi-online scheduling with combined information on two identical machines in parallel," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 686-695, February.
    8. György Dósa & Leah Epstein, 2010. "Online scheduling with a buffer on related machines," Journal of Combinatorial Optimization, Springer, vol. 20(2), pages 161-179, August.
    9. Michaël Gabay & Nadia Brauner & Vladimir Kotov, 2017. "Improved lower bounds for the online bin stretching problem," 4OR, Springer, vol. 15(2), pages 183-199, June.
    10. Yong He & György Dósa, 2007. "Extension of algorithm list scheduling for a semi-online scheduling problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 15(1), pages 97-104, March.
    11. Kangbok Lee & Joseph Leung & Michael Pinedo, 2013. "Makespan minimization in online scheduling with machine eligibility," Annals of Operations Research, Springer, vol. 204(1), pages 189-222, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Feifeng Zheng & Yuhong Chen & Ming Liu & Yinfeng Xu, 2022. "Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1060-1076, September.
    2. Alves de Queiroz, Thiago & Iori, Manuel & Kramer, Arthur & Kuo, Yong-Hong, 2023. "Dynamic scheduling of patients in emergency departments," European Journal of Operational Research, Elsevier, vol. 310(1), pages 100-116.

    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. György Dósa & Armin Fügenschuh & Zhiyi Tan & Zsolt Tuza & Krzysztof Węsek, 2019. "Tight lower bounds for semi-online scheduling on two uniform machines with known optimum," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(4), pages 1107-1130, December.
    3. Feifeng Zheng & Yuhong Chen & Ming Liu & Yinfeng Xu, 2022. "Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1060-1076, September.
    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. Koulamas, Christos & Kyparisis, George J., 2009. "A modified LPT algorithm for the two uniform parallel machine makespan minimization problem," European Journal of Operational Research, Elsevier, vol. 196(1), pages 61-68, July.
    6. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Research on permutation flow shop scheduling problems with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 211(1), pages 473-480, December.
    7. Wang, John & Yan, Ruiliang & Hollister, Kimberly & Zhu, Dan, 2008. "A historic review of management science research in China," Omega, Elsevier, vol. 36(6), pages 919-932, December.
    8. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    9. Qian Cao & Zhaohui Liu, 2010. "Semi-online scheduling with known maximum job size on two uniform machines," Journal of Combinatorial Optimization, Springer, vol. 20(4), pages 369-384, November.
    10. 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.
    11. Liao, Ching-Jong & Lin, Chien-Hung, 2003. "Makespan minimization for two uniform parallel machines," International Journal of Production Economics, Elsevier, vol. 84(2), pages 205-213, May.
    12. Xianglai Qi & Jinjiang Yuan, 2017. "Semi-online hierarchical scheduling for $$l_p$$ l p -norm load balancing with buffer or rearrangements," 4OR, Springer, vol. 15(3), pages 265-276, September.
    13. 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.
    14. Sheng-I Chen & Delvinia Su, 2022. "A multi-stage stochastic programming model of lot-sizing and scheduling problems with machine eligibilities and sequence-dependent setups," Annals of Operations Research, Springer, vol. 311(1), pages 35-50, April.
    15. Xiangzhong Xiang, 2015. "Prompt mechanism for online auctions with multi-unit demands," Journal of Combinatorial Optimization, Springer, vol. 30(2), pages 335-346, August.
    16. Leah Epstein & Hanan Zebedat-Haider, 2014. "Online scheduling with rejection and reordering: exact algorithms for unit size jobs," Journal of Combinatorial Optimization, Springer, vol. 28(4), pages 875-892, November.
    17. Alan J. Soper & Vitaly A. Strusevich, 2021. "Parametric analysis of the quality of single preemption schedules on three uniform parallel machines," Annals of Operations Research, Springer, vol. 298(1), pages 469-495, March.
    18. Xianglai Qi & Jinjiang Yuan, 2019. "Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(01), pages 1-16, February.
    19. Christos Koulamas & George J. Kyparisis, 2006. "A heuristic for maximizing the number of on‐time jobs on two uniform parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(6), pages 568-575, September.
    20. Ivar Massabò & Giuseppe Paletta & Alex J. Ruiz-Torres, 2016. "A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem," Journal of Scheduling, Springer, vol. 19(2), pages 207-211, April.

    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:spr:jsched:v:21:y:2018:i:3:d:10.1007_s10951-018-0567-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.