Paper Info
Title
A tight linear time $$\frac{13}{12}$$1312-approximation algorithm for the $$P2 || C_{\max }$$P2||Cmax problem
Abstract
AbstractWe consider problem $$P2 || C_{\max }$$P2||Cmax 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}$$1312-approximation ratio improving the ratio of $$\frac{12}{11}$$1211 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).
Year
DOI
Venue
2019
10.1007/s10878-019-00399-w
Periodicals
Keywords
DocType
Volume
Two identical parallel machines scheduling,Makespan,LPT rule,Mathematical programming,Approximation
Journal
38
Issue
ISSN
Citations 
2
1382-6905
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Federico Della Croce139941.60
Rosario Scatamacchia2587.66
Vincent T'kindt320321.04