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

DOI10.1287/IJOC.7.2.201zbMATH Open0859.90083OpenAlexW2128392441MaRDI QIDQ4896447FDOQ4896447

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

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

zbMATH Keywords

multiprocessor scheduling problemasymptotic performance of heuristic algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cited In (7)

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