Title :
Makespan minimization on two parallel machines with release dates
Author :
Hifi, Mhand ; Kacem, Imed
Author_Institution :
Laria, Univ. Picardie Jules Verne, Amiens, France
Abstract :
In this paper, we investigate the minimization of the makespan on two parallel machines with release dates. We propose two constant approximation heuristics with performance ratios of 2 and 3 = 2. Moreover, we show that the problem admits an FPTAS (fully polynomial-time approximation scheme). The above scheme is strongly polynomial.
Keywords :
approximation theory; computational complexity; minimisation; parallel machines; approximation heuristics; fully polynomial-time approximation scheme; makespan minimization; parallel machines; Algorithm design and analysis; Approximation algorithms; Job shop scheduling; Magnetic heads; Parallel machines; Polynomials; Scheduling algorithm; Tail; Tin; Approximation; Heuristic; Parallel-Machine; Scheduling;
Conference_Titel :
Computers & Industrial Engineering, 2009. CIE 2009. International Conference on
Conference_Location :
Troyes
Print_ISBN :
978-1-4244-4135-8
Electronic_ISBN :
978-1-4244-4136-5
DOI :
10.1109/ICCIE.2009.5223871
