Approximation techniques for average completion time scheduling

DOI10.1137/S0097539797327180MaRDI QIDQ2719134zbMATH OpenFDO

Authors Chandra Chekuri, Rajeev Motwani, Clifford Stein, Balachandran Natarajan

Publication date 21 June 2001

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539797327180

zbMATH Keywords

approximation algorithmsparallel machine schedulingprecedence constraintsrelease datesscheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 871909
• Single machine scheduling with release dates
• Minimizing average completion time in the presence of release dates
• Scheduling jobs that arrive over time
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

Cited in

(56)

• On-line scheduling of parallel machines to minimize total completion times
• LP-based online scheduling: From single to parallel machines
• Online scheduling to minimize modified total tardiness with an availability constraint
• Scheduling parallel machines with inclusive processing set restrictions and job release times
• Minimizing average completion time in the presence of release dates
• On the approximability of average completion time scheduling under precedence constraints.
• The benefit of preemption for single machine scheduling so as to minimize total weighted completion time
• On the on-line maintenance scheduling problem
• Resource cost aware scheduling
• A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• A class of on-line scheduling algorithms to minimize total completion time
• Lower bounds for on-line single-machine scheduling.
• Robust algorithms for total completion time
• Applying ``peeling onion approach for competitive analysis in online scheduling with rejection
• Randomized selection algorithm for online stochastic unrelated machines scheduling
• Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time
• The benefit of preemption with respect to the \(\ell_p\) norm
• Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
• The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
• On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
• A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection
• The efficiency-fairness balance of round robin scheduling
• Single machine scheduling with release dates
• Almost sure asymptotic optimality for online routing and machine scheduling problems
• Dual techniques for scheduling on a machine with varying speed
• Unrelated machine scheduling with stochastic processing times
• Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling
• Fair scheduling via iterative quasi-uniform sampling
• PARALLEL PROCESSING OF CONNECTION STREAMS IN NODES OF PACKET-SWITCHED COMPUTER COMMUNICATION SYSTEMS
• Approximability of Average Completion Time Scheduling on Unrelated Machines
• Single machine batch scheduling with release times and delivery costs
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• scientific article; zbMATH DE number 871909 (Why is no real title available?)
• scientific article; zbMATH DE number 1445390 (Why is no real title available?)
• Scheduling jobs that arrive over time
• Approximability of average completion time scheduling on unrelated machines
• Exact and Approximation Algorithms for the Expanding Search Problem
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• A tight 2-approximation for preemptive stochastic scheduling
• Coping with Incomplete Information in Scheduling — Stochastic and Online Models
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Stochastic Online Scheduling Revisited
• On competitive analysis for polling systems
• Joint replenishment meets scheduling
• Reducing network and computation complexities in neural based real-time scheduling scheme
• Bicriteria two-machine flowshop scheduling: approximation algorithms and their limits
• Improved results for scheduling batched parallel jobs by using a generalized analysis framework
• Fifty years of research in scheduling -- theory and applications
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• Sequencing stochastic jobs with a single sample
• On-line scheduling to minimize average completion time revisited.
• Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time
• An on-line multi-CBR agent dispatching algorithm
• Scheduling problems in master-slave model
• Maximizing business value by optimal assignment of jobs to resources in grid computing
• On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

This page was built for publication: Approximation techniques for average completion time scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2719134)