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

A tight linear time $$\frac{13}{12}$$ 13 12 -approximation algorithm for the $$P2 || C_{\max }$$ P 2 | | C max problem

Author

Listed:
  • Federico Della Croce

    (DIGEP, Politecnico di Torino
    CNR, IEIIT)

  • Rosario Scatamacchia

    (DIGEP, Politecnico di Torino)

  • Vincent T’kindt

    (Université Francois-Rabelais)

Abstract

We consider problem $$P2 || C_{\max }$$ P 2 | | C max where the goal is to schedule n jobs on two identical parallel machines to minimize the makespan. We focus on constant factor approximation algorithms with complexity independent from the required accuracy. We exploit the famous Longest Processing Time (LPT) rule that requires to sort jobs in non-ascending order of processing times and then to assign one job at a time to the machine whose load is smallest so far. We propose an approximation algorithm that applies LPT to a subset of 2k jobs, then considers a single step of local search on the obtained subschedule and finally applies list scheduling to the remaining jobs. This algorithm, when applied for $$k=5$$ k = 5 , reaches a tight $$\frac{13}{12}$$ 13 12 -approximation ratio improving the ratio of $$\frac{12}{11}$$ 12 11 proposed by He et al. (Nav Res Logist 47:593–601, 2000). We use Mathematical Programming to analyze the approximation ratio of our approach. As a byproduct, we also show how to improve the FPTAS of Sahni for any $$n > 1/\epsilon $$ n > 1 / ϵ so as to reach an approximation ratio $$(1 + \epsilon )$$ ( 1 + ϵ ) with time complexity $$O(n + \frac{1}{\epsilon ^3})$$ O ( n + 1 ϵ 3 ) .

Suggested Citation

  • Federico Della Croce & Rosario Scatamacchia & Vincent T’kindt, 2019. "A tight linear time $$\frac{13}{12}$$ 13 12 -approximation algorithm for the $$P2 || C_{\max }$$ P 2 | | C max problem," Journal of Combinatorial Optimization, Springer, vol. 38(2), pages 608-617, August.
  • Handle: RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00399-w
    DOI: 10.1007/s10878-019-00399-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-019-00399-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-019-00399-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. Rico Walter, 2017. "A note on minimizing the sum of squares of machine completion times on two identical parallel machines," 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. 25(1), pages 139-144, March.
    2. Yong He & Hans Kellerer & Vladimir Kotov, 2000. "Linear compound algorithms for the partitioning problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(7), pages 593-601, October.
    3. Koulamas, Christos & Kyparisis, George J., 2008. "An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines," European Journal of Operational Research, Elsevier, vol. 187(2), pages 660-666, June.
    4. 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.
    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. Myungho Lee & Kangbok Lee & Michael Pinedo, 2022. "Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs," Journal of Scheduling, Springer, vol. 25(6), pages 721-740, December.
    2. Rico Walter & Alexander Lawrinenko, 2020. "A characterization of optimal multiprocessor schedules and new dominance rules," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 876-900, November.

    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. 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.
    2. Federico Della Croce & Rosario Scatamacchia, 2020. "The Longest Processing Time rule for identical parallel machines revisited," Journal of Scheduling, Springer, vol. 23(2), pages 163-176, April.
    3. Bentao Su & Naiming Xie, 2020. "Single workgroup scheduling problem with variable processing personnel," 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. 28(2), pages 671-684, June.
    4. 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.
    5. 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.
    6. 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.
    7. Guo, Shouwei & Kang, Liying, 2010. "Online scheduling of malleable parallel jobs with setup times on two identical machines," European Journal of Operational Research, Elsevier, vol. 206(3), pages 555-561, November.
    8. 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.
    9. Olawale James, GBADEYAN, & Jamiu Ola, IDRIS & Kayode Olawale, KUMOYE, & Tayo Akindele, ZUBAIR,, 2016. "Assessing The Security Of Learning Spaces In Selected Primary Schools Within Ilorin Metropolis," Ilorin Journal of Business and Social Sciences, Faculty of Social Sciences, University of Ilorin, vol. 18(2), pages 179-198, October.
    10. 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.
    11. Rico Walter, 2017. "A note on minimizing the sum of squares of machine completion times on two identical parallel machines," 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. 25(1), pages 139-144, March.
    12. Leah Epstein, 2018. "A survey on makespan minimization in semi-online environments," Journal of Scheduling, Springer, vol. 21(3), pages 269-284, 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:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00399-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.