Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines

DOI10.1051/ro/2017044zbMath1395.90148OpenAlexW2620541949WikidataQ59228840 ScholiaQ59228840MaRDI QIDQ4578168

No author found.

Publication date: 8 August 2018

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ro/2017044

zbMATH Keywords

schedulingapproximationparallel machine

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Related Items

A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint

Cites Work

• Unnamed Item
• A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
• Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates
• Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Minimizing the sum of job completion times on capacitated two-parallel machines
• Approximation algorithms for single machine scheduling with one unavailability period
• Fast approximation algorithm for job sequencing with deadlines
• Capacitated two-parallel machines scheduling to minimize sum of job completion times
• Scheduling with limited machine availability
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem