The paper considers a problem of scheduling n jobs in a two-machine open sh
op to minimise the makespan, provided that preemption is not allowed and th
e interstage transportation times are involved. In general, this problem is
known to be NP-hard. We present a linear time algorithm that finds an opti
mal schedule if no transportation time exceeds the smallest: of the process
ing times. We also describe an algorithm that creates a heuristic solution
to the problem with job-independent transportation times. Our algorithm pro
vides a worst-case performance ratio of 8/5 if the transportation time of a
job depends on the assigned processing route. The ratio reduces to 3/2 if
all transportation times are equal.