A heuristic for the two-machine open-shop scheduling problem with transportation times Original Research Article

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimize the makespan, provided that preemption is not allowed and the interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O(n log n) time and provides a worst-case performance ratio of 32.