Task 5 — Deadline and Penalty Scheduling

Objective

Schedule a set of jobs on a limited number of workers.

Each job has:

Duration
Deadline
LatePenalty

A job produces its penalty if it completes after its deadline.

The objective is to minimize:

TotalPenalty

Job Model

type ScheduledJobInput struct {
    ID          string
    Duration    int
    Deadline    int
    LatePenalty int
}

Workers

Use:

2 workers

Workers are identical.

They are identified as:

W01
W02

Input

J01: Duration=4, Deadline=4,  Penalty=30
J02: Duration=3, Deadline=7,  Penalty=20
J03: Duration=6, Deadline=8,  Penalty=50
J04: Duration=2, Deadline=6,  Penalty=15
J05: Duration=5, Deadline=10, Penalty=40
J06: Duration=3, Deadline=12, Penalty=25
J07: Duration=7, Deadline=9,  Penalty=60
J08: Duration=2, Deadline=5,  Penalty=18

Scheduling Rules

All workers start at:

time = 0

A worker may execute only one job at a time.

Jobs are non-preemptive.

Once a job starts, it runs continuously until completion.

Completion Time

For a job:

FinishTime = StartTime + Duration

A job is on time when:

FinishTime <= Deadline

A job is late when:

FinishTime > Deadline

Penalty

A late job contributes its entire:

LatePenalty

The amount of lateness does not change the penalty in the base task.

Example:

Deadline = 10
Finish   = 11
Penalty  = 40

and:

Deadline = 10
Finish   = 20
Penalty  = 40

both contribute:

40

Result Model

A possible model is:

type ScheduledJob struct {
    JobID      string
    WorkerID   string
    StartTime  int
    FinishTime int
    Deadline   int
    Late       bool
    Penalty    int
}

type PenaltyScheduleResult struct {
    Jobs         []ScheduledJob
    TotalPenalty int
    TotalDuration int
}

Optimization Goal

Find a valid schedule with minimum:

TotalPenalty

The implementation must decide:

which worker executes each job

and:

in which order

Example

Suppose:

W01:
J01 -> J03

W02:
J04 -> J02

The implementation must calculate every completion time and determine which jobs miss their deadlines.

This is only an example of schedule structure.

It is not necessarily optimal.

Deterministic Tie-Breaking

If several schedules have the same minimum penalty:

1. prefer smaller overall completion time
2. then fewer late jobs
3. then compare jobs ordered by start time, worker ID, and JobID lexicographically

Total Duration

Define:

TotalDuration

as the time when the last worker finishes its last job.

Equivalent terminology:

makespan

Example:

W01 finishes at 14
W02 finishes at 11

TotalDuration = 14

Validation

Reject:

duplicate job ID
Duration <= 0
Deadline < 0
LatePenalty < 0
worker count <= 0

All Jobs Must Run

Every job must be scheduled exactly once.

The implementation may not drop a job merely to avoid its penalty.

Additional Test Case

One worker:

A: Duration=4, Deadline=4, Penalty=100
B: Duration=2, Deadline=2, Penalty=20

Schedule:

A -> B

results:

A finishes 4  -> on time
B finishes 6  -> late

TotalPenalty = 20

Schedule:

B -> A

results:

B finishes 2  -> on time
A finishes 6  -> late

TotalPenalty = 100

Expected optimal schedule:

A -> B

with:

TotalPenalty = 20

This demonstrates that:

earliest deadline first

does not necessarily minimize weighted penalties.

Zero-Penalty Job

A job may have:

LatePenalty = 0

It still must be scheduled.

It simply contributes no penalty if late.

Optional Extension — Penalty Per Time Unit

Instead of a fixed penalty, define:

PenaltyPerLateUnit

Then:

Lateness = max(0, FinishTime - Deadline)

Penalty =
    Lateness * PenaltyPerLateUnit

This changes the optimization objective significantly.

Optional Extension — Different Worker Speeds

A worker may execute different jobs at different speeds.

For example:

W01 executes J03 in 4 units
W02 executes J03 in 7 units

Duration becomes worker-dependent.

Optional Extension — Job Dependencies

Add:

Dependencies []string

A job may start only after all dependencies complete.

This combines the task with dependency-aware scheduling from Group 8.

Goal

This task demonstrates scheduling where the objective is not simply:

finish as early as possible

Instead, the scheduler must decide which deadlines are most valuable to protect.

The implementation must reason about:

job order
worker assignment
completion times
deadlines
penalties

as one optimization problem.