Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
From MaRDI portal
Publication:1961232
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)
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, Asymptotically optimal schedules for single-server flow shop problems with setup costs and times, A 2-approximation algorithm for the network substitution problem, 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