A Heuristic of Scheduling Parallel Tasks and Its Analysis

DOI10.1137/0221021MaRDI QIDQ3990654zbMATH OpenOpenAlexFDO

Authors Qingzhou Wang, Kam Hoi Cheng

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/0221021

zbMATH Keywords

earliest completion timeidentical parallel machinesmakespanperformance ratioprecedence constraints

Mathematics Subject Classification ID

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

Recommendations

• An analysis of parallel heuristics for task allocation in multicomputers
• Optimized parallelization heuristic for task scheduling
• Worst-case analysis of scheduling heuristics of parallel systems
• A heuristic algorithm for dynamic task scheduling in highly parallel computing systems
• scientific article; zbMATH DE number 1375583
• An analysis of heuristics for the parallel-machine flexible-resource scheduling problem
• Some Heuristics for Scheduling Jobs on Parallel Machines with Setups
• Evaluating scheduling heuristics for non-identical parallel processors
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• scientific article; zbMATH DE number 1760037

Cited in

(20)

• A heuristic for the maximum processor requirement for scheduling layered task graphs with cloning
• Worst-case analysis of scheduling heuristics of parallel systems
• Scheduling multiprocessor tasks -- An overview
• On chromatic sums and distributed resource allocation
• Optimal workforce assignment to operations of a paced assembly line
• Scheduling preemptive jobs with precedence constraints on parallel machines
• Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors
• Multi-core real-time scheduling for generalized parallel task models
• Competitive online scheduling of perfectly malleable jobs with setup times
• May-Happen-in-Parallel Analysis for Priority-Based Scheduling
• Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions
• A Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines
• Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
• An effective approximation algorithm for the malleable parallel task scheduling problem
• Global EDF scheduling for parallel real-time tasks
• On-line scheduling of parallel jobs
• On-line scheduling of parallel jobs with runtime restrictions
• An almost optimal heuristic for preemptive \(C_{\text{max}}\) scheduling of dependent tasks on parallel identical machines
• Efficient approximation algorithms for scheduling moldable tasks
• List scheduling of parallel tasks

This page was built for publication: A Heuristic of Scheduling Parallel Tasks and Its Analysis

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