Precedence constrained scheduling to minimize sum of weighted completion times on a single machine

DOI10.1016/S0166-218X(98)00143-7zbMath1009.90053MaRDI QIDQ1961232

Rajeev Motwani, Chandra Chekuri

Publication date: 17 January 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Queues and service in operations research (90B22)

Related Items

A 2-OPT procedure to reduce total inspection time in a serial inspection process ⋮ A General Framework for Approximating Min Sum Ordering Problems ⋮ Minimum equivalent precedence relation systems ⋮ Partially ordered knapsack and applications to scheduling ⋮ On Submodular Search and Machine Scheduling ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time ⋮ Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine ⋮ Approximating Weighted Completion Time for Order Scheduling with Setup Times ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints ⋮ Preemptive and non-preemptive generalized min sum set cover ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Scheduling with bully selfish jobs ⋮ Asymptotically optimal schedules for single-server flow shop problems with setup costs and times ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ A 2-approximation algorithm for the network substitution problem ⋮ Precedence-Constrained Min Sum Set Cover ⋮ Decision diagrams for solving a job scheduling problem under precedence constraints ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling chain-structured tasks to minimize makespan and mean flow time
• Optimal task sequencing with precedence constraints
• A new approach to the maximum-flow problem
• An algorithm for the single machine sequencing problem with precedence constraints
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Single Machine Job Sequencing with Precedence Constraints
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• A Fast Parametric Maximum Flow Algorithm and Applications
• Single-Machine Job Sequencing with Treelike Precedence Ordering and Linear Delay Penalties