IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v47y2024i3d10.1007_s10878-024-01118-w.html
   My bibliography  Save this article

Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines

Author

Listed:
  • Ruiqing Sun

    (Yunnan University)

Abstract

In this paper, we discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The objective is to minimize the weighted makespan of jobs, i.e., the maximum weighted completion time of jobs. This scheduling problem is a generalization of minimizing the makespan on parallel machine scheduling problem. We present a ( $$2-\frac{1}{m}$$ 2 - 1 m )-approximation algorithm and a randomized efficient polynomial time approximation scheme (EPTAS) for the problem. We also design a randomized fully polynomial time approximation scheme (FPTAS) for the special case when the number of machines is fixed.

Suggested Citation

  • Ruiqing Sun, 2024. "Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines," Journal of Combinatorial Optimization, Springer, vol. 47(3), pages 1-16, April.
    • Handle: RePEc:spr:jcomop:v:47:y:2024:i:3:d:10.1007_s10878-024-01118-w
    DOI: 10.1007/s10878-024-01118-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-024-01118-w
    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/s10878-024-01118-w?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. Xing Chai & Lingfa Lu & Wenhua Li & Liqi Zhang, 2018. "Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(06), pages 1-11, December.
    2. Wenjie Li, 2015. "A Best Possible Online Algorithm for the Parallel-Machine Scheduling to Minimize the Maximum Weighted Completion Time," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(04), pages 1-10.
    3. Sainan Guo & Ran Ma & Yuzhong Zhang & Baoqiang Fan, 2021. "A Semi-Online Algorithm for Single Machine Scheduling with Rejection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 38(05), pages 1-21, October.
    4. Martin Skutella & Gerhard J. Woeginger, 2000. "A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines," Mathematics of Operations Research, INFORMS, vol. 25(1), pages 63-75, February.
    5. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    6. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    7. Klaus Jansen & Kim-Manuel Klein & José Verschae, 2020. "Closing the Gap for Makespan Scheduling via Sparsification Techniques," Mathematics of Operations Research, INFORMS, vol. 45(4), pages 1371-1392, November.
    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. Hongmin Li & Woonghee T. Huh & Matheus C. Sampaio & Naiping Keng, 2021. "Planning Production and Equipment Qualification under High Process Flexibility," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3369-3390, October.
    2. Danny Hermelin & Dvir Shabtay & Chen Zelig & Michael Pinedo, 2022. "A general scheme for solving a large set of scheduling problems with rejection in FPT time," Journal of Scheduling, Springer, vol. 25(2), pages 229-255, April.
    3. Xiangtong Qi, 2005. "A logistics scheduling model: Inventory cost reduction by batching," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 312-320, June.
    4. Alberto Caprara & Andrea Lodi & Michele Monaci, 2005. "Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 150-172, February.
    5. G. Jaykrishnan & Asaf Levin, 2024. "EPTAS for parallel identical machine scheduling with time restrictions," Journal of Combinatorial Optimization, Springer, vol. 47(2), pages 1-21, March.
    6. Jan Karel Lenstra & Franz Rendl & Frits Spieksma & Marc Uetz, 2022. "In memoriam Gerhard Woeginger," Journal of Scheduling, Springer, vol. 25(5), pages 503-505, October.
    7. 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.
    8. Wenjie Li & Jinjiang Yuan, 2021. "Single-machine online scheduling of jobs with non-delayed processing constraint," Journal of Combinatorial Optimization, Springer, vol. 41(4), pages 830-843, May.
    9. Han Zhang & Lingfa Lu & Jinjiang Yuan, 2025. "Online scheduling on an unbounded parallel-batch machine to minimize the weighted makespan," Journal of Combinatorial Optimization, Springer, vol. 49(1), pages 1-17, January.
    10. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    11. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    12. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    13. Lili Liu & Guochun Tang & Baoqiang Fan & Xingpeng Wang, 2015. "Two-person cooperative games on scheduling problems in outpatient pharmacy dispensing process," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 938-948, November.
    14. van Beek, Andries & Malmberg, Benjamin & Borm, Peter & Quant, Marieke & Schouten, Jop, 2021. "Cooperation and Competition in Linear Production and Sequencing Processes," Discussion Paper 2021-011, Tilburg University, Center for Economic Research.
    15. 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.
    16. 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.
    17. Reijnierse, Hans & Borm, Peter & Quant, Marieke & Meertens, Marc, 2010. "Processing games with restricted capacities," European Journal of Operational Research, Elsevier, vol. 202(3), pages 773-780, May.
    18. Borm, Peter & Fiestras-Janeiro, Gloria & Hamers, Herbert & Sanchez, Estela & Voorneveld, Mark, 2002. "On the convexity of games corresponding to sequencing situations with due dates," European Journal of Operational Research, Elsevier, vol. 136(3), pages 616-634, February.
    19. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    20. Ravindran Vijayalakshmi, Vipin & Schröder, Marc & Tamir, Tami, 2024. "Minimizing total completion time with machine-dependent priority lists," European Journal of Operational Research, Elsevier, vol. 315(3), pages 844-854.

    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:jcomop:v:47:y:2024:i:3:d:10.1007_s10878-024-01118-w. 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.