DocumentCode
3155575
Title
Makespan minimization on two parallel machines with release dates
Author
Hifi, Mhand ; Kacem, Imed
Author_Institution
Laria, Univ. Picardie Jules Verne, Amiens, France
fYear
2009
fDate
6-9 July 2009
Firstpage
296
Lastpage
299
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ICCIE.2009.5223871
Filename
5223871
Link To Document