In a shop with transportation delays an instance carries, for every job $j$ and every ordered pair of its operations $k, l$, a delay $t_{jkl}$. Of any two operations of a job, the later one may not start before the completion of the earlier one plus the delay from the earlier to the later.

The shape field restricts the delays:

• none: all delays are $0$;
• uniform: all delays equal one number $T$;
• two values: there are two numbers, and the delays of each job all equal one of them;
• job: the delay depends on the job only, $t_j$;
• source: the delay depends on the earlier operation only, $t_k$;
• job and source: the delay does not depend on the later operation, $t_{jk}$;
• pair: the delay depends on the two positions only, $t_{kl}$, possibly required to be symmetric, $t_{kl} = t_{lk}$;
• job and pair: arbitrary delays $t_{jkl}$, possibly required to be symmetric, $t_{jkl} = t_{jlk}$.

A shape is a special case of another if its delays are among the other's.

With a transport robot, in addition every transport of a job from an operation to the next one in its sequence is carried out by a single robot: the transport starts no earlier than the completion of the operation, lasts for the delay, and ends no later than the start of the next operation. The robot may need time to travel empty, as in Brucker and Knust, Complex Scheduling, §4.6: an instance then carries, for every two machines $i, i'$, an empty moving time $t'_{ii'}$. Of any two transports, the later one departs no earlier than the arrival of the earlier one plus the time the robot needs to travel empty from the machines where it delivers the earlier one to the machines where it picks up the later one, the largest empty moving time between them. Unless the robot has empty moves, all empty moving times are $0$, and two transports merely do not overlap.

A problem with a robot and one without are incomparable. A robot without empty moves is a special case of one with them.

Theorem. The field of transportation delays is sound.