Approximation algorithms for scheduling problems with a modified total weighted tardiness objective

DOI10.1016/j.orl.2006.12.002zbMath1149.90060OpenAlexW2037297894MaRDI QIDQ2465959

Stavros G. Kolliopoulos, George Steiner

Publication date: 11 January 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2006.12.002

zbMATH Keywords

schedulingtardinessapproximation algorithmsjust-in-time scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Optimal due date assignment in multi-machine scheduling environments ⋮ Optimal restricted due date assignment in scheduling ⋮ Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments ⋮ Online scheduling to minimize total weighted (modified) earliness and tardiness cost ⋮ New results for scheduling to minimize tardiness on one machine with rejection and related problems ⋮ Online scheduling to minimize modified total tardiness with an availability constraint ⋮ A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• Single machine scheduling to minimize total weighted tardiness
• Structure of a simple scheduling polyhedron
• A fully polynomial approximation scheme for the total tardiness problem
• Approximation schemes for scheduling jobs with common due date on parallel machines to minimize Total tardiness
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Approximation algorithms for minimizing the total weighted tardiness on a single machine
• An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
• Approximation in stochastic scheduling
• Convex quadratic and semidefinite programming relaxations in scheduling
• Minimizing Total Tardiness on One Machine is NP-Hard
• Stochastic scheduling problems I — General strategies
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• An algorithm for the single machine sequencing problem with precedence constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Stochastic Machine Scheduling with Precedence Constraints
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems