Concurrent open shop scheduling to minimize the weighted number of tardy jobs

We consider a relaxed version of the open shop scheduling problem - the "concurrent open shop" scheduling problem, in which any two operations of the same job on distinct machines are allowed to be processed concurrently. The completion time of a job is the maximum completion time of its operations. The objective is to schedule the jobs so as to minimize the weighted number of tardy jobs, with 0-1 operation processing times and a common due date d. We show that, even when the weights are identical, the problem has no (1-ε)ln m-approximation algorithm for any ε > 0 if NP is not a subset of DTIME(nloglogn), and has no c > ln m-approximation algorithm for some constant c > 0 if P≠NP, where m is the number of machines. This also implies that the problem is strongly NP-hard. We also give a (1+d)-approximation algorithm for the problem.