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 these problems 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 . We also give polynomial time algorithms, or heuristic algorithms, for all the problems considered.
Published January 1991 , 20 pages
This cahier was revised in June 1991