We 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 we show that optimal schedules for a regular performance measure are permutation schedules. Then we 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. We also give polynomial time algorithms, or heuristic algorithms, for all the problems considered. 1993.
