Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/27486
Title: Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem
Authors: Ng, CT 
Cheng, TCE 
Yuan, JJ
Keywords: Scheduling
Single machine multi-operation jobs
Issue Date: 2002
Source: Information processing letters, 2002, v. 82, no. 4, p. 187-191 How to cite?
Journal: Information Processing Letters 
Abstract: We consider the single machine multi-operation jobs total completion time scheduling problem. 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 set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1.
URI: http://hdl.handle.net/10397/27486
ISSN: 0020-0190
DOI: 10.1016/S0020-0190(01)00274-5
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

5
Last Week
0
Last month
0
Citations as of Sep 8, 2017

WEB OF SCIENCETM
Citations

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

Page view(s)

56
Last Week
3
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.