Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/24869
Title: A stronger complexity result for the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs
Authors: Cheng, TCE 
Ng, CT 
Yuan, JJ
Keywords: Computational complexity
Multi-operation jobs
Scheduling
Single machine
Issue Date: 2003
Publisher: Springer
Source: Journal of scheduling, 2003, v. 6, no. 6, p. 551-555 How to cite?
Journal: Journal of scheduling 
Abstract: We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.
URI: http://hdl.handle.net/10397/24869
ISSN: 1094-6136
EISSN: 1099-1425
DOI: 10.1023/A:1026276627133
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

3
Last Week
0
Last month
0
Citations as of Oct 9, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Oct 18, 2017

Page view(s)

106
Last Week
1
Last month
Checked on Oct 15, 2017

Google ScholarTM

Check

Altmetric



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