Open-shop scheduling, where the processing times of the operations constituting a job depend on the route by which it passes through the machines, is proved to be the master problem of which both open-shop and flow-shop scheduling are special cases. The two-machine, minimum-schedule-length case, where both open-shop and flow-shop scheduling problems belong toSP, is proved to be binaryTISP-complete under a route-dependent open-shop discipline. An0(n)algorithm is presented for a special case of the latter problem with a dominating machine.