Algorithms

Heterogeneous Earliest Finish Time

A list scheduling heuristic that prioritizes tasks by their upward rank (distance from exit task) and assigns each to the processor that minimizes earliest finish time. One of the most widely-used DAG scheduling algorithms.

Earliest Task First

Selects the ready task with the earliest start time at each step. Assumes homogeneous computation speeds. Has formal performance bound guarantees.

Minimum Completion Time

Assigns each task to the processor that gives the minimum completion time, considering the current schedule state. A greedy node-selection heuristic.

Minimum Execution Time

Assigns each task to the processor with the fastest execution time, ignoring communication costs and load balance. A simple greedy baseline.

Best Imaginary Level

List scheduling algorithm for unrelated machines. Prioritizes tasks based on their imaginary bottom level in the task graph. Assumes homogeneous communication bandwidth.

Fast Load Balancing

An O(|T| log|V| + |D|) load-balancing algorithm. Assumes homogeneous computation and communication speeds.

Generalized Dynamic Level

Uses dynamic priority that updates as tasks are scheduled. Considers both computation cost and data locality. Assumes homogeneous communication bandwidth.

Workflow-Based Algorithm

Designed for cloud computing workflows. Considers workflow structure and cloud resource characteristics for scheduling decisions.

Critical Path on a Processor

Computes the critical path of the task graph and schedules all critical-path tasks on the single fastest processor. Non-critical tasks are scheduled using earliest finish time. Proposed alongside HEFT.

Fast Critical Path

An efficient O(|T| log|V| + |D|) scheduling algorithm based on critical path analysis. Assumes homogeneous computation and communication.

Distributed Priority Scheduling

A distributed scheduling algorithm that groups tasks into clusters and schedules them across processors using priority-based assignment.

Modified Stream Tree

A modified streaming tree-based scheduling algorithm that organizes tasks into a tree structure for efficient processor assignment.

Min-Min

Considers all unmapped tasks, computes minimum completion time on each processor, then schedules the task with the overall smallest minimum completion time first.

Max-Min

Like MinMin, but schedules the task with the largest minimum completion time first. Tends to schedule long tasks early, potentially improving parallelism.

Duplex

Runs both MinMin and MaxMin, then returns whichever schedule has the lower makespan. A simple ensemble approach.

Hybrid Batch Minimum Completion Time

A hybrid approach that combines batch scheduling with minimum completion time selection. Processes tasks in batches for improved parallelism.

Multi-Step Batch Completion

Schedules tasks in multi-step batches, considering both completion time and processor utilization at each step.

Sufferage

Assigns tasks based on their sufferage value - the difference between the best and second-best completion time. Tasks that suffer most from not getting their best assignment are prioritized.

Opportunistic Load Balancing

Assigns each task to the next available processor without considering execution time. A basic baseline with O(|T|) complexity.

Fastest Node

Schedules all tasks sequentially on the fastest processor. A simple baseline that avoids all communication costs.