On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem

DOI10.1287/IJOC.7.2.201MaRDI QIDQ4896447zbMATH OpenOpenAlexFDO

Authors Sunan Han, Joseph Y.-T. Leung, Dawei Hong

Publication date 10 April 1997

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

Full work available at URL https://doi.org/10.1287/ijoc.7.2.201

zbMATH Keywords

multiprocessor scheduling problemasymptotic performance of heuristic algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Probabilistic Bounds on the Performance of List Scheduling
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Stochastic limit laws for schedule makespans
• An algorithm for flow time minimization and its asymptotic makespan properties

Cited in

(7)

• List scheduling algorithms to minimize the makespan on identical parallel machines
• An algorithm for flow time minimization and its asymptotic makespan properties
• Asymptotic scheduling
• Asymptotic optimality of statistical multiplexing in pipelined processing
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• Probabilistic Bounds on the Performance of List Scheduling
• On the Expected Relative Performance of List Scheduling

This page was built for publication: On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem

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