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

Abstract : We consider the total weighted completion time minimization for the two-parallel capacitated machines scheduling problem. In this problem, one of the machines can process jobs until a certain time T1 after which it is no longer available. The other machine is continuously available for performing jobs at any time. We prove the existence of a strongly Fully Polynomial Time Approximation Scheme (FPTAS) for the studied problem, which extends the results for the unweighted version (see Kacem, Lanuel and Sahnoune (2011)). Our FPTAS is based on the simplification of a dynamic programming algorithm.
Document type :
Journal articles
Complete list of metadatas

https://hal.univ-lorraine.fr/hal-01784175
Contributor : Lcoms Ul <>
Submitted on : Thursday, May 3, 2018 - 9:59:17 AM
Last modification on : Tuesday, May 21, 2019 - 2:22:03 PM

Identifiers

Collections

Citation

Imed Kacem, Myriam Sahnoune, Günter Schmidt. Strongly Fully Polynomial Time Approximation Scheme for the Weighted Completion Time Minimization Problem on Two-Parallel Capacitated Machines. IFAC-PapersOnLine, Elsevier, 2016, 49 (12), pp.425 - 430. ⟨10.1016/j.ifacol.2016.07.643⟩. ⟨hal-01784175⟩

Share

Metrics

Record views

59