MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK
From MaRDI portal
Publication:3569281
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)
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product, A strongly polynomial FPTAS for the symmetric quadratic knapsack problem, Differential approximation schemes for half-product related functions and their scheduling applications, Approximability issues for unconstrained and constrained maximization of half-product related functions, Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints, Single machine scheduling with a generalized job-dependent cumulative effect, On the complexity of the single machine scheduling problem minimizing total weighted delay penalty, The symmetric quadratic knapsack problem: approximation and scheduling applications, Scheduling jobs with a V-shaped time-dependent processing time, Scheduling with common due date assignment to minimize generalized weighted earliness-tardiness penalties, Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection, Approximation schemes for scheduling on a single machine subject to cumulative deterioration and maintenance, Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
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
