IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v45y2020i2p497-516.html
   My bibliography  Save this article

Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling

Author

Listed:
  • Varun Gupta

    (Booth School of Business, University of Chicago, Chicago, Illinois 60637)

  • Benjamin Moseley

    (Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213)

  • Marc Uetz

    (Department of Applied Mathematics, University of Twente, 7522 NB Enschede, Netherlands)

  • Qiaomin Xie

    (Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of magnitude as those of earlier work and depend linearly on an upper bound on the squared coefficient of variation of the jobs’ processing times. Specifically for deterministic processing times, without and with release times, the competitive ratios are 4 and 6, respectively. As to the technical contribution, this paper shows how dual fitting techniques can be used for stochastic and nonpreemptive scheduling problems.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ormoor:v:45:y:2020:i:2:p:497-516
    DOI: 10.1287/moor.2019.0999
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2019.0999
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2019.0999?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
    ---><---

    References listed on IDEAS

    as
    1. Michael H. Rothkopf, 1966. "Scheduling with Random Service Times," Management Science, INFORMS, vol. 12(9), pages 707-713, May.
    2. José R. Correa & Maurice Queyranne, 2012. "Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 384-395, August.
    3. Leslie A. Hall & Andreas S. Schulz & David B. Shmoys & Joel Wein, 1997. "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 513-544, August.
    4. 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.
    5. Megow, N. & Vredeveld, T., 2009. "Approximating preemptive stochastic scheduling," Research Memorandum 054, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    6. 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.
    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. Tugba Saraç & Feristah Ozcelik & Mehmet Ertem, 2023. "Unrelated parallel machine scheduling problem with stochastic sequence dependent setup times," Operational Research, Springer, vol. 23(3), pages 1-19, September.

    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. 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.
    3. Santiago R. Balseiro & David B. Brown, 2019. "Approximations to Stochastic Dynamic Programs via Information Relaxation Duality," Operations Research, INFORMS, vol. 67(2), pages 577-597, 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. 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.
    6. Vredeveld, T., 2009. "Stochastic Online Scheduling," Research Memorandum 052, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    7. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    8. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    9. Marban, S. & Rutten, C. & Vredeveld, T., 2010. "Asymptotic optimality of SEPT in Bayesian scheduling," Research Memorandum 050, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    10. 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.
    11. Cole, Richard & Correa, Jose & Gkatzelis, Vasillis & Mirrokni, Vahab & Olver, Neil, 2015. "Decentralized utilitarian mechanisms for scheduling games," LSE Research Online Documents on Economics 103081, London School of Economics and Political Science, LSE Library.
    12. 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).
    13. Shabtay, Dvir & Gilenson, Miri, 2023. "A state-of-the-art survey on multi-scenario scheduling," European Journal of Operational Research, Elsevier, vol. 310(1), pages 3-23.
    14. Megow, N. & Vredeveld, T., 2009. "Approximating preemptive stochastic scheduling," Research Memorandum 054, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    15. Marban, S. & Rutten, C. & Vredeveld, T., 2010. "Tight performance in Bayesian scheduling," Research Memorandum 052, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    16. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    17. Büsing, Christina & Goetzmann, Kai-Simon & Matuschke, Jannik & Stiller, Sebastian, 2017. "Reference points and approximation algorithms in multicriteria discrete optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 829-840.
    18. Patrick Jaillet & Michael R. Wagner, 2006. "Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios," Transportation Science, INFORMS, vol. 40(2), pages 200-210, May.
    19. Bertsimas, Dimitris., 1995. "The achievable region method in the optimal control of queueing systems : formulations, bounds and policies," Working papers 3837-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    20. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.

    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:inm:ormoor:v:45:y:2020:i:2:p:497-516. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.