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

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

Chandra Chekuri, Rajeev Motwani

Publication date: 17 January 2000

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

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90B22: Queues and service in operations research

Related Items

Scheduling with bully selfish jobs, A 2-OPT procedure to reduce total inspection time in a serial inspection process, Partially ordered knapsack and applications to scheduling, Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints, Single machine precedence constrained scheduling is a Vertex cover problem, 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, A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, Preemptive and non-preemptive generalized min sum set cover, An exact algorithm for the precedence-constrained single-machine scheduling problem, Asymptotically optimal schedules for single-server flow shop problems with setup costs and times, A 2-approximation algorithm for the network substitution problem, Online Linear Optimization for Job Scheduling Under Precedence Constraints, Vertex Cover in Graphs with Locally Few Colors, Approximating Single Machine Scheduling with Scenarios

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