Strongly Fully Polynomial Time Approximation Scheme for the Weighted Completion Time Minimization Problem on Two-Parallel Capacitated Machines

Session : GTSS2-2 / GTSS2 : Heuristics and approximation algorithms for scheduling problems
Jeudi 11 février 15:00 - 16:40 Salle : CI2-04
Imed Kacem et Myriam Sahnoune

We study the n-job two-parallel machines scheduling problem with the aim of minimizing the total weighted completion time. In this problem, instead of allowing both machines to be continuously available as it is often assumed in the literature, we consider that one of the machines is available for a specified period of time after which it can no longer process any job. Based on the modification of an exact algorithm execution, we establish the existence of a strongly Fully Polynomial Time Approximation Scheme (FPTAS) for the above problem.

Mots clés : approximation, scheduling, FPTAS, heuristic, availability constraint