#### Milestone Year

### 1974

#### Just-In-Time Scheduling and partitions of the integers

Just-in-time scheduling is a central industrial paradigm
that means manufacuring parts only when they are needed,
thus eliminating inventories and streamlining assembly lines.
Just-in-time requires a partition of time into a given number $m$
of non-overlapping time-frames of decreasing density.
That is, for every $i=1,...,m$, elements of the $i$th part
should appear with constant frequency, but with frequency
that is lower than that of the $i-1$st part.
The partition should be made ``in real time'' meaning
that at time $t$ one should decide quickly to which
part $k$ belongs.

In 1973 an Institute scientist solved the above partition problem,
while being driven by a different motivation
(and while being unaware of the Just-in-time application).
In his solution the $i$th subset is the set of all integers of the form
$[k\cdot(2^m-1)/2^(m-i)]-2^(i-1)+1$, where $k=1,2,...$
and $[x]$ means rounding down $x$ to the nearest integer.
He conjectured that the method is unique; that is, for $m\geq 3$,
the sequence of numbers $a_i=(2^m-1)/2^(m-i)$, for $i=1...,m$,
is essentially the only sequence that can partition the integers
into $m$ subsets.

Mathematicians have since only been able to prove partial results
of the conjecture; and industrial scientists have used
and perfected it to design optimal Just-in-time procedures.