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.
Paru en janvier 1991 , 20 pages
Ce cahier a été révisé en juin 1991