# Scheduling

Attach feasibility and optimality to an explicit scheduling model, including resource assumptions and the objective.

## Definitions

- **Makespan**: The completion time of the last job.
- **Non-preemptive job**: A job runs continuously once it starts.
- **Identical machine model**: Every machine has the same processing rate, and independent jobs are available at time zero.

## Acceptance procedure

1. Enumerate every job-to-machine assignment.
2. Sum the durations assigned to each machine.
3. Evaluate makespan as the maximum load.
4. Check that the witness achieves the minimum across all assignments.

## Complexity

m machines and n jobs produce mⁿ assignments. In this model, job order within a machine does not change the load.

## Common failure

A balanced-looking schedule need not be optimal; release dates and precedence change the problem.

## Extensions

Add precedence-constrained schedules and dual or lower-bound certificates.

## Instances

- KL-FCS-010: An optimal two-machine schedule — Minimum makespan: 3
- KL-FCS-024: A perfectly balanced four-job schedule — Minimum makespan: 4
- KL-FCS-025: Three machines and five jobs — Minimum makespan: 4

## References

- https://developers.google.com/optimization/assignment/linear_assignment