# An optimal two-machine schedule

KL-FCS-010 · Scheduling · version 1.0.0

## Problem

Schedule independent, non-preemptive jobs with durations [2, 2, 1] on two identical machines, all available at time zero, to minimize makespan.

## Context

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.

## Checked result

Minimum makespan: 3.

Assign the first and third jobs to machine 0 and the second to machine 1. Loads are 3 and 2. Enumeration of every assignment establishes the optimum; job order does not affect loads in this model.

## Checker reasoning

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.

## Dataset construction

{
  "family": "scheduling",
  "task": "Schedule independent, non-preemptive jobs with durations [2, 2, 1] on two identical machines, all available at time zero, to minimize makespan.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Complete assignment enumeration · 8 schedules",
  "acceptance": [
    "Enumerate every job-to-machine assignment.",
    "Sum the durations assigned to each machine.",
    "Evaluate makespan as the maximum load.",
    "Check that the witness achieves the minimum across all assignments."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "durations": [
      2,
      2,
      1
    ],
    "machines": 2,
    "constraints": "No precedence, setup time, release delay, or preemption; each machine runs its assigned jobs sequentially."
  },
  "claim": {
    "minimum_makespan": 3
  },
  "witness": {
    "assignment": [
      0,
      1,
      0
    ]
  }
}
```

## Complexity

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

## Limits

Only this job set and scheduling model; additional constraints require a new specification and checker.

## Common error and further work

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

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

## Verification

Complete assignment enumeration · 8 schedules. 8 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11.
No external dataset or model-generation experiment. Reuse-license selection
remains pending.

- [Conceptual reference](https://developers.google.com/optimization/assignment/linear_assignment)