Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling

DOI10.1137/0221007MaRDI QIDQ3990102zbMATH OpenOpenAlexFDO

Authors Li-Hui Tsai

Publication date 28 June 1992

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

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

zbMATH Keywords

makespan schedulingprobabilistic algorithm analysis

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 1375583
• An efficient load-balancing processor scheduling algorithm for parallelization of Gauss-Seidel type algorithms
• A parallel approximation scheme for the multiprocessor scheduling problem
• scientific article; zbMATH DE number 2090589
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• scientific article; zbMATH DE number 1187293
• scientific article; zbMATH DE number 444983
• Parallel algorithms for solution of problems in scheduling theory
• Scheduling parallel processors: Structural properties and optimal policies

Cited in

(20)

• An algorithm for flow time minimization and its asymptotic makespan properties
• An approximation algorithm for scheduling two parallel machines with capacity constraints.
• \(\kappa\)-partitioning problems for maximizing the minimum load
• Faster algorithms for \(k\)-subset sum and variations
• An algebraic expression of the number partitioning problem
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• An average-case analysis of online non-clairvoyant scheduling of independent parallel tasks
• Comparing the minimum completion times of two longest-first scheduling-heuristics
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• Proof of the local REM conjecture for number partitioning. I: Constant energy scales
• scientific article; zbMATH DE number 1375583 (Why is no real title available?)
• Computer-assisted proof of performance ratios for the differencing method
• On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem
• Approximating Scheduling Machines with Capacity Constraints
• scientific article; zbMATH DE number 2230249 (Why is no real title available?)
• A physicist's approach to number partitioning
• Algorithmic obstructions in the random number partitioning problem
• Partially ordered sets corresponding to the partition problem
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• Performance ratios of the Karmarkar-Karp differencing method

This page was built for publication: Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling

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