MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK

DOI10.1142/S0129054110007301zbMath1192.68102MaRDI QIDQ3569281

Hans Kellerer, Vitaly A. Strusevich

Publication date: 18 June 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

earliness-tardinesssingle machine schedulingFPTASquadratic knapsack

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications, Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, The symmetric quadratic knapsack problem: approximation and scheduling applications, Single machine scheduling with a generalized job-dependent cumulative effect, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, A strongly polynomial FPTAS for the symmetric quadratic knapsack problem, Scheduling jobs with a V-shaped time-dependent processing time, Scheduling with common due date assignment to minimize generalized weighted earliness-tardiness penalties, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, Differential approximation schemes for half-product related functions and their scheduling applications, Approximability issues for unconstrained and constrained maximization of half-product related functions, Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection, Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product

Cites Work

• A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
• The quadratic knapsack problem -- a survey
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• Scheduling around a small common due date
• A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
• Convex quadratic and semidefinite programming relaxations in scheduling
• Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• New Lower and Upper Bounds for Scheduling Around a Small Common Due Date
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem