Approximation Techniques for Average Completion Time Scheduling
From MaRDI portal
Publication:2719134
DOI10.1137/S0097539797327180zbMath0992.68066MaRDI QIDQ2719134
No author found.
Publication date: 21 June 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (43)
Lower bounds for on-line single-machine scheduling. ⋮ Online scheduling on \(m\) uniform machines to minimize total (weighted) completion time ⋮ Dual Techniques for Scheduling on a Machine with Varying Speed ⋮ Unnamed Item ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ An on-line multi-CBR agent dispatching algorithm ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection ⋮ The efficiency-fairness balance of round robin scheduling ⋮ The benefit of preemption with respect to the \(\ell_p\) norm ⋮ Single machine batch scheduling with release times and delivery costs ⋮ On competitive analysis for polling systems ⋮ Joint replenishment meets scheduling ⋮ Reducing network and computation complexities in neural based real-time scheduling scheme ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ The benefit of preemption for single machine scheduling so as to minimize total weighted completion time ⋮ Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints ⋮ Coping with Incomplete Information in Scheduling — Stochastic and Online Models ⋮ Improved results for scheduling batched parallel jobs by using a generalized analysis framework ⋮ Scheduling problems in master-slave model ⋮ Fair Scheduling via Iterative Quasi-Uniform Sampling ⋮ On the on-line maintenance scheduling problem ⋮ Resource cost aware scheduling ⋮ Maximizing business value by optimal assignment of jobs to resources in grid computing ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ On-line scheduling to minimize average completion time revisited. ⋮ Robust algorithms for total completion time ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ Almost sure asymptotic optimality for online routing and machine scheduling problems ⋮ Applying ``peeling onion approach for competitive analysis in online scheduling with rejection ⋮ On-line scheduling of parallel machines to minimize total completion times ⋮ LP-based online scheduling: From single to parallel machines ⋮ A class of on-line scheduling algorithms to minimize total completion time ⋮ PARALLEL PROCESSING OF CONNECTION STREAMS IN NODES OF PACKET-SWITCHED COMPUTER COMMUNICATION SYSTEMS ⋮ Online scheduling to minimize modified total tardiness with an availability constraint ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ Scheduling parallel machines with inclusive processing set restrictions and job release times ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ Stochastic Online Scheduling Revisited ⋮ Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time
This page was built for publication: Approximation Techniques for Average Completion Time Scheduling
