IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v191y2011i1p97-11310.1007-s10479-011-0985-1.html
   My bibliography  Save this article

Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines

Author

Listed:
  • Manzhan Gu
  • Xiwen Lu

Abstract

We study the stochastic online scheduling on m uniform machines with the objective to minimize the expected value of total weighted completion times of a set of jobs that arrive over time. For each job, the processing time is a random variable, and the distribution of processing time is unknown in advance. The actual processing time could be known only when the job is completed. For the problem, we propose a policy which is proved to be asymptotically optimal when the processing times and weights are uniformly bounded, i.e. the relative error of the solution achieved by our policy approaches zero as the number of jobs increases to infinity. Copyright Springer Science+Business Media, LLC 2011

Suggested Citation

  • Manzhan Gu & Xiwen Lu, 2011. "Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines," Annals of Operations Research, Springer, vol. 191(1), pages 97-113, November.
    • Handle: RePEc:spr:annopr:v:191:y:2011:i:1:p:97-113:10.1007/s10479-011-0985-1
    DOI: 10.1007/s10479-011-0985-1
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-0985-1
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-011-0985-1?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. Mabel C. Chou & Hui Liu & Maurice Queyranne & David Simchi-Levi, 2006. "On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions," Operations Research, INFORMS, vol. 54(3), pages 464-474, June.
    2. Nicole Megow & Marc Uetz & Tjark Vredeveld, 2006. "Models and Algorithms for Stochastic Online Scheduling," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 513-525, August.
    3. Hui Liu & Maurice Queyranne & David Simchi‐Levi, 2005. "On the asymptotic optimality of algorithms for the flow shop problem with release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 232-242, 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. Manzhan Gu & Xiwen Lu & Jinwei Gu, 2017. "An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 473-495, February.
    2. Xiaoyan Zhang & Ran Ma & Jian Sun & Zan-Bo Zhang, 0. "Randomized selection algorithm for online stochastic unrelated machines scheduling," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-16.
    3. Xing Chai & Wenhua Li & Yuejuan Zhu, 2021. "Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine," Annals of Operations Research, Springer, vol. 298(1), pages 79-93, March.
    4. Xiaoyan Zhang & Ran Ma & Jian Sun & Zan-Bo Zhang, 2022. "Randomized selection algorithm for online stochastic unrelated machines scheduling," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1796-1811, October.
    5. Jinwei Gu & Manzhan Gu & Xiwen Lu & Ying Zhang, 2018. "Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 142-161, July.

    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. Martin Skutella & Maxim Sviridenko & Marc Uetz, 2016. "Unrelated Machine Scheduling with Stochastic Processing Times," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 851-864, August.
    2. Shen, Zuo-Jun Max & Xie, Jingui & Zheng, Zhichao & Zhou, Han, 2023. "Dynamic scheduling with uncertain job types," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1047-1060.
    3. Xiaoyan Zhang & Ran Ma & Jian Sun & Zan-Bo Zhang, 0. "Randomized selection algorithm for online stochastic unrelated machines scheduling," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-16.
    4. Vredeveld, T., 2009. "Stochastic Online Scheduling," Research Memorandum 052, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    5. Nicole Megow & Tjark Vredeveld, 2014. "A Tight 2-Approximation for Preemptive Stochastic Scheduling," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1297-1310, November.
    6. Xiaoyan Zhang & Ran Ma & Jian Sun & Zan-Bo Zhang, 2022. "Randomized selection algorithm for online stochastic unrelated machines scheduling," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1796-1811, October.
    7. Huiqiao Su & Guohua Wan & Shan Wang, 2019. "Online scheduling for outpatient services with heterogeneous patients and physicians," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 123-149, January.
    8. Megow, N. & Vredeveld, T., 2009. "Approximating preemptive stochastic scheduling," Research Memorandum 054, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    9. Gökalp, E. & Gülpınar, N. & Doan, X.V., 2023. "Dynamic surgery management under uncertainty," European Journal of Operational Research, Elsevier, vol. 309(2), pages 832-844.
    10. Manzhan Gu & Xiwen Lu & Jinwei Gu, 2017. "An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 473-495, February.
    11. Varun Gupta & Benjamin Moseley & Marc Uetz & Qiaomin Xie, 2020. "Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 497-516, May.
    12. Ma, Ran & Guo, Sainan, 2021. "Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 290(1), pages 57-67.
    13. Marbán Sebastián & Rutten Cyriel & Vredeveld Tjark, 2010. "Asymptotic optimality of SEPT in Bayesian Scheduling," Research Memorandum 051, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    14. Xinshang Wang & Van-Anh Truong, 2018. "Multi-Priority Online Scheduling with Cancellations," Operations Research, INFORMS, vol. 66(1), pages 104-122, January.
    15. Luscombe, Ruth & Kozan, Erhan, 2016. "Dynamic resource allocation to improve emergency department efficiency in real time," European Journal of Operational Research, Elsevier, vol. 255(2), pages 593-603.
    16. Jonathan Turner & Soonhui Lee & Mark Daskin & Tito Homem-de-Mello & Karen Smilowitz, 2012. "Dynamic fleet scheduling with uncertain demand and customer flexibility," Computational Management Science, Springer, vol. 9(4), pages 459-481, November.
    17. Megow, N. & Vredeveld, T., 2006. "Approximation results for preemptive stochastic online scheduling," Research Memorandum 053, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    18. Rowan Wang & Oualid Jouini & Saif Benjaafar, 2014. "Service Systems with Finite and Heterogeneous Customer Arrivals," Manufacturing & Service Operations Management, INFORMS, vol. 16(3), pages 365-380, July.
    19. Nicole Megow & Marc Uetz & Tjark Vredeveld, 2006. "Models and Algorithms for Stochastic Online Scheduling," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 513-525, August.
    20. Patrick Jaillet & Michael R. Wagner, 2008. "Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses," Operations Research, INFORMS, vol. 56(3), pages 745-757, June.

    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:annopr:v:191:y:2011:i:1:p:97-113:10.1007/s10479-011-0985-1. 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.