Task 3 — Dependency-Aware Task Scheduler

Objective

Create a scheduler that executes tasks across a limited number of workers.

Each task has:

• an ID
• execution duration
• zero or more dependencies

A task may begin only after all of its dependencies have completed.

The scheduler must determine:

• worker assignment
• start time
• finish time
• final execution order
• total workflow duration

Task Model

A possible model is:

type Task struct {
    ID           string
    Duration     int
    Dependencies []string
}

Duration is expressed in seconds.

Input

Use the following tasks:

tasks := []Task{
    {
        ID:       "fetch-source",
        Duration: 4,
    },
    {
        ID:           "build-api",
        Duration:     8,
        Dependencies: []string{"fetch-source"},
    },
    {
        ID:           "build-worker",
        Duration:     6,
        Dependencies: []string{"fetch-source"},
    },
    {
        ID:           "test-api",
        Duration:     5,
        Dependencies: []string{"build-api"},
    },
    {
        ID:           "test-worker",
        Duration:     3,
        Dependencies: []string{"build-worker"},
    },
    {
        ID:           "package",
        Duration:     4,
        Dependencies: []string{"test-api", "test-worker"},
    },
    {
        ID:           "deploy",
        Duration:     2,
        Dependencies: []string{"package"},
    },
}

Number of workers:

2

Scheduling Rules

Time begins at:

0

A worker may execute only one task at a time.

A task becomes ready when:

all dependencies are complete

When multiple tasks are ready at the same time, select them using lexicographical task ID order.

When multiple workers are available, use the worker with the lowest worker ID.

Workers are identified as:

worker-1
worker-2
...

Initial State

At time:

0

only:

fetch-source

has no dependencies.

Therefore:

worker-1:
fetch-source
start = 0
finish = 4

Worker 2 remains idle.

Time 4

When fetch-source finishes, two tasks become ready:

build-api
build-worker

With two workers:

worker-1 -> build-api
worker-2 -> build-worker

Their execution is:

build-api:
start = 4
finish = 12

build-worker:
start = 4
finish = 10

Time 10

build-worker completes.

Therefore:

test-worker

becomes ready.

Worker 2 executes:

test-worker:
start = 10
finish = 13

Time 12

build-api completes.

Therefore:

test-api

becomes ready.

Worker 1 executes:

test-api:
start = 12
finish = 17

Time 13

test-worker is complete.

However:

package

cannot begin because:

test-api

has not completed yet.

Worker 2 remains idle.

Time 17

Both package dependencies are complete.

Start:

package:
start = 17
finish = 21

Time 21

Start:

deploy:
start = 21
finish = 23

Expected Total Duration

The complete workflow finishes at:

23 seconds

Suggested Result Model

type ScheduledTask struct {
    TaskID    string
    WorkerID  int
    StartTime int
    FinishTime int
}

type ScheduleResult struct {
    Valid         bool
    Tasks         []ScheduledTask
    TotalDuration int
}

Expected Schedule

Conceptually:

fetch-source
worker 1
0 -> 4

build-api
worker 1
4 -> 12

build-worker
worker 2
4 -> 10

test-worker
worker 2
10 -> 13

test-api
worker 1
12 -> 17

package
worker 1
17 -> 21

deploy
worker 1
21 -> 23

Worker assignment for later tasks may depend on the exact deterministic worker-allocation rule, but total scheduling behavior must satisfy dependencies.

Dependency Validation

The scheduler must reject:

• missing dependencies
• duplicate task IDs
• self-dependencies
• dependency cycles

A cyclic dependency graph cannot be scheduled.

Duration Validation

Task duration must satisfy:

Duration > 0

Zero or negative durations are invalid for this exercise.

Worker Validation

Worker count must satisfy:

workers >= 1

More Ready Tasks Than Workers

If five tasks are ready but only two workers are available, execute only two.

The remaining ready tasks must wait.

Use the deterministic task-ordering rule to decide which tasks are selected first.

Worker Idle Time

Workers are allowed to remain idle when:

• no task is ready
• all remaining tasks are waiting for dependencies

The scheduler must not violate dependency rules merely to keep workers busy.

Requirements

The scheduler must:

1. validate the task graph
2. track completed dependencies
3. track worker availability
4. identify ready tasks
5. assign tasks deterministically
6. calculate start and finish times
7. preserve dependency constraints
8. calculate total workflow duration

Important Distinction

A valid topological task order is not enough.

This task also requires calculating actual execution timing with limited workers.

For example:

A
↓
B

and:

A
↓
C

may allow B and C to run in parallel when multiple workers are available.

Extension

An advanced implementation may also report:

worker utilization
worker idle time
critical execution path

These are optional extensions and are not required by the base task.

Implementation Notes

A useful implementation strategy is event-based scheduling.

The scheduler can repeatedly process the next moment when one or more running tasks finish.

At each scheduling point:

mark completed tasks
      ↓
resolve newly ready tasks
      ↓
find available workers
      ↓
assign work
      ↓
advance to next completion time

The algorithm must remain generic for arbitrary tasks, dependencies, durations, and worker counts.