Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/13155
Title: Concurrent open shop scheduling to minimize the weighted number of tardy jobs
Authors: Ng, CT 
Cheng, TCE 
Yuan, JJ
Keywords: Concurrent open shop
Due date
In-approximability
Scheduling
Issue Date: 2003
Publisher: Springer
Source: Journal of scheduling, 2003, v. 6, no. 4, p. 405-412 How to cite?
Journal: Journal of scheduling 
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.
URI: http://hdl.handle.net/10397/13155
ISSN: 1094-6136
EISSN: 1099-1425
DOI: 10.1023/A:1024284828374
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

21
Last Week
0
Last month
0
Citations as of Sep 19, 2017

WEB OF SCIENCETM
Citations

15
Last Week
1
Last month
0
Citations as of Jul 28, 2017

Page view(s)

81
Last Week
2
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.