Smith's rule in Python
Sort jobs by nonincreasing weight divided by processing time; optimal for weighted completion time.
- File
smith_rule.py, 36 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/smith-rule/. The authors are listed in prov/5N4EPA.jsonl.
from fractions import Fraction
from functools import cmp_to_key
from typing import Sequence, Union
Number = Union[int, float, Fraction]
def smith_rule(jobs: Sequence[tuple[Number, Number]]) -> tuple[list[int], Number]:
"""Order jobs on one machine to minimize the sum of weight times completion time.
Each job is a pair (p, w) with processing time p > 0 and a real weight w.
The jobs are sorted by nonincreasing ratio w / p, compared through the cross
products w_a * p_b and w_b * p_a, with ties kept in input order. The result
is the order (0-based job indices) and its cost sum(w_j * C_j).
Cost: O(n log n) comparisons for the sort and O(n) for the cost.
"""
if any(p <= 0 for p, _ in jobs):
raise ValueError("every processing time must be positive")
def before(a: int, b: int) -> int:
(pa, wa), (pb, wb) = jobs[a], jobs[b]
left, right = wa * pb, wb * pa
return -1 if left > right else (1 if left < right else 0)
order = sorted(range(len(jobs)), key=cmp_to_key(before)) # @line L1
t: Number = 0 # @line L2
total: Number = 0
for j in order: # @line L3
p, w = jobs[j]
t = t + p # @line L4
total = total + w * t # @line L5
return order, total # @line L6
test_smith_rule.py 74 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/smith-rule/. The authors are listed in prov/5N4EPA.jsonl.
import itertools
import math
import random
import pytest
from smith_rule import smith_rule
def cost(jobs, order):
t = total = 0
for j in order:
t += jobs[j][0]
total += jobs[j][1] * t
return total
def test_example() -> None:
names = "ABCDEF"
jobs = [(3, 1), (1, 2), (4, 4), (2, 5), (5, 3), (2, 2)]
order, total = smith_rule(jobs)
assert "".join(names[j] for j in order) == "DBCFEA"
assert total == 121
assert min(cost(jobs, p) for p in itertools.permutations(range(6))) == 121
def test_edges() -> None:
assert smith_rule([]) == ([], 0)
assert smith_rule([(5, 7)]) == ([0], 35)
assert smith_rule([(2, 2), (2, 2), (2, 2)]) == ([0, 1, 2], 2 * 2 + 2 * 4 + 2 * 6)
order, total = smith_rule([(1, 0), (3, 1)])
assert order == [1, 0] and total == 3
with pytest.raises(ValueError):
smith_rule([(0, 1)])
def test_pitfall_keys() -> None:
jobs = [(3, 1), (1, 2), (4, 4), (2, 5), (5, 3), (2, 2)]
spt = sorted(range(6), key=lambda j: jobs[j][0])
heavy = sorted(range(6), key=lambda j: -jobs[j][1])
assert cost(jobs, spt) == 134 and cost(jobs, heavy) == 136
def test_negative_weights() -> None:
jobs = [(2, -3), (1, 4), (3, 0), (1, -1)]
_, total = smith_rule(jobs)
assert total == min(cost(jobs, p) for p in itertools.permutations(range(4)))
def test_against_brute_force() -> None:
rng = random.Random(9031)
for _ in range(600):
n = rng.randrange(0, 7)
jobs = [(rng.randrange(1, 8), rng.randrange(0, 8)) for _ in range(n)]
order, total = smith_rule(jobs)
assert sorted(order) == list(range(n))
assert total == cost(jobs, order)
assert total == min(cost(jobs, p) for p in itertools.permutations(range(n)))
def test_floats() -> None:
jobs = [(0.5, 1.0), (1.5, 2.0), (0.25, 0.1)]
order, total = smith_rule(jobs)
best = min(cost(jobs, p) for p in itertools.permutations(range(3)))
assert math.isclose(total, best, rel_tol=1e-12)
def test_large_integers() -> None:
jobs = [(2**40 + 1, 2**41), (2**40, 2**41 - 1)]
order, total = smith_rule(jobs)
assert total == min(cost(jobs, p) for p in itertools.permutations(range(2)))
What the next level needs
- the tests did not run in this build