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

Federico Della Croce (), Rosario Scatamacchia () and Vincent T’kindt ()
Additional contact information
Federico Della Croce: DIGEP, Politecnico di Torino
Rosario Scatamacchia: DIGEP, Politecnico di Torino
Vincent T’kindt: Université Francois-Rabelais

Journal of Combinatorial Optimization, 2019, vol. 38, issue 2, No 15, 608-617

Abstract: 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 ) .

Keywords: Two identical parallel machines scheduling; Makespan; LPT rule; Mathematical programming; Approximation (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00399-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:2:d:10.1007_s10878-019-00399-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00399-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().