Title: Strongly Fully Polynomial Time Approximation Scheme for the two-parallel capacitated machines scheduling problem

Authors: Imed Kacem; Yann Lanuel; Myriam Sahnoune

Addresses: Universite Paul Verlaine – Metz, Laboratoire d'Informatique Theorique et Appliquee (LITA), UFR M.I.M, Ile du Saulcy 57000, Metz, France. ' Universite Paul Verlaine – Metz, Laboratoire d'Informatique Theorique et Appliquee (LITA), UFR M.I.M, Ile du Saulcy 57000, Metz, France. ' Universite Paul Verlaine – Metz, Laboratoire d'Informatique Theorique et Appliquee (LITA), UFR M.I.M, Ile du Saulcy 57000, Metz, France

Abstract: We study the n-job two-parallel machines scheduling problem with the aim of minimising the total flow-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. On the basis of the modification of an exact algorithm execution, we establish the existence of a strongly Fully Polynomial Time Approximation Scheme (FPTAS) for the above-mentioned problem.

Keywords: parallel machine scheduling; FPTAS; fully polynomial time approximation scheme; heuristics; availability constraints; total flow time.

DOI: 10.1504/IJPS.2011.044560

International Journal of Planning and Scheduling, 2011 Vol.1 No.1/2, pp.32 - 41

Received: 12 Apr 2011
Accepted: 29 Aug 2011
Published online: 31 Dec 2011 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article