The authors consider the complexity status of scheduling n jobs in an openshop with m machines, when overlapping of jobs is permitted, for some classical objective functions. In particular they show that optimal schedules for a regular performance measure are permutation schedules. Then the authors prove that the maximum completion time and the maximum tardiness are polynomial, that the number of late jobs problem is binary NP-hard in the two-machine case, and that the sum of completion times and the total tardiness problems are unary NP-hard for m≥2. They also give polynomial time algorithms, or heuristic algorithms, for all the problems considered.
