On the complexity of preemptive openshop scheduling problems

We investigate the complexity status of the preemptive openshop scheduling problem. After reviewing recent studies of the shop with various objective functions, we define the concept of preempting job with respect to a schedule, and state some general results for the preemptive openshop environment. These results are then used to show by reduction from the 3-Partition that the n job-2 machine mean flow time problem with ready times and job preemption is unary NP-hard.