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

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

0.00 Avg rating0 Votes
Article ID: iaor2008169
Country: United Kingdom
Volume: 6
Issue: 4
Start Page Number: 405
End Page Number: 412
Publication Date: Jul 2003
Journal: Journal of Scheduling
Authors: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.